布隆过滤器误判率计算
Swift

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

假设布隆过滤器的长度为$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,则会产生误判,其概率为:

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

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


参考