布隆过滤器 从位数组到误判概率与精确枚举

数据库索引回答怎样定位候选记录。有时还可以在昂贵的读取之前加一层更便宜的预检：如果某个键肯定没出现过，就不必继续访问；如果它可能出现过，仍交给真实存储确认。

布隆过滤器用一段位数组换取这种单向判断，因此归入计算机基础的索引与概率数据结构方向。本篇讲清它的状态、不变量、误判概率和内存边界，再用一个足够小的模型检查常见近似到底省略了什么。

先看位数组

插入只置位，不保存键和完整记录。

再看单向错误

阴性可以排除，阳性仍要回查。

最后核对概率

理想哈希模型、近似公式与实测计数分开解释。

共享位节省空间，也让阳性不再等于命中。 A、B、C 的哈希位置为手工指定的教学映射，不是下方具体字符串的 BLAKE2 摘要结果。查看原图

状态与两种操作

准备 m 个初始为零的位和 k 个确定性位置函数 h_i(key)∈{0,…,m−1}。插入时把这 k 个位置置为 1；查询时检查这 k 位，任意一位为 0 就返回“不存在”，全部为 1 就返回“可能存在”。

同一个键的多个位置可以重合，不额外要求互不相同。真实应用还必须固定字节编码、位置函数及参数，保证插入和查询对同一个键的解释完全一致。

Bloom 原始论文讨论了允许一定错误的空间时间权衡；Redis 官方说明也强调了容量与误判率的关系。本文实现是固定大小的基本版本，没有实现 Redis 的自动扩展。

不漏掉已插入键，需要哪些条件

对一个已插入键，它的所有位置在插入完成后都为 1。若后续操作只会置 1，不清位，查询使用同样的位置函数，则这些位仍全部为 1。因此不会把这个键判断为“不存在”。

这个证明不需要哈希函数独立或均匀；概率假设用于估计误判率，不用于上述单调不变量。但证明依赖插入已完成、位未丢失、编码与参数一致。位写入并发丢失、数据损坏、加载了错误版本，都可能破坏前提。

对未插入键，对应位置可能被其他键碰巧全部置为 1，于是出现假阳性。过滤器没有保存完整键，不能仅凭一次阳性就返回业务记录、跳过权限验证或认定去重成功。

八个位怎样手算共享与误判

取 m=8、k=2，位下标从 0 开始。手工规定 A→[1,4]、B→[4,6]、C→[1,6]、D→[0,6]。

操作	涉及下标	为 1 的位集合	返回	真实成员关系
插入 A	1、4	{1,4}	—	A 已插入
插入 B	4、6	{1,4,6}	—	B 已插入
查询 A	1、4	{1,4,6}	可能存在	真阳性
查询 C	1、6	{1,4,6}	可能存在	假阳性
查询 D	0、6	{1,4,6}	不存在	正确排除

如果为了删除 A 而清除 1、4，B 所需的共享位 4 也变成 0，随后 B 就会得到错误阴性。这说明基本位数组不能这样删除；计数布隆过滤器等变体需要另外的状态、容量与更新约定，不是加一个清位函数就完成了。

常见误判公式从哪里来

下面先建立理想模型：n 个不同键的 kn 次置位独立、均匀、有放回；一个未插入键的 k 次查询位置也独立均匀，并独立于插入过程。

单个位经过 kn 次置位后仍为零的概率为 (1−1/m)^(kn)，所以为 1 的概率 q=1−(1−1/m)^(kn)。如果进一步近似把查询所需各位的占用看作独立，就得到 q^k。m 较大时再用指数近似：

f ≈ (1 − exp(−kn/m))^k
k 的连续近似最优值 ≈ (m/n) ln 2
m ≈ −n ln(f) / (ln 2)²

选择 k 时还要整数化并考虑哈希成本；n=0 应单独处理。公式用于规划，不是每次数据集的误判比例保证。相同键的重复插入不会增加置位集合，不能把重复操作数直接当成 n。

四个位的精确模型揭示什么

取 m=4、k=2、n=2。四次插入位置有 4⁴=256 种等概率分配，设最后有 B 位为 1。给定 B，未插入键的两次独立查询同时落在已占用位的概率是 (B/4)²，所以精确误判率为 E[(B/4)²]，而不是 (E[B]/4)²。

占用位数 B	插入分配数	条件误判率
1	4	1/16
2	84	4/16
3	144	9/16
4	24	16/16

加权得到 (4×1+84×4+144×9+24×16)/(256×16)=505/1024，约 0.493164。把位占用当成独立会得到 (175/256)²，约 0.467300；再做指数近似则约 0.399576。

差异既来自有限 m 的指数近似，也来自忽略占用随机性。这里的精确枚举仍是理想独立哈希模型，不是证明某个具体摘要实现的概率分布正好如此。

完整标准库实现

使用 bytearray 实际存位，使用 BLAKE2b 的固定输入格式构造可重复的位置。UTF-8 编码不做 Unicode 归一化；如果业务需要把不同写法当成同一键，应在插入和查询前执行同一规则。

Python hashlib 官方文档给出了 BLAKE2 参数和字节输入要求。这里用摘要位置作为工程构造，没有把不同域的摘要当成已证明独立的随机函数，也没有用 Python 内置 hash 的进程随机化结果持久化位置。

