Bloom Filter

概率计算：

False Positive 概率（k个函数，n个数后全部为1的概率）

image.png

实际使用场景：

当n很大时，误报率会上升，

 python
 math.pow(1-math.exp(-k*n/m),k)

>>> math.pow(1-math.exp(-8*20/256),8)
0.02549173076596687
>>> math.pow(1-math.exp(-8*16/256),8)
0.02549173076596687
>>> math.pow(1-math.exp(-8*32/512),8)
0.02549173076596687
>>> math.pow(1-math.exp(-8*64/1024),8)
0.02549173076596687

为了保证98%的准确率，所以要不断的扩充 m

• 字符串存 ：16*16 = 256 B
• bloomfilter ：256Bit = 32B
  存储为原来的为1/8

生成一个新的Bloom FIlter

• 两个都写，读两个都读，都为True则True
• 只写新的，读取时都读，有一个Trure则True

转载：
https://zhuanlan.zhihu.com/p/43263751