我了解,为了减少单个散列冲突导致误报布隆过滤器的可能性,我使用了多个 (k) 散列。
使用 k 个数组不是更好吗,每个哈希算法对应一个数组,这样如果算法 A 将许多输入键映射到相同的值并存储在相同的数组单元格中,那么另一个键是由算法 B 映射到相同的值——这是一个有值(value)的信息,应该单独标记。 我认为大小为 m/k 的 k 个数组应该比大小为 m 的单个数组给出更好的结果。 我错了吗?
最佳答案
假设k << m
,没关系。
我们是否使用一个大小为 m
的数组或 k
大小为 m/k
的数组, 存储在过滤器中的东西的单个比特将平均碰撞 k/m
与另一个东西存储在同一个过滤器中的时间。由于这些单独的成对碰撞本质上是独立的,每个比特与其他物体碰撞的次数遵循相同的泊松分布,因此碰撞的几率是相同的,因此每个比特碰撞的几率是相同的,因此误报的几率是一样的。
因此,一切都与实现的简单性有关。
关于algorithm - 为什么布隆过滤器对所有 k 个哈希算法都使用相同的数组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49139960/