我的布隆过滤器需要多少个哈希函数？

维基百科说:

空Bloom过滤器是m位的位数组,全部设置为0.还必须定义k个不同的散列函数,每个散列函数将一些集合元素映射或散列到具有均匀随机分布的m个阵列位置之一.

我读了这篇文章,但我不明白的是k是如何确定的.它是表格大小的函数吗？

此外,在我编写的哈希表中,我使用了一种简单但有效的算法来自动增加哈希的大小.基本上,如果表中超过50%的桶被填满,我会将表的大小加倍.我怀疑你可能仍然希望使用布隆过滤器来减少误报.正确吗？

鉴于:

n:您希望过滤器中有多少件物品(例如216,553)

p:您可接受的误报率{0..1}(例如0.01→1%)

我们要计算:

m:bloom过滤器中所需的位数

k:我们应该应用的哈希函数的数量

公式:

m = -n*ln(p) / (ln(2)^2) 散列函数的位数
k = m/n * ln(2)

在我们的情况下:

m= -216553*ln(0.01) / (ln(2)^2)= 997263 / 0.48045= 2,075,686位(253 kB)

k= m/n * ln(2)= 2075686/216553 * 0.693147= 6.46散列函数(7个散列函数)

注意:任何代码都会发布到公共领域.无需归属.

如果您在维基百科关于Bloom过滤器的文章中进一步阅读,那么您会找到一个误报概率部分.本节解释了散列函数的数量如何影响误报的概率,并为您提供了从期望的预期概率确定k的公式.误报.

来自维基百科文章的引用:

显然,假阳性的概率随着m(阵列中的位数)的增加而减小,并且随着n(插入元素的数量)的增加而增加.对于给定的m和n,最小化概率的k的值(散列函数的数量)是

把它摆放在一张整洁的小桌子里:

http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html