标签：概率 frac 布隆 kn 哈希 过滤器 原理

1. 原理

布隆过滤器拥有K个哈希函数，当一个元素要加入布隆过滤器时，会使用K个哈希函数对其进行计算，得到K个哈希值，然后根据哈希值，在一维数组中把其对应下标的值置位1。

要判断某个数是否在布隆过滤器中，就进行K次哈希计算，得到哈希值，然后在位数组中判断哈希值对应位置是否都为1，如果都为1，就说明这个值可能在布隆过滤器中，需要进一步确认。

如果一个值不在过滤器中，那么他一定不存在，如果一个值在过滤器中，他并不一定存在，需要进一步确认

2. 误报率

误报率：一个不存在的值，其K个Hash值所对应位置都为1的概率。

推导

解释

m: 过滤器位数组长度
n：插入元素的个数
k：哈希函数的个数
p：假阳性(误报)概率

假定

1. 位数组长m位
2. 哈希函数对每个位置等概率插入
3. 一共K个哈希函数
4. 向bloom过滤器中插入n个值

那么

1. 任意一位被设置为1的概率为\(\frac{1}{m}\)

2. 不被设置为1的概率就是\(1-\frac{1}{m}\)

3. 经过K个哈希函数，仍未被设置为1的概率就是\((1-\frac{1}{m})^k\)

4. 插入n个值后，仍未被设置为1的概率是\((1-\frac{1}{m})^{kn}\)

   可变形为\(((1-\frac{1}{m})^{-m})^\frac{-kn}{m}\)

   对其中的\((1-\frac{1}{m})^{-m}\)进行变形

\[(1-\frac{1}{m})^{-m} \\ 令t = -m,有(1+\frac{1}{t})^t \\ 当t足够大时，由e的定义 \\ e=\displaystyle\lim_{x->\infty}(1+\frac{1}{x})^x \\ 所以, \displaystyle\lim_{m->\infty}(1-\frac{1}{m})^{-m} = e \\ \\ 因此, ((1-\frac{1}{m})^{-m})^\frac{-kn}{m} \approx e^{\frac{-kn}{m}} \]

5. 被设置为1的概率就是

   \(1-e^{\frac{-kn}{m}}\)

6. 现在要误报率，即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

1. 通过n和p算出m
2. 通过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