如何避免 Google 抓取重復的 URL？

方案 1：使用 Set 數據結構檢查 URL 是否已經存在。Set 速度很快，但不節省空間。

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

方案 3：布隆過濾器。此方案更受青睞。布隆過濾器由伯頓-霍華德-布隆（Burton Howard Bloom）于 1970 年提出。它是一種概率數據結構，用于測試某個元素是否是某個集合的成員。

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

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

下圖說明了布隆過濾器的工作原理。布隆過濾器的基本數據結構是比特矢量。每個比特代表一個散列值。

圖片

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

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

在我們的示例中，使用了三個哈希函數。在現實中，我們應該使用多少個哈希函數？

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

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

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