Bloom Filter
2020-04-07 本文已影响0人
sealwang24
概率计算：
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
