Bloom Filter Variant

基础布隆过滤器中，不同哈希函数需要修改同一个位图，这导致：

于是 2004 年提出 布隆过滤器变体（Bloom Filter Variant） 以解决这两个问题。^[1]

原理

该布隆过滤器变体由两部份组成：

其中，M 位的位图被 k 等分，每个切片（slice）长度为 m，即 $m = \frac{M}{k}$ 。

与基础布隆过滤器不同的是，每个哈希函数独占一个 slice，不同哈希函数不会重复设置位。

这种变体更健壮，并且支持并发处理。

插入 1 个元素后，某一个位被置 1、置 0 的概率为 $\frac{1}{m}$ 、 $1 - \frac{1}{m}$

当插入 n 个元素后，某一位被置 0、置 1 的概率是 $(1 - \frac{1}{m})^{n}$ 、 $1 - (1 - \frac{1}{m})^{n}$

同样使用自然对数 e 的计算公式

lim_{x \to \infty} (1 - \frac{1}{x})^{- x} = e

插入 n 个元素后某一位被置 1 的概率可以简化为

p \approx 1 - e^{- \frac{n}{m}}

于是得到

n \approx - m l n (1 - p)

又由公式 $M = k m$ 和 $P = p^{k}$ ，我们推导出 $m = M \frac{l n (p)}{l n (P)}$ ，因此有

n \approx M \frac{l n (p) l n (1 - p)}{- l n (P)}

对于给定的纳伪率 $P$ 和位图大小 M，当 $p = \frac{1}{2}$ 时 n 取到最大值，此时能容纳最多的元素。 $p$ 代表一个 slice 的饱和程度，我们得知 slice 半饱和时最好，对于 $p = \frac{1}{2}$ 我们可以简化上面的公式为

n \approx M \frac{(l n (2)^{2})}{| l n (P) |}

$P$ 是给定的纳伪率，因此对于这个布隆过滤器变体而言，可以容纳的元素数量 n 是和位图大小 M 呈线性关系。

最后由 $P = p^{k}$ 和 $p = \frac{1}{2}$ 我们推导出最合适的哈希函数个数为

k = l o g_{2} \frac{1}{P}

首先获取/估算插入个数（ $n$ ），并固定可容忍的错误率（ $P$ ），然后通过公示计算：

F. Chang, W. chang Feng, K. Li, Approximate caches for packet classiﬁcation, in: Proc. of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (IN- FOCOM 2004), IEEE, 2004. ↩︎