预估布隆过滤器假阳性比率(false positive)

假定bloom filter有m位数，k个独立哈希函数，数据集合大小为n，数据可能的取值范围为l,则某一位是零的概率为：

P'=(1-1/m)^kn，这也是数组中零的个数的期望值。

则假阳性比率为：

rate ≈ (1-n/l) * (1-P')^k <= (1-P')^k

能预估假阳性比率就非常有用了，一般要确保较低的false positive，kn<m，至于取最合理的k这些相对不是那么使用。

原文写得不错：《Bloom Filter概念和原理》https://blog.csdn.net/jiaomeng/article/details/1495500

似乎bloom filter还有不少变种，counting bloom filter, dynamic bloom filter, spectral bloom filter，compressed bloom filter，没有看得太细(《Bloom Filter 系列改进之Counting Bloom Filter》：https://blog.csdn.net/zhaoyunxiang721/article/details/41123007)。

感觉上bloom filter用roaring bitmap实现也不错，可以减少内存开销。

counting bloom filter来说，增加一定存储去支持删除操作，可以看到位数一般不需要很多，超过位数的概率极低。那超过位数溢出之后就有假阴性问题吗，我估计是额外加个存储超出位数的来解决假阴性问题。