约 12 分钟6 张卡

布隆过滤器

布隆过滤器（Bloom filter）是一种节省空间的近似成员查询结构。它能回答“这个元素一定没有加入过”或“这个元素可能加入过”，但不保存完整元素，也不能凭肯定结果确认元素存在。

它适合放在昂贵查询前，提前排除一部分无效请求。面试中需要讲清的不只是位数组和多个哈希，还包括误判发生在哪个方向、容量不足有什么影响，以及过滤器为什么不能独自决定唯一性或业务正确性。

1. 面试核心

先记住这几条，再读正文

加入元素时，按多个哈希位置把对应位设为 1；查询时，只要其中一位是 0 就能排除，全为 1 则只能说可能存在。卡 · 位数组与多哈希
假阳性是未加入的元素通过检查，原因是不同元素共享位。对于已经完整加入的元素，只要位没有丢失、读写映射一致且可见，普通布隆过滤器不会给出否定结果。卡 · 假阳性与没有假阴性的条件
误判率取决于位数、不同元素数、哈希次数及分布。位数组固定时，持续加入新元素会使更多位变成 1，过滤效果逐渐下降；哈希次数并非越多越好。卡 · 容量与哈希次数
普通布隆过滤器不能通过清零来安全删除元素，因为清掉的位可能还被其他元素使用。计数变体也要求正确匹配加入与删除，不能凭“可能存在”就减计数。卡 · 普通过滤器不能直接清位
扩容不能只复制旧位并补零，改变容量通常也改变位置映射。重建需要原始元素或可靠数据源，还要覆盖构建期间的新增数据。卡 · 容量增长不能只补零
布隆过滤器不是唯一约束或原子去重操作。肯定结果可能误判，否定结果也不会替调用者占住一个尚不存在的键。卡 · 适用场景与唯一约束

2. 位数组与多哈希

卡 · 布隆过滤器怎样判断元素是否存在，为什么会误判？

位数组是由 0 和 1 组成的数组，每一位只表示一个标记。设数组有 m 位，初始全部为 0；对每个元素，使用 k 个稳定的映射得到范围 [0, m) 内的位置。

加入 x 时，把 h₁(x) 到 hₖ(x) 对应的位都设为 1。查询 x 时计算相同位置：

只要找到一位为 0，就返回“不存在于已加入集合”。
如果检查的位置全为 1，就返回“可能存在”。

位置可以重合。某一位已经是 1 时，再设为 1 不会改变它。相同元素采用相同映射重复加入，也不会继续设置新的位置。

下面用 8 位数组、两个位置说明共享位的结果。位置值是便于推导的示意，不是推荐的哈希函数：

元素	两个位置	实际是否加入
`a`	1、4	是
`b`	4、7	是
`c`	1、7	否
`d`	0、7	否

加入 a 和 b 后，1、4、7 三位为 1。查询 d 能看到第 0 位为 0，正确排除；查询 c 却会看到两位都是 1，所以返回“可能存在”。过滤器只看到位的合并结果，不知道这些位分别由谁设置。

这与哈希表不同。哈希表保留键，发生冲突后仍比较键是否相等；布隆过滤器省略了这一步所需的信息，用允许部分误判换取更小的空间。

3. 假阳性与没有假阴性的条件

卡 · 布隆过滤器怎样判断元素是否存在，为什么会误判？卡 · 布隆过滤器没有假阴性，为什么系统仍可能拒绝真实存在的数据？卡 · 如何估算布隆过滤器容量，哈希次数为什么不是越多越好？

假阳性（false positive）是元素没有加入，却被判断为“可能存在”。假阴性（false negative）是元素已经加入，却被判断为不存在。

标准的只增不删布隆过滤器没有假阴性，其依据很直接：加入 x 时已把它会查询的全部位置设为 1，后续加入只会继续置 1，不会把这些位改回 0。这个结论不要求哈希分布完美均匀；分布差首先影响的是假阳性和过滤效果。

但上述推导依赖具体条件：

加入操作已经完成，查询能看到它写入的全部位。
加入与查询采用相同的编码、规范化规则、哈希算法、种子及容量。
没有错误清位、并发更新丢失、损坏或加载不完整的状态。

