15.2 布隆过滤器

前置：哈希表与位运算。布隆过滤器回答的是概率成员关系：它可以证明“肯定没见过”，却只能说“可能见过”。

名单太大，答案可以有一点模糊

算法森林出口有一道名单检查。完整保存每个名字当然最准确，但守门人只想先挡住明显不在名单里的请求；少量“可能存在”的结果可以再去后端数据库确认。

布隆过滤器用 m 个 bit 和 k 个哈希位置保存集合摘要。加入元素时把对应位置设为 1；查询时只要看到一个 0，就能确定元素从未按同一规则加入。所有位置都是 1 时，可能是元素本身留下的，也可能是其他元素碰巧覆盖了这些位置。

因此，标准布隆过滤器有两条不对称的合同：

• 不会产生假阴性，前提是没有删除、位数组未损坏，编码和哈希配置保持一致；
• 允许假阳性，调用方必须准备二次确认。

守门人的 bit 名册

守门人不保存旅客的完整姓名，只在一面 bit 板上标出若干位置。查询时只要有一处仍为 0，就能肯定此人没登记；全部为 1，也只能把他送去权威名册复查。下面的实现把这条规则落到真实 bit，而不是用 set 偷换空间模型。

下面使用 bytearray，每个字节保存 8 个位置。接口只接受 bytes，让字符编码由调用方决定；跨服务使用时还要固定摘要算法、位数、哈希数量和序列化版本。

import hashlib


class BloomFilter:
    def __init__(self, bit_count, hash_count):
        if not isinstance(bit_count, int) or bit_count <= 0:
            raise ValueError("bit_count must be a positive integer")
        if not isinstance(hash_count, int) or hash_count <= 0:
            raise ValueError("hash_count must be a positive integer")
        self.bit_count = bit_count
        self.hash_count = hash_count
        self._bits = bytearray((bit_count + 7) // 8)

    def _positions(self, value):
        if not isinstance(value, bytes):
            raise TypeError("BloomFilter values must be bytes")
        digest = hashlib.blake2b(value, digest_size=16).digest()
        first = int.from_bytes(digest[:8], "little")
        second = int.from_bytes(digest[8:], "little") | 1
        for index in range(self.hash_count):
            yield (first + index * second) % self.bit_count

    def add(self, value):
        for position in self._positions(value):
            byte_index, bit_index = divmod(position, 8)
            self._bits[byte_index] |= 1 << bit_index

    def might_contain(self, value):
        for position in self._positions(value):
            byte_index, bit_index = divmod(position, 8)
            if not self._bits[byte_index] & (1 << bit_index):
                return False
        return True

    def byte_size(self):
        return len(self._bits)


if __name__ == "__main__":
    bloom = BloomFilter(bit_count=10_000, hash_count=7)
    inserted = [f"traveler-{index}".encode() for index in range(500)]
    for item in inserted:
        bloom.add(item)

    assert all(bloom.might_contain(item) for item in inserted)
    assert bloom.byte_size() == 1_250

    probes = [f"outsider-{index}".encode() for index in range(2_000)]
    false_positives = sum(bloom.might_contain(item) for item in probes)
    print("样本误报数：", false_positives)

最后的误报数只是这批探针上的测量，不是概率保证。测试真正必须断言的是：所有已插入元素都返回 True。

名册越满，守门人越容易放错人

bit 板的大小 m、登记人数 n 和每个名字落下的标记数 k 共同决定误报。多画几个标记起初有帮助，画得太多却会很快把整面板涂满。

插入 n 个元素后，在哈希近似独立且分布均匀的模型下，误报率约为：

p ≈ (1 - exp(-k * n / m))^k

给定 m 与预计的 n，使误报率较小的哈希数量约为：

k ≈ (m / n) * ln(2)

k 不是越大越好。哈希位置太少，bit 利用不足；太多则每次操作更贵，也会更快把位数组填满。容量规划应从预计元素数和可接受误报率反推，而不是随手写 k=3。

实际误报还受哈希质量、输入分布和容量超载影响。元素数显著超过设计值后，越来越多 bit 变成 1，过滤器会逐渐失去区分能力。生产系统通常要监控填充率，并安排分代或重建。

为什么不能随手擦掉一个标记

两个旅客可能在同一格留下标记。守门人若为删除其中一人而把那一格擦掉，另一人就会被错误地判成“不存在”。共享 bit 没有记录所有权。

一个 bit 可能由多个元素共同设为 1。删除某个元素时把这些 bit 清零，会连带制造其他元素的假阴性。计数布隆过滤器为每个位置保存计数，可以在相应限制下支持删除，但空间更大，还要处理计数溢出与并发更新。

若需求是精确成员关系、枚举元素或删除后立即严格一致，应使用集合、哈希表或其他索引。布隆过滤器适合放在权威数据源之前减少无效查询，不能替代权威数据。

复杂度与工程边界

操作	时间	空间或误差
加入	O(k)	设置 k 个 bit
查询	O(k)	可能假阳性
存储	O(m) bit	不保存原始元素

摘要计算还要读取输入字节，严格写法应加上 O(L)，其中 L 是输入长度。本页通过一个 128-bit 摘要做双重哈希以生成多个位置，这是常见的工程折中，不等于获得了 k 个数学上完全独立的哈希函数。

动手测量过滤器

1. 固定 n 与 m，改变 k，比较实测误报率与近似公式。
2. 让插入量超过设计值两倍，记录 bit 填充率与误报变化。
3. 给配置加入版本号，设计跨进程序列化格式。
4. 解释为什么 might_contain 返回 True 后仍要访问权威存储。
5. 设计一个会因直接清 bit 而制造假阴性的删除例子。

守门人的下一张地图

布隆过滤器用允许误报换取紧凑空间。下一篇的并查集不接受概率答案，它维护的是不断合并的连通分量；再下一篇用线段树处理区间聚合与单点更新。