algorithm - 布隆过滤器中的过滤器索引和哈希函数

Question

布隆过滤器使用 m 位的位数组，因此数组中有 0 到 m-1 个索引，但我使用的散列函数返回一个 32 位散列，因此它可能是从 0 到 (2^32 )-1 因为散列用作位数组(过滤器)的索引，所以散列很可能大于 m，因此该值不会映射到位数组。我是否应该采用散列的 mod，即 hash % m 以便生成的散列必须对应于位数组中的索引。它会增加误报的数量(IMO 它会)吗？

Answer 1

散列函数 h: S -> uint 被松散地定义为在集合 S 上表现出高度熵的函数。假设我有一个特定的散列函数 h，它在 S 上具有非常高的熵，但是 的输出 h(x) S 中的 x 始终为偶数。此限制仅意味着 h 的输出中有一部分被浪费了，只有 1/32 位。

现在假设我有一个布隆过滤器，其中 m 是偶数。然后 h(x) % m 将始终为偶数 - 这意味着只有一半的 Bloom 过滤器将被使用!这很糟糕!

正如其他人所建议的，只需将 h(x) 的前 m 位作为 2^m 布隆过滤器箱的索引是一个更好的策略，因为，假设给定的散列函数在集合 S 上表现出高度熵，“第一个 m 位”散列函数g(x) = h(x)[0:m-1] 应该表现出几乎成比例的熵。