例如把同一个业务 ID 一次编码为 "0012"、另一次编码为 "12"，过滤器实际收到的是两个键。并发写入同一个机器字时，如果用不安全的读后改写覆盖了另一线程设置的位，也会破坏只增不减的前提。实际库需要提供相应的原子位操作或同步保证。

此外，“没有加入过滤器”和“数据库里不存在”是两个判断。数据库新增成功而过滤器尚未更新时，过滤器可以正确回答“没加入过”，业务却错误地拒绝一条真实记录。将否定结果用于拦截前，必须保证过滤器覆盖了需要查询的数据；具体新增同步与切换方案见缓存穿透中的过滤器维护。

3.1 误判率的分母

通常所说的假阳性率，是实际不在集合中的查询里，有多少比例被判断为可能存在。它不是所有查询的错误比例，也不是“返回可能存在时，有多大概率是真的”。

假设 100000 次查询中，1000 次查询已加入的元素，99000 次查询未加入的元素。若后者的假阳性率约为 1%，就约有 990 次误判，加上 1000 次真实命中，共约 1990 次肯定结果。肯定结果中，约一半仍不是真实成员。

这个计算只说明分母不同。实际结果还取决于查询分布；在位状态和映射不变时，重复查询同一个假阳性键会重复得到肯定结果，不是每次重新独立抽取一个“1% 概率”。

4. 容量与哈希次数

卡 · 如何估算布隆过滤器容量，哈希次数为什么不是越多越好？

设计容量时先确定预计加入的不同元素数 n、可用位数 m 与哈希位置数 k。在只增不删且映射不变的前提下，同一个键重复加入不增加有效负载。

在独立、均匀的理想哈希模型中，经过 kn 次位置选择后，某一位仍为 0 的概率是 (1 - 1/m)^(kn)，大数组下可近似为 e^(-kn/m)。进一步以位占用比例作近似，可以得到常用的假阳性率估算：

p ≈ (1 - e^(-kn/m))^k

这不是任意真实哈希函数和任意查询输入的精确保证。有限位数组的占用存在相关性，实际映射、位置生成策略和查询分布也会影响结果；尤其不能用理想模型直接承诺对抗性输入的误判上限。

4.1 参数之间的取舍

固定 n 和 k，增加 m 会减少位置拥挤，但占用更多内存。
固定 m 和 k，增加不同元素数 n 会提高位占用和误判率。
增加 k 会检查更多位置，同时也会为每个新元素设置更多位，所以存在取舍；过大的 k 会加快填满位数组，并增加计算与访问成本。

在上述近似模型下，常用参数估算为：

k ≈ (m/n) × ln(2)
m ≈ -n × ln(p) / (ln(2))²

ln 是自然对数，实际 k 需要取整数并重新检查估计值。例如预计 100 万个不同键、目标约 1% 的假阳性率，估算需要约 959 万位，位数组约 1.14 MiB，k 接近 7。这里还没有计算对象、元数据或对齐开销。

若不改变这组容量和 k=7，却加入约 200 万个不同键，同一模型的估算会升到约 15.7%。这组数字是参数模型的计算结果，不是某个实现已经测出的精确概率。

4.2 多个位置不等于多次昂贵哈希

多个位置可以由不同哈希函数生成，也可以采用经过分析的组合方案。Kirsch 和 Mitzenmacher 对利用两个基础哈希生成多个位置给出了渐近分析，说明不一定要为每个位置重新执行一遍完整哈希。

但不能因此随意复制同一个位置，或把任意两个相关整数当成独立均匀哈希。具体实现需要检查位置分布和步长等条件；“做了 k 次检查”本身不能证明满足理想公式的假设。

5. 删除、扩容与重建

卡 · 普通布隆过滤器为什么不能直接删除，计数变体是否可以随意删除？卡 · 容量不足时，为什么不能把位数组扩大一倍并直接复制旧位？

5.1 普通过滤器不能直接清位

在前面的例子中，a 使用 1、4 两位，b 使用 4、7 两位。删除 a 时若把 1、4 清零，仍然存在的 b 就会因为第 4 位为 0 而被排除，产生假阴性。

如果只从真实数据源删除 a，保留过滤器中的位，过滤器可能继续放行 a 的查询，但不会因此破坏其他已加入键的位。这会增加无效查询，需要按业务选择定期重建或支持删除的结构。

