URL 去重的 6 種方案！(附詳細(xì)代碼)

文章來(lái)源于公眾號(hào)：Java中文社群 ，作者：磊哥

URL 去重在我們?nèi)粘９ぷ髦泻兔嬖囍泻艹Ｓ龅剑热邕@些：

可以看出，包括阿里，網(wǎng)易云、優(yōu)酷、作業(yè)幫等知名互聯(lián)網(wǎng)公司都出現(xiàn)過(guò)類似的面試題，而且和 URL 去重比較類似的，如 IP 黑/白名單判斷等也經(jīng)常出現(xiàn)在我們的工作中，所以我們本文就來(lái)“盤一盤”URL 去重的問(wèn)題。

URL 去重思路

在不考慮業(yè)務(wù)場(chǎng)景和數(shù)據(jù)量的情況下，我們可以使用以下方案來(lái)實(shí)現(xiàn) URL 的重復(fù)判斷：

1. 使用 Java 的 Set 集合，根據(jù)添加時(shí)的結(jié)果來(lái)判斷 URL 是否重復(fù)（添加成功表示 URL 不重復(fù)）；
2. 使用 Redis 中的 Set 集合，根據(jù)添加時(shí)的結(jié)果來(lái)判斷 URL 是否重復(fù)；
3. 將 URL 都存儲(chǔ)在數(shù)據(jù)庫(kù)中，再通過(guò) SQL 語(yǔ)句判斷是否有重復(fù)的 URL；
4. 把數(shù)據(jù)庫(kù)中的 URL 一列設(shè)置為唯一索引，根據(jù)添加時(shí)的結(jié)果來(lái)判斷 URL 是否重復(fù)；
5. 使用 Guava 的布隆過(guò)濾器來(lái)實(shí)現(xiàn) URL 判重；
6. 使用 Redis 的布隆過(guò)濾器來(lái)實(shí)現(xiàn) URL 判重。

以上方案的具體實(shí)現(xiàn)如下。

URL 去重實(shí)現(xiàn)方案

1.使用 Java 的 Set 集合判重

Set 集合天生具備不可重復(fù)性，使用它只能存儲(chǔ)值不相同的元素，如果值相同添加就會(huì)失敗，因此我們可以通過(guò)添加 Set 集合時(shí)的結(jié)果來(lái)判定 URL 是否重復(fù)，實(shí)現(xiàn)代碼如下：

public class URLRepeat {
    // 待去重 URL
    public static final String[] URLS = {
            "www.apigo.cn",
            "www.baidu.com",
            "www.apigo.cn"
    };
    public static void main(String[] args) {
        Set<String> set = new HashSet();
        for (int i = 0; i < URLS.length; i++) {
            String url = URLS[i];
            boolean result = set.add(url);
            if (!result) {
                // 重復(fù)的 URL
                System.out.println("URL 已存在了：" + url);
            }
        }
    }
}

程序的執(zhí)行結(jié)果為：

URL 已存在了：www.apigo.cn

從上述結(jié)果可以看出，使用 Set 集合可以實(shí)現(xiàn) URL 的判重功能。

2.Redis Set 集合去重

使用 Redis 的 Set 集合的實(shí)現(xiàn)思路和 Java 中的 Set 集合思想思路是一致的，都是利用 Set 的不可重復(fù)性實(shí)現(xiàn)的，我們先使用 Redis 的客戶端 redis-cli來(lái)實(shí)現(xiàn)一下 URL 判重的示例：

從上述結(jié)果可以看出，當(dāng)添加成功時(shí)表示 URL 沒(méi)有重復(fù)，但添加失敗時(shí)（結(jié)果為 0）表示此 URL 已經(jīng)存在了。

我們?cè)儆么a的方式來(lái)實(shí)現(xiàn)一下 Redis 的 Set去重，實(shí)現(xiàn)代碼如下：

// 待去重 URL
public static final String[] URLS = {
    "www.apigo.cn",
    "www.baidu.com",
    "www.apigo.cn"
};


@Autowired
RedisTemplate redisTemplate;


@RequestMapping("/url")
public void urlRepeat() {
    for (int i = 0; i < URLS.length; i++) {
        String url = URLS[i];
        Long result = redisTemplate.opsForSet().add("urlrepeat", url);
        if (result == 0) {
            // 重復(fù)的 URL
            System.out.println("URL 已存在了：" + url);
        }
    }
}

以上程序的執(zhí)行結(jié)果為：

URL 已存在了：www.apigo.cn

以上代碼中我們借助了 Spring Data 中的 RedisTemplate 實(shí)現(xiàn)的，在 Spring Boot 項(xiàng)目中要使用 RedisTemplate 對(duì)象我們需要先引入 spring-boot-starter-data-redis 框架，配置信息如下：

<!-- 添加操作 RedisTemplate 引用 -->
<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

