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

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

4.唯一索引去重

我們也可以使用數(shù)據(jù)庫的唯一索引來防止 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 布隆過濾器去重

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

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

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

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

  <dependency> <groupId>com.google.guavagroupId> <artifactId>guavaartifactId> <version>28.2-jreversion> 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è)布隆過濾器 BloomFilterfilter?=?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?存儲在布隆過濾器中 filter.put(url);
????????????}
????????}
????}
}

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

URL 已存在了：www.apigo.cn

6.Redis 布隆過濾器去重

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

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

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

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

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

接下來我們使用代碼來演示一下 Redis 布隆過濾器的使用：

import redis.clients.jedis.Jedis; import utils.JedisUtils; import java.util.Arrays; public class BloomExample { //?布隆過濾器?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;
????} /**
?????*?查詢元素是否存在
?????* @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 布隆過濾器、數(shù)據(jù)庫和唯一索引這 4 種解決方案適用于分布式系統(tǒng)，如果是海量的分布式系統(tǒng)，建議使用 Redis 布隆過濾器來實(shí)現(xiàn) URL 去重，如果是單機(jī)海量數(shù)據(jù)推薦使用 Guava 的布隆器來實(shí)現(xiàn) URL 去重。