algorithm - 为什么布隆过滤器对所有 k 个哈希算法都使用相同的数组

Question

我了解，为了减少单个散列冲突导致误报布隆过滤器的可能性，我使用了多个 (k) 散列。

使用 k 个数组不是更好吗，每个哈希算法对应一个数组，这样如果算法 A 将许多输入键映射到相同的值并存储在相同的数组单元格中，那么另一个键是由算法 B 映射到相同的值——这是一个有值(value)的信息，应该单独标记。我认为大小为 m/k 的 k 个数组应该比大小为 m 的单个数组给出更好的结果。我错了吗？

Answer 1

假设k << m ，没关系。

我们是否使用一个大小为 m 的数组或 k大小为 m/k 的数组, 存储在过滤器中的东西的单个比特将平均碰撞 k/m与另一个东西存储在同一个过滤器中的时间。由于这些单独的成对碰撞本质上是独立的，每个比特与其他物体碰撞的次数遵循相同的泊松分布，因此碰撞的几率是相同的，因此每个比特碰撞的几率是相同的，因此误报的几率是一样的。

因此，一切都与实现的简单性有关。