然后需要再項(xiàng)目中配置 Redis 的連接信息，在 application.properties 中配置如下內(nèi)容：

spring.redis.host=127.0.0.1
spring.redis.port=6379
#spring.redis.password=123456 # Redis 服務(wù)器密碼，有密碼的話需要配置此項(xiàng)

經(jīng)過(guò)以上兩個(gè)步驟之后，我們就可以在 Spring Boot 的項(xiàng)目中正常的使用 RedisTemplate 對(duì)象來(lái)操作 Redis 了。

3.數(shù)據(jù)庫(kù)去重

我們也可以借助數(shù)據(jù)庫(kù)實(shí)現(xiàn) URL 的重復(fù)判斷，首先我們先來(lái)設(shè)計(jì)一張 URL 的存儲(chǔ)表，如下圖所示：

此表對(duì)應(yīng)的 SQL 如下：

/*==============================================================*/
/* Table: urlinfo                                               */
/*==============================================================*/
create table urlinfo
(
   id                   int not null auto_increment,
   url                  varchar(1000),
   ctime                date,
   del                  boolean,
   primary key (id)
);


/*==============================================================*/
/* Index: Index_url                                             */
/*==============================================================*/
create index Index_url on urlinfo
(
   url
);

其中 id 為自增的主鍵，而 url 字段設(shè)置為索引，設(shè)置索引可以加快查詢的速度。

我們先在數(shù)據(jù)庫(kù)中添加兩條測(cè)試數(shù)據(jù)，如下圖所示：

我們使用 SQL 語(yǔ)句查詢，如下圖所示：

如果結(jié)果大于 0 則表明已經(jīng)有重復(fù)的 URL 了，否則表示沒(méi)有重復(fù)的 URL。

4.唯一索引去重

我們也可以使用數(shù)據(jù)庫(kù)的唯一索引來(lái)防止 URL 重復(fù)，它的實(shí)現(xiàn)思路和前面 Set 集合的思想思路非常像。

首先我們先為字段 URL 設(shè)置了唯一索引，然后再添加 URL 數(shù)據(jù)，如果能添加成功則表明 URL 不重復(fù)，反之則表示重復(fù)。

創(chuàng)建唯一索引的 SQL 實(shí)現(xiàn)如下：

create unique index Index_url on urlinfo
(
   url
);

5.Guava 布隆過(guò)濾器去重

布隆過(guò)濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

布隆過(guò)濾器的核心實(shí)現(xiàn)是一個(gè)超大的位數(shù)組和幾個(gè)哈希函數(shù)，假設(shè)位數(shù)組的長(zhǎng)度為 m，哈希函數(shù)的個(gè)數(shù)為 k。

以上圖為例，具體的操作流程：假設(shè)集合里面有 3 個(gè)元素 {x, y, z}，哈希函數(shù)的個(gè)數(shù)為 3。首先將位數(shù)組進(jìn)行初始化，將里面每個(gè)位都設(shè)置位 0。對(duì)于集合里面的每一個(gè)元素，將元素依次通過(guò) 3 個(gè)哈希函數(shù)進(jìn)行映射，每次映射都會(huì)產(chǎn)生一個(gè)哈希值，這個(gè)值對(duì)應(yīng)位數(shù)組上面的一個(gè)點(diǎn)，然后將位數(shù)組對(duì)應(yīng)的位置標(biāo)記為 1，查詢 W 元素是否存在集合中的時(shí)候，同樣的方法將 W 通過(guò)哈希映射到位數(shù)組上的 3 個(gè)點(diǎn)。如果 3 個(gè)點(diǎn)的其中有一個(gè)點(diǎn)不為 1，則可以判斷該元素一定不存在集合中。反之，如果 3 個(gè)點(diǎn)都為 1，則該元素可能存在集合中。注意：此處不能判斷該元素是否一定存在集合中，可能存在一定的誤判率?？梢詮膱D中可以看到：假設(shè)某個(gè)元素通過(guò)映射對(duì)應(yīng)下標(biāo)為 4、5、6 這 3 個(gè)點(diǎn)。雖然這 3 個(gè)點(diǎn)都為 1，但是很明顯這 3 個(gè)點(diǎn)是不同元素經(jīng)過(guò)哈希得到的位置，因此這種情況說(shuō)明元素雖然不在集合中，也可能對(duì)應(yīng)的都是 1，這是誤判率存在的原因。

我們可以借助 Google 提供的 Guava 框架來(lái)操作布隆過(guò)濾器，實(shí)現(xiàn)我們先在 pom.xml 中添加 Guava 的引用，配置如下：

<!-- 添加 Guava 框架 -->
<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.2-jre</version>
</dependency>

URL 判重的實(shí)現(xiàn)代碼：

public class URLRepeat {
    // 待去重 URL
    public static final String[] URLS = {
            "www.apigo.cn",
            "www.baidu.com",
            "www.apigo.cn"
    };


