布隆过滤器误判率计算

记录一下布隆过滤器误判率的计算过程：

假设布隆过滤器的长度为$m$，需要插入的元素个数为$n$，哈希函数个数为$k$：

1. 先插入一个元素，某个位置没有被置为1的概率为：$1-\frac{1}{m}$
2. 经过$k$个哈希函数后，仍然没有被置为1的概率：$(1-\frac{1}{m})^k$
3. 插入了$n$个元素，仍然没有被置为1的概率：$(1-\frac{1}{m})^{kn}$；反之被置为1的概率：$1-(1-\frac{1}{m})^{kn}$
4. 现处于query阶段，来了一个元素待插入到过滤器中，如果插入的位置全部为1，则会产生误判，其概率为： $$(1-(1-\frac{1}{m})^{kn})^k$$

根据定理：$当\mathrm{x} \rightarrow 0时， (1+\mathrm{x})^{\frac{1}{x}} \sim e$，进一步推导：

$$\begin{align} (1-(1-\frac{1}{m})^{kn})^k &= \left(1-\left(1-\frac{1}{m}\right)^{-m \cdot \frac{-k n}{m}}\right)^k \\ &\sim \left(1-e^{-\frac{n k}{m}}\right)^k \end{align}$$

最终：$P_{error} = \left(1-e^{-\frac{n k}{m}}\right)^k$

---

参考

• 布隆过滤器概念及其公式推导