布隆过滤器的实现原理
布隆过滤器可以理解为一个不怎么精确的
set
结构，当你使用它的
contains
方法判断某
个对象是否存在时，它可能会误判。但是布隆过滤器也不是特别不精确，只要参数设置的合
理，它的精确度可以控制的相对足够精确，只会有小小的误判概率。
当布隆过滤器说某个值存在时，这个值可能不存在；当它说不存在时，那就肯定不存
在。打个比方，当它说不认识你时，肯定就不认识；当它说见过你时，可能根本就没见过
面，不过因为你的脸跟它认识的人中某脸比较相似
(
某些熟脸的系数组合
)
，所以误判以前见
过你。
布隆过滤器的hash分发标注原理，一般用3-5个hash算法进去标注
每个布隆过滤器对应到
Redis
的数据结构里面就是一个大型的位数组和几个不一样的无
偏
hash
函数。所谓无偏就是能够把元素的
hash
值算得比较均匀。
向布隆过滤器中添加
key
时，会使用多个
hash
函数对
key
进行
hash
算得一个整数索
引值然后对位数组长度进行取模运算得到一个位置，每个
hash
函数都会算得一个不同的位
置。
空
间占用估计
布隆过滤器的空间占用有一个简单的计算公式，但是推导比较繁琐，这里就省去推导过
程了，直接引出计算公式，感兴趣的读者可以点击「扩展阅读」深入理解公式的推导过程。
布隆过滤器有两个参数，第一个是预计元素的数量
n
，第二个是错误率
f
。公式根据这
两个输入得到两个输出，第一个输出是位数组的长度
l
，也就是需要的存储空间大小
(bit)
，
第二个输出是
hash
函数的最佳数量
k
。
hash
函数的数量也会直接影响到错误率，最佳的数
量会有最低的错误率。
k=0.7*(l/n)
# 约等于
f=0.6185^(l/n)
# ^ 表示次方计算，也就是 math.pow
错误率估计
错误率其实是根据位数组的长度和hash函数的个数决定的。一般3-5个hash函数，并不是越大越好。