import hashlib
import json
import math
from collections import defaultdict
from fractions import Fraction


def integer(value, low, high, name):
    if type(value) is not int or not low <= value <= high:
        raise ValueError(name + " outside supported range")
    return value


class Bloom:
    def __init__(self, bits=2048, hashes=4):
        self.m = integer(bits, 1, 10000000, "bits")
        self.k = integer(hashes, 1, 16, "hashes")
        self.data = bytearray((self.m+7)//8)

    def indices(self, key):
        if not isinstance(key, str):
            raise ValueError("key must be text")
        encoded = key.encode("utf-8")
        if len(encoded) > 1000000:
            raise ValueError("teaching implementation limits key length")
        prefix = len(encoded).to_bytes(8, "big")
        return [int.from_bytes(hashlib.blake2b(
                    i.to_bytes(2, "big")+prefix+encoded,
                    digest_size=8, person=b"esbloom-v1").digest(), "big") % self.m
                for i in range(self.k)]

    def add(self, key):
        for bit in self.indices(key):
            self.data[bit//8] |= 1 << (bit % 8)

    def may_contain(self, key):
        return all(self.data[bit//8] & (1 << (bit % 8))
                   for bit in self.indices(key))

    def occupied(self):
        return sum(byte.bit_count() for byte in self.data)


def exact_model(m=4, k=2, n=2):
    m, k, n = integer(m, 1, 16, "m"), integer(k, 1, 8, "k"), integer(n, 0, 8, "n")
    if n*k > 32:
        raise ValueError("exact teaching model limits placement count")
    counts = {0: 1}
    for _ in range(n*k):
        nxt = defaultdict(int)
        for occupied, count in counts.items():
            if occupied:
                nxt[occupied] += count*occupied
            if occupied < m:
                nxt[occupied+1] += count*(m-occupied)
        counts = dict(nxt)
    numerator = sum(count*occupied**k for occupied, count in counts.items())
    return {"counts": counts, "false_positive": str(Fraction(numerator, m**(n*k+k)))}


def experiment():
    bloom = Bloom()
    inserted = ["item:"+str(i) for i in range(200)]
    for key in inserted:
        bloom.add(key)
    probes = ["probe:"+str(i) for i in range(20000)]
    false_positives = sum(bloom.may_contain(key) for key in probes)
    return {"bits": bloom.m, "hashes": bloom.k, "bit_array_bytes": len(bloom.data),
            "occupied": bloom.occupied(),
            "false_negatives": sum(not bloom.may_contain(key) for key in inserted),
            "negative_queries": len(probes), "false_positives": false_positives,
            "empirical_rate": false_positives/len(probes),
            "exponential_model": (-math.expm1(-bloom.k*len(inserted)/bloom.m))**bloom.k}


if __name__ == "__main__":
    print(json.dumps({"toy": exact_model(), "experiment": experiment()}))

位数组本体为 ceil(m/8) 字节，Python 对象和容器还有额外开销。该实现每次插入或查询计算 k 个摘要；若键长为 L，时间为 O(kL)，位操作为 O(k)。除输入编码与摘要临时空间外，存储主体为 O(m) 位，不包含权威数据。精确模型的循环为 O(nkm) 次整数运算，大整数的位数还会影响单次成本。

实验应该怎样解释

代码插入 200 个不同键，用另一套前缀构造 20000 个确定不存在的查询，分别报告错误阴性和假阳性。它没有把过滤器的阳性直接当成真实命中；256 字节只指 2048 位的数组本体，不包括字符串、实验列表或完整存储。

实际运行时，661 位被置一，已插入键的错误阴性为 0；20000 个阴性查询中有 209 个假阳性，比例为 1.045%，指数模型近似为 1.0934%。这是指定字符串集合上的确定性计数，不是任意未来查询分布的覆盖保证。

验证程序 tests/verify-bloom-article.cjs 检查 360 个随机尺寸/哈希数组合、14400 个阴性查询及逐位独立参考；对 54 个小型理想模型直接枚举 140210 种插入与查询联合位置组合，核对占用递推的精确概率。另检查重复插入、满位数组、共享位删除反例、不同 PYTHONHASHSEED 下的稳定位置及 16 类非法输入。

位数组逐渐填满时，假阳性会越来越常见，极限情况下所有查询都返回“可能存在”。即使最终没有错误阴性，也不能据此说它的排除效率仍然有用。

使用边界	需要注意
阳性命中	回查权威存储，不能作为权限或真实性依据
删除和到期	基本实现没有删除，清共享位会制造错误阴性
持久化与迁移	固定 m、k、摘要格式、编码和版本；本文没有序列化协议
并发更新	读改写丢失会破坏只增不删不变量，需要同步策略
实测比例	依赖键和查询分布，不等于任意请求上的保证
大规模增长	重新规划容量或采用有明确协议的扩展方案

自检：查询 C 的两个位置都是 1，为什么仍不能确认 C 已插入？

位数组保存的是许多键的联合置位结果，不保存这些位属于哪个键。手算例中的 1、6 分别来自 A、B，组合起来仍可让未插入的 C 通过。

把它放回数据库索引的读取路径：布隆预检可以减少确定无成员时的后续工作，但剩余候选还需要正确的查询与结果验证。减少读取次数和确认真实成员关系，是两项需要分别核对的工作。