    public static void main(String[] args) {
        // 創(chuàng)建一個(gè)布隆過(guò)濾器
        BloomFilter<String> filter = BloomFilter.create(
                Funnels.stringFunnel(Charset.defaultCharset()),
                10, // 期望處理的元素?cái)?shù)量
                0.01); // 期望的誤報(bào)概率
        for (int i = 0; i < URLS.length; i++) {
            String url = URLS[i];
            if (filter.mightContain(url)) {
                // 用重復(fù)的 URL
                System.out.println("URL 已存在了：" + url);
            } else {
                // 將 URL 存儲(chǔ)在布隆過(guò)濾器中
                filter.put(url);
            }
        }
    }
}

以上程序的執(zhí)行結(jié)果為：

URL 已存在了：www.apigo.cn

6.Redis 布隆過(guò)濾器去重

除了 Guava 的布隆過(guò)濾器，我們還可以使用 Redis 的布隆過(guò)濾器來(lái)實(shí)現(xiàn) URL 判重。在使用之前，我們先要確保 Redis 服務(wù)器版本大于 4.0（此版本以上才支持布隆過(guò)濾器），并且開啟了 Redis 布隆過(guò)濾器功能才能正常使用。

以 Docker 為例，我們來(lái)演示一下 Redis 布隆過(guò)濾器安裝和開啟，首先下載 Redis 的布隆過(guò)器，然后再在重啟 Redis 服務(wù)時(shí)開啟布隆過(guò)濾器，如下圖所示：

布隆過(guò)濾器使用:布隆過(guò)濾器正常開啟之后，我們先用 Redis 的客戶端 redis-cli 來(lái)實(shí)現(xiàn)一下布隆過(guò)濾器 URL 判重了，實(shí)現(xiàn)命令如下：

在 Redis 中，布隆過(guò)濾器的操作命令不多，主要包含以下幾個(gè)：

- bf.add 添加元素；
- bf.exists 判斷某個(gè)元素是否存在；
- bf.madd 添加多個(gè)元素；
- bf.mexists 判斷多個(gè)元素是否存在；
- bf.reserve 設(shè)置布隆過(guò)濾器的準(zhǔn)確率。

接下來(lái)我們使用代碼來(lái)演示一下 Redis 布隆過(guò)濾器的使用：

import redis.clients.jedis.Jedis;
import utils.JedisUtils;


import java.util.Arrays;


public class BloomExample {
    // 布隆過(guò)濾器 key
    private static final String _KEY = "URLREPEAT_KEY";

    
    // 待去重 URL
    public static final String[] URLS = {
            "www.apigo.cn",
            "www.baidu.com",
            "www.apigo.cn"
    };


    public static void main(String[] args) {
        Jedis jedis = JedisUtils.getJedis();
         for (int i = 0; i < URLS.length; i++) {
            String url = URLS[i];
            boolean exists = bfExists(jedis, _KEY, url);
            if (exists) {
                // 重復(fù)的 URL
                System.out.println("URL 已存在了：" + url);
            } else {
                bfAdd(jedis, _KEY, url);
            }
        }
    }


    /**
     * 添加元素
     * @param jedis Redis 客戶端
     * @param key   key
     * @param value value
     * @return boolean
     */
    public static boolean bfAdd(Jedis jedis, String key, String value) {
        String luaStr = "return redis.call('bf.add', KEYS[1], KEYS[2])";
        Object result = jedis.eval(luaStr, Arrays.asList(key, value),
                Arrays.asList());
        if (result.equals(1L)) {
            return true;
        }
        return false;
    }


    /**
     * 查詢?cè)厥欠翊嬖?     * @param jedis Redis 客戶端
     * @param key   key
     * @param value value
     * @return boolean
     */
    public static boolean bfExists(Jedis jedis, String key, String value) {
        String luaStr = "return redis.call('bf.exists', KEYS[1], KEYS[2])";
        Object result = jedis.eval(luaStr, Arrays.asList(key, value),
                Arrays.asList());
        if (result.equals(1L)) {
            return true;
        }
        return false;
    }
}

以上程序的執(zhí)行結(jié)果為：

URL 已存在了：www.apigo.cn

總結(jié)

本文介紹了 6 種 URL 去重的方案，其中 Redis Set、Redis 布隆過(guò)濾器、數(shù)據(jù)庫(kù)和唯一索引這 4 種解決方案適用于分布式系統(tǒng)，如果是海量的分布式系統(tǒng)，建議使用 Redis 布隆過(guò)濾器來(lái)實(shí)現(xiàn) URL 去重，如果是單機(jī)海量數(shù)據(jù)推薦使用 Guava 的布隆器來(lái)實(shí)現(xiàn) URL 去重。

以上就是W3Cschool編程獅關(guān)于URL 去重的 6 種方案！(附詳細(xì)代碼)的相關(guān)介紹了，希望對(duì)大家有所幫助。