布隆过滤器 (Bloom Filter) 的错误率与最佳函数个数推导

本文旨在对布隆过滤器的错误率与最佳函数个数公式进行推导。

布隆过滤器的错误率推导

设 Hash 函数个数: ， 布隆过滤器大小: ( )， 流上的元素个数为:

可得 Hash 函数 应用于元素 后，布隆过滤器上某位 是 1 的概率：

易得， 是 0 的概率：

当所有 Hash 函数应用于元素 ， 依旧是 0 的概率：

当向布隆过滤器添加了 流上的 个元素后， 为 0 的概率为：

可推得， 为 1 的概率为：

结合：

可得到：

故 有近似值:

因此误报的可能性为:

寻找函数个数的最优值

根据：

令 ，可知：

令 ，有：

若存在 ， 则 的导数为：

求解得：

同时，由于：

由 可证 , 因此，当 时，存在：

化简得

当且仅当 时，上式成立，因此可知：

由于 , 因此：

可得：

此时误报概率 为：