布隆过滤器原理及实现
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