方案 1：使用 Set 数据结构检查 URL 是否已存在，如此设计速度很快，但不节省空间。
方案 2：将 URL 存储在数据库中，并检查数据库中是否有新的 URL，可以运行，但数据库的负载将非常高。
方案 3：BloomFilter，此方案是首选，BloomFilter于1970年提出。它是一种概率数据结构，用于测试元素是否是集合的成员。 false：元素肯定不在集合中。 true：元素可能在集合中。 下图说明了 BloomFilter的工作原理。BloomFilter的基本数据结构是位图，每个位表示一个哈希值。
步骤1：要将元素添加到布隆过滤器，我们将其提供给3个不同的哈希函数（A，B和C），并在结果位置设置。请留意，“www.myweb1.com”和“www.myweb2.com”在索引 5 处用 1 标记相同的位，碰撞是可能的，因为一个位可能由另一个元素设置。
步骤 2：测试 URL 字符串是否存在时，相同的哈希函数 A、B 和 C 将应用于 URL 字符串。如果所有三个位均为1，则URL可能存在于数据集中;如果任何位为 0，则 URL 在数据集中肯定不存在。
哈希函数选择很重要。它们必须均匀分布且快速。例如，RedisBloom和Apache Spark使用murmur，InfluxDB使用xxhash。
问题 - 在我们的示例中，我们使用了三个哈希函数。在现实中我们应该使用多少个哈希函数？权衡取舍是什么？
欢迎交流，评论转发！
| 留言与评论（共有 0 条评论） “” |
