我的布隆过滤器需要多少个哈希函数？
dic*_*oce 17 algorithm bloom-filter
维基百科说:
空Bloom过滤器是m位的位数组,全部设置为0.还必须定义k个不同的散列函数,每个散列函数将一些集合元素映射或散列到具有均匀随机分布的m个阵列位置之一.
我读了这篇文章,但我不明白的是k是如何确定的.它是表格大小的函数吗？
此外,在我编写的哈希表中,我使用了一种简单但有效的算法来自动增加哈希的大小.基本上,如果表中超过50%的桶被填满,我会将表的大小加倍.我怀疑你可能仍然希望使用布隆过滤器来减少误报.正确吗？
Ian*_*oyd 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个散列函数)
注意:任何代码都会发布到公共领域.无需归属.
f3l*_*lix 17
如果您在维基百科关于Bloom过滤器的文章中进一步阅读,那么您会找到一个误报概率部分.本节解释了散列函数的数量如何影响误报的概率,并为您提供了从期望的预期概率确定k的公式.误报.
来自维基百科文章的引用:
显然,假阳性的概率随着m(阵列中的位数)的增加而减小,并且随着n(插入元素的数量)的增加而增加.对于给定的m和n,最小化概率的k的值(散列函数的数量)是
