如何避免 Google 抓取重复的 URL？
方案 1 ：使用 Set 数据结构检查 URL 是否已经存在。Set 速度很快，但不节省空间。
方案 2 ：在数据库中存储 URL，并检查数据库中是否有新的 URL。这种方法可行，但数据库的负载会非常高。
方案 3 ：布隆过滤器。此方案更受青睐。布隆过滤器由伯顿-霍华德-布隆（Burton Howard Bloom）于 1970 年提出。它是一种概率数据结构，用于测试某个元素是否是某个集合的成员。
假阳性匹配是可能的，但假阴性匹配是不可能的。
下图说明了布隆过滤器的工作原理。布隆过滤器的基本数据结构是比特矢量。每个比特代表一个散列值。
哈希函数的选择非常重要。它们必须分布均匀、速度快。例如，RedisBloom 和 Apache Spark 使用 murmur，InfluxDB 使用 xxhash。
在我们的示例中，使用了三个哈希函数。在现实中，我们应该使用多少个哈希函数？
在使用布隆过滤器时，哈希函数的数量 k 取决于布隆过滤器的位数组大小 m 和要存储的元素数量 n。最佳哈希函数数量的公式为：
这个公式是为了 最小化布隆过滤器的误判率 （即“假阳性率”）而得出的。
在实际应用中，常见的布隆过滤器哈希函数数量通常在 3 到 7 个之间，这个数量能在位数组长度和误判率之间达到较好的平衡。
© 版权声明