布隆过滤器误判率

本文目录导读：

1. 什么是布隆过滤器的误判率？
2. 误判率是如何产生的？
3. 误判率的计算公式
4. 如何控制误判率？
5. 已知 $n$ 和 $p$，如何设计最佳过滤器？
6. 常见误判率与空间占比速查表

布隆过滤器（Bloom Filter）是一种空间效率很高的概率型数据结构,用于判断一个元素是否在集合中。

它的核心特性是：宁可错杀一千（误判存在），绝不放过一个（绝不可能漏报）。

误判率”（False Positive Rate，假阳性率）,以下是详细的解释和计算方法：

什么是布隆过滤器的误判率？

• 定义：查询一个不在集合中的元素时，布隆过滤器错误地告诉你“它在集合中”的概率。
• 特点：
  • 不会漏判：如果元素确实在集合中，过滤器会100% 返回“存在”。
  • 可能会误判：如果元素不在集合中，过滤器以一定的概率返回“存在”，这就是误判率 $p$。

误判率是如何产生的？

布隆过滤器内部使用一个位数组（bit array）和多个哈希函数。

1. 添加元素时，通过 $k$ 个哈希函数计算出 $k$ 个位置，将这些位置的值设为 1。
2. 查询元素时，检查这 $k$ 个位置是否全部为 1，如果全部为 1,则认为元素存在。

误判来源：因为哈希函数会碰撞，且不同元素可以设置相同的位，导致多个不存在的元素，它们对应的哈希位置恰好都被其他元素设置为 1。

误判率的计算公式

误判率 $p$ 取决于三个参数：

• $n$：已经插入的元素个数
• $m$：位数组的长度（位数）
• $k$：哈希函数的个数

最优误判率 $p$ 的公式（假设哈希函数完美随机分布）：

$$p \approx \left(1 - e^{-\frac{kn}{m}}\right)^k$$

这个公式的推导思路是：

1. 某一位在插入 $n$ 个元素后未被设置为 1 的概率为 $(1 - \frac{1}{m})^{kn} \approx e^{-\frac{kn}{m}}$。
2. 某一位被设为 1 的概率为 $1 - e^{-\frac{kn}{m}}$。
3. 查询时，需要 $k$ 个位全为 1，因此概率为 $(1 - e^{-\frac{kn}{m}})^k$。

如何控制误判率？

误判率可以通过调整参数来控制，核心思路是用更大的空间（$m$）来换取更低的误判率。

已知 $n$ 和 $p$，如何设计最佳过滤器？

如果你预先知道要存储的最大元素数量 $n$ 和能接受的误判率 $p$,可以计算出最优参数：

步骤 1：计算所需的最小位数组长度 $m$

$$m = -\frac{n \ln p}{(\ln 2)^2}$$

• 数值例子：如果你要存储 1000 万个 元素，并希望误判率不超过 1% （即 $p = 0.01$）。
  • $\ln p = \ln(0.01) \approx -4.605$
  • $(\ln 2)^2 \approx 0.4805$
  • $m = -\frac{1000万 \times (-4.605)}{0.4805} \approx 9585万$ 位
  • 换算成内存：$9585万 / 8 \approx 1198万$ 字节 $\approx 11.4$ MB。

步骤 2：计算最优的哈希函数个数 $k$

$$k = \frac{m}{n} \ln 2$$

• 接上例：$k = \frac{9585万}{1000万} \times 0.693 \approx 0.9585 \times 0.693 \approx 6.64 \approx \mathbf{7}$

常见误判率与空间占比速查表

为了方便估计，有一个经典的经验公式：实际比特率 $m/n$ 与误判率 $p$ 的关系如下：

可以看到，每降低一个数量级的误判率，每个元素大约需要多占用 4.8 位（0.6 字节）的空间。

• 误判率是布隆过滤器无法避免的代价，这是它用“空间换准确性”的一种妥协。
• 你可以通过计算来精确控制它，根据预期的数据量 $n$ 和可接受的误判率 $p$，可以计算出最优的位数组长度 $m$ 和哈希函数个数 $k$。
• 在实际应用中，$n$ 是动态增长的，误判率会随着元素插入而逐渐升高，需要预留足够的空间，并在误判率过高前对过滤器进行扩容（即创建一个新的更大的布隆过滤器，将旧数据迁移过去）。