布隆过滤器的假阳性率数学推导 布隆过滤器的假阳性率（False Positive Rate）是指当查询一个不存在于集合中的元素时，布隆过滤器错误地判断为“可能存在”的概率。下面我们逐步推导这一概率的数学表达式。 1. 布隆过滤器基础设定 位数组长度为 \( m \)（即共有 \( m \) 个比特位）。 使用 \( k \) 个独立的哈希函数，每个哈希函数将元素均匀映射到 \( [ 0, m-1 ] \) 的某个位置。 集合中共有 \( n \) 个元素插入到布隆过滤器中。 2. 单个比特位未被设置的概率 对于某一个特定的比特位，在一次哈希操作中被设置（即变为1）的概率为 \( \frac{1}{m} \)，未被设置的概率为 \( 1 - \frac{1}{m} \)。 由于有 \( k \) 个哈希函数，但 一个元素插入时 ，这个特定的比特位未被任意一个哈希函数选中的概率为： \[ \left(1 - \frac{1}{m}\right)^k \] 现在考虑插入 \( n \) 个元素，这个比特位仍然为 0 的概率（即所有元素的 \( k \) 次哈希都未命中该位）： \[ \left(1 - \frac{1}{m}\right)^{kn} \] 当 \( m \) 较大时，利用近似公式 \( \lim_ {m \to \infty} \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m} \)，可得： \[ p_ 0 \approx e^{-kn/m} \] 其中 \( p_ 0 \) 表示一个比特位在插入 \( n \) 个元素后仍为 0 的概率。 3. 假阳性发生的条件 当查询一个不存在的新元素时，布隆过滤器会检查该元素的 \( k \) 个哈希位置。 仅当这 \( k \) 个位置都为 1 ，才会错误地判断为“可能存在”。 一个比特位为 1 的概率为 \( 1 - p_ 0 \approx 1 - e^{-kn/m} \)。 由于哈希函数是独立的，\( k \) 个位置全为 1 的概率为： \[ \left(1 - p_ 0\right)^k \approx \left(1 - e^{-kn/m}\right)^k \] 这就是假阳性率的近似表达式。 4. 进一步优化表达式 令 \( c = \frac{m}{n} \) 表示每个元素分配的比特数，则 \( \frac{kn}{m} = \frac{k}{c} \)。 假阳性率可写为： \[ f \approx \left(1 - e^{-k/c}\right)^k \] 对固定的 \( c \)，可以通过求导找到使 \( f \) 最小的 \( k \)。 取对数后求导（或直接对 \( f \) 优化），可得当 \( k = c \ln 2 \) 时，假阳性率最小。 此时最小假阳性率为： \[ f_ {\min} \approx \left(0.6185\right)^{c} = \left(\frac{1}{2}\right)^{k} \quad (\text{当 } k = c \ln 2) \] 更精确地，代入 \( k = c \ln 2 \) 到 \( f \) 中： \[ f \approx \left(1 - e^{-\ln 2}\right)^{c \ln 2} = \left(1 - \frac{1}{2}\right)^{c \ln 2} = \left(\frac{1}{2}\right)^{c \ln 2} = 2^{-c \ln 2} = \left(\frac{1}{2}\right)^{\ln 2 \cdot c} \] 常用形式是 \( f \approx (0.6185)^c \)，因为 \( 2^{-\ln 2} = e^{-\ln 2 \cdot \ln 2} \) 不对，实际上： \[ k = c \ln 2 \implies f = \left(1 - e^{-k/c}\right)^k = \left(1 - e^{-\ln 2}\right)^{c \ln 2} = \left(\frac12\right)^{c \ln 2} \] 而 \( \left(\frac12\right)^{\ln 2} \approx 0.6185 \)，所以 \( f \approx (0.6185)^c \)。 5. 总结 布隆过滤器的假阳性率公式为： \[ f \approx \left(1 - e^{-kn/m}\right)^k \] 通过调整 \( k \) 和 \( m \)，可以在空间效率和误判率之间进行权衡。