选项 1：使用 Set 数据结构检查 URL 是否已存在。设置速度很快，但空间利用率不高。

选项2：将URL存储在数据库中并检查数据库中是否有新的URL。这种方法可行，但数据库的负载会非常高。

选项 3：布隆过滤器。该选项是首选。布隆过滤器是由--Bloom于1970年提出的。它是一种概率数据结构，用于测试某个元素是否是集合的成员。

如果结果为 false，则表明该元素肯定不在集合中。

真实结果表明该元素可能在集合中。

假阳性匹配是可能的，但假阴性匹配是不可能的。

下图说明了布隆过滤器的工作原理。布隆过滤器的基本数据结构是位向量。每个位代表一个哈希值。

第 1 步：要将元素添加到布隆过滤器，我们需要将其输入 3 个不同的哈希函数（A、B 和 C），并在结果位置设置位。请注意，“”和“”在索引 5 处具有标记为 1 的相同位。由于位可能由其他元素设置，因此可能会出现误报。

步骤2：测试URL字符串是否存在时，对URL字符串应用相同的哈希函数A、B和C。如果三位都为 1，则该 URL 可能存在于数据集中；如果任意一位为0，则该URL肯定不存在于数据集中。

哈希函数的选择非常重要。它们必须均匀分布且快速。例如，和Spark使用，使用。

在我们的示例中，使用了三个哈希函数。实际上，我们应该使用多少个哈希函数？

当使用布隆过滤器时，哈希函数的数量k取决于布隆过滤器的位数组大小m和要存储的元素数量n。最佳哈希函数数量的公式为：

推导出这个公式是为了最小化布隆过滤器的误报率（即“误报率”）。

在实际应用中，常见的布隆过滤器哈希函数的数量通常在3到7之间。这个数量可以在比特数组长度和误报率之间取得很好的平衡。