计数布隆过滤器用计数器替代单个位：加入时增加相应计数，删除时减少相应计数，查询检查计数是否非零。它需要额外空间，并要求计数不溢出、加入与删除次数正确匹配。

“可能存在”不能作为执行删除的充分证据。若一个没加入过的元素只是碰巧通过检查，减去它对应的计数就可能伤及其他元素；重复删除、计数溢出或不一致的重复加入策略也会破坏保证。删除必须有可信的成员或操作记录作为依据。

5.2 容量增长不能只补零

把位数组从 m 扩到 2m 后，原来按 % m 得到的位置通常与 % (2m) 不同。只复制旧位并在末尾补零，查询就可能检查到尚未设置的新位置，漏掉原本加入的键。位数组也没有保存原始键，不能从中反推出所有元素重新散列。

一种做法是从可靠数据源构建更大的过滤器，再补齐构建期间的新增数据，完成切换。另一种做法是保留旧过滤器，让新数据进入新过滤器，查询检查相关的多个过滤器；这样需要承担更多检查，并为整体假阳性率分配预算，不能默认每层 1% 就等于整体 1%。

两个过滤器做按位或，可以合并它们代表的集合，但前提是容量、位置算法、种子和键编码等完全兼容。合并也会增加位占用；它不是把两个小过滤器自动变成一个低误判的大过滤器。

6. 适用场景与唯一约束

卡 · 为什么布隆过滤器不能替代数据库唯一约束或精确去重？

布隆过滤器适合允许多做一次确认、但希望提前排除大量无效候选的场景。例如：

缓存查询前过滤不存在的 ID，肯定结果继续查缓存或数据库。
LSM 树点查时，跳过不可能包含该键的候选文件。
先过滤大量候选，再用精确集合或数据源确认需要保留的结果。

它不提供完整成员列表、键值内容或范围顺序，也不能直接替代精确集合。若把“可能重复”的数据直接丢弃，就要接受假阳性带来的误删；要求一条不丢的去重流程必须保留精确确认。

6.1 为什么不能代替唯一约束

唯一约束要求同一个业务键只能成功建立一次，而布隆过滤器既可能误判，也不提供“判断后占有”这一原子操作。

顺序	请求 A	请求 B
1	查询 `order:42`，结果为不存在	尚未执行
2	尚未完成插入	查询同一个键，也得到不存在
3	插入订单并更新过滤器	继续执行自己已经通过的插入

即使这两次否定判断当时都正确，也不能阻止后续重复写入。反过来，肯定判断可能是假阳性，不能直接拒绝一条合法的新记录。

要求唯一性时，应由数据库唯一约束或等价的原子协调机制决定哪个写入成功，并正确处理冲突。过滤器只能减少部分前置查询；最终写入仍需经过可靠约束，具体规则见数据约束。

7. 可复现的最小实现

下面用 Python 3 的 bytearray 保存位，并用固定前缀与 SHA-256 生成位置。它只展示单线程、只增不删的机制，没有实现并发更新、持久化或在线扩容，也不把这些摘要输出当作数学上已证明独立的哈希函数。

from hashlib import sha256


class BloomFilter:
    def __init__(self, m: int, k: int):
        if m <= 0 or k <= 0:
            raise ValueError("m and k must be positive")
        self.m = m
        self.k = k
        self.bits = bytearray((m + 7) // 8)

    def _positions(self, key: str):
        data = key.encode("utf-8")
        for i in range(self.k):
            digest = sha256(i.to_bytes(4, "big") + data).digest()
            yield int.from_bytes(digest, "big") % self.m

    def add(self, key: str):
        for pos in self._positions(key):
            self.bits[pos // 8] |= 1 << (pos % 8)

    def might_contain(self, key: str) -> bool:
        return all(
            self.bits[pos // 8] & (1 << (pos % 8))
            for pos in self._positions(key)
        )


f = BloomFilter(m=32, k=3)
inserted = [f"key:{i}" for i in range(8)]
for key in inserted:
    f.add(key)

before = bytes(f.bits)
f.add("key:0")
assert bytes(f.bits) == before
assert all(f.might_contain(key) for key in inserted)

false_positives = [
    f"query:{i}" for i in range(100)
    if f.might_contain(f"query:{i}")
]
print(f.bits.hex())
print(false_positives[0], len(false_positives))