如何避免 Google 抓取重復(fù)的 URL？

方案 1：使用 Set 數(shù)據(jù)結(jié)構(gòu)檢查 URL 是否已經(jīng)存在。Set 速度很快，但不節(jié)省空間。

方案 2：在數(shù)據(jù)庫(kù)中存儲(chǔ) URL，并檢查數(shù)據(jù)庫(kù)中是否有新的 URL。這種方法可行，但數(shù)據(jù)庫(kù)的負(fù)載會(huì)非常高。

方案 3：布隆過(guò)濾器。此方案更受青睞。布隆過(guò)濾器由伯頓-霍華德-布?。˙urton Howard Bloom）于 1970 年提出。它是一種概率數(shù)據(jù)結(jié)構(gòu)，用于測(cè)試某個(gè)元素是否是某個(gè)集合的成員。

• 結(jié)果為 false 說(shuō)明元素肯定不在集合中。
• 結(jié)果為 true 說(shuō)明元素可能在集合中。

假陽(yáng)性匹配是可能的，但假陰性匹配是不可能的。

下圖說(shuō)明了布隆過(guò)濾器的工作原理。布隆過(guò)濾器的基本數(shù)據(jù)結(jié)構(gòu)是比特矢量。每個(gè)比特代表一個(gè)散列值。

圖片

• 第 1 步：要在布隆過(guò)濾器中添加一個(gè)元素，我們需要將其輸入 3 個(gè)不同的散列函數(shù)（A、B 和 C），并在結(jié)果位置上設(shè)置比特。請(qǐng)注意，“www.myweb1.com”和“www.myweb2.com”都在索引 5 處用 1 標(biāo)記了相同的位。由于比特可能被其他元素設(shè)置，因此可能出現(xiàn)誤報(bào)。
• 第 2 步：測(cè)試 URL 字符串是否存在時(shí)，對(duì) URL 字符串應(yīng)用相同的哈希函數(shù) A、B 和 C。如果三個(gè)位都為 1，則數(shù)據(jù)集中可能存在 URL；如果任何一位為 0，則數(shù)據(jù)集中肯定不存在 URL。

哈希函數(shù)的選擇非常重要。它們必須分布均勻、速度快。例如，RedisBloom 和 Apache Spark 使用 murmur，InfluxDB 使用 xxhash。

在我們的示例中，使用了三個(gè)哈希函數(shù)。在現(xiàn)實(shí)中，我們應(yīng)該使用多少個(gè)哈希函數(shù)？

在使用布隆過(guò)濾器時(shí)，哈希函數(shù)的數(shù)量 k 取決于布隆過(guò)濾器的位數(shù)組大小 m 和要存儲(chǔ)的元素?cái)?shù)量 n。最佳哈希函數(shù)數(shù)量的公式為：

這個(gè)公式是為了最小化布隆過(guò)濾器的誤判率（即“假陽(yáng)性率”）而得出的。

在實(shí)際應(yīng)用中，常見(jiàn)的布隆過(guò)濾器哈希函數(shù)數(shù)量通常在 3 到 7 個(gè)之間，這個(gè)數(shù)量能在位數(shù)組長(zhǎng)度和誤判率之間達(dá)到較好的平衡。