algorithm - 散列值如何映射到布隆过滤器中的向量？

Question

在实现布隆过滤器时，有几个潜在的事件部分:

m = 位向量的大小 n = 项目(预期)插入过滤器 k = 要使用的哈希数

我知道 m/n 和 k 之间存在最佳关系，但是对于如何将 k 哈希值映射到位向量以获得更大的 m 值，我还没有找到明确的解释。

在几乎每个示例中，我都读到人们使用微不足道的 m 值 (>256)，并且它们显示哈希函数严重重叠。对于少于 256 位的情况，很容易想象有 k 个 256 位哈希函数并将它们与向量进行或运算。

随着 m 变大以降低较大 n 值的误报率，我不确定应如何将 HashMap 到向量。我已经看到一些想法，例如对向量进行分区并将“独立”(例如不同的杂音种子)哈希应用于向量的每个 128 位部分。但是，我还没有看到如何为更大的 n/m 值实现布隆过滤器的具体示例。

Answer 1

在我学习布隆过滤器的时候，下面的页面对我帮助很大:

http://matthias.vallentin.net/blog/2011/06/a-garden-variety-of-bloom-filters/

那里描述的所有内容都是作为开源库实现的。查看其来源也很有帮助。