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

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

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

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

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

假陽性匹配是可能的，但假陰性匹配是不可能的。

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

圖片

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

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

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

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

這個公式是為了最小化布隆過濾器的誤判率（即“假陽性率”）而得出的。

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