URL 如何防止 抓取重复的 面试官 Google

如何防止 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 个之间，这个数量能在位数组长度和误判率之间到达较好的平衡。