1. 原理
布隆过滤器拥有K个哈希函数,当一个元素要加入布隆过滤器时,会使用K个哈希函数对其进行计算,得到K个哈希值,然后根据哈希值,在一维数组中把其对应下标的值置位1。
要判断某个数是否在布隆过滤器中,就进行K次哈希计算,得到哈希值,然后在位数组中判断哈希值对应位置是否都为1,如果都为1,就说明这个值可能在布隆过滤器中,需要进一步确认。
如果一个值不在过滤器中,那么他一定不存在,如果一个值在过滤器中,他并不一定存在,需要进一步确认
2. 误报率
误报率:一个不存在的值,其K个Hash值所对应位置都为1的概率。
推导
解释
m: 过滤器位数组长度
n:插入元素的个数
k:哈希函数的个数
p:假阳性(误报)概率
假定
- 位数组长m位
- 哈希函数对每个位置等概率插入
- 一共K个哈希函数
- 向bloom过滤器中插入n个值
那么
-
任意一位被设置为1的概率为\(\frac{1}{m}\)
-
不被设置为1的概率就是\(1-\frac{1}{m}\)
-
经过K个哈希函数,仍未被设置为1的概率就是\((1-\frac{1}{m})^k\)
-
插入n个值后,仍未被设置为1的概率是\((1-\frac{1}{m})^{kn}\)
可变形为\(((1-\frac{1}{m})^{-m})^\frac{-kn}{m}\)
对其中的\((1-\frac{1}{m})^{-m}\)进行变形
-
被设置为1的概率就是
\(1-e^{\frac{-kn}{m}}\)
-
现在要误报率,即K个散列函数计算出的位置的值都是1,这个概率是
\(p = (1-e^{\frac{-kn}{m}})^k\) --
公式1
随着m(位数组大小)的增加,假阳性概率会下降,同时随着插入元素个数n的增加,假阳性概率又会上升。
人们对上述公式进行分析后发现,对于给定的m和n,当 k=\(\frac{m}{n}\ln2\approx\frac{m}{n}*0.7\) 的时候p最小
将上述k的最佳值带入公式1
,可得
\({\displaystyle p =\left(1-e^{-({\frac {m}{n}}\ln 2){\frac {n}{m}}}\right)^{{\frac { m}{n}}\ln 2}}\)
化简可得\(m=-\frac{n\ln^p}{(\ln2)^2}\),由此得出m的最佳值
上述公式怎么用?
当创建布隆过滤器时,用户需要提供预计插入的元素个数n
和可接受的误报率p
- 通过n和p算出m
- 通过n和m算出k
3. golang实现
仿照guava完成,hash函数用的是golang提供,代码很简单,不到100行
https://github.com/INnoVationv2/corekv_diy/tree/bloom-filter
标签:概率,frac,布隆,kn,哈希,过滤器,原理 From: https://www.cnblogs.com/INnoVationv2/p/17649559.html