编程面试：实现一个 Bloom Filter

题干与适用场景

请实现一个 Bloom Filter，提供 add(value) 和 mightContain(value)。它用于在昂贵查询前做预过滤：返回“不存在”时必须可信，返回“可能存在”时允许再查一次数据库。回答要覆盖 n、p、m、k 的关系，以及删除、扩容、并发和测试。题目适合考察数据结构、缓存和后端基础。

面试官考察点

语义是否准确

标准 Bloom Filter 允许 false positive，不允许 false negative。mightContain 的名字应提醒调用方：true 不是存在证明。

参数是否可解释

位数组长度 m 和哈希数量 k 决定空间、速度和误判率。应先问预计容量和可接受 p，再给出公式，而不是随意选常数。

边界是否完整

候选人需要主动说明标准结构不能安全删除单个元素，装满后误判率会上升，扩容需要重建或分层结构。

回答前需要澄清的问题

• 预计插入多少个元素，目标误判率 p 是多少？
• 值是否可序列化为稳定字节串，跨进程哈希是否要保持一致？
• 过滤器是否只追加，还是必须支持删除和更新？
• 内存预算、查询延迟和并发写入上限是多少？
• 装满后是拒绝写入、重建，还是切换到新的分层过滤器？
• false positive 带来的后端查询成本如何监控？

30 秒回答框架

“我会用 m 位数组和 k 个独立性足够的哈希位置。add 把 k 个位置置 1；查询时只要一个位置为 0，就能断言不存在，否则返回可能存在。给定 n 和 p，m=-n ln(p)/(ln2)^2，k=(m/n)ln2。标准结构不能删除，容量变化要重建或分层；我会测试插入必为 true、缺失样本的误判率和并发读写约束。”

分步骤深入解答

先写出不变量与接口

位数组的每一位初始为 0。对每个值，稳定哈希函数产生 k 个索引；插入只会把这些索引设为 1。只要查询遇到 0，就能证明该值从未被这组哈希写入。

计算 m 与 k

目标是预计 n 个元素、误判率 p。近似公式为 m = -n ln(p) / (ln(2)^2)，k = (m/n) ln(2)。例如 n=1,000,000、p=1% 时，m 约 9.6M bits（约 1.14 MiB），k 约 7。

处理哈希与位操作

实现可用双重哈希：h_i(x) = h1(x) + i*h2(x)，再对 m 取模，避免维护 k 套完整哈希函数。必须固定字节编码、端序和种子；跨版本改变这些约定会让旧过滤器失效。

说明删除与扩容

单个位可能由多个值共享，直接清零会制造 false negative。因此标准 Bloom Filter 不支持安全删除。需要删除时可采用 Counting Bloom Filter，但每个桶占更多空间。容量增长后应重建更大的过滤器，或用多个按容量分层的过滤器。

处理并发与生命周期

并发读通常安全；并发写至少要保证置位操作不会丢失，分片位数组、原子 OR 或写锁都可选。过滤器应与其容量、哈希种子和版本一起持久化，重启时不能悄悄换参数。

伪代码

~~~text add(x): for i in 0..k-1: bits[index(hash1(x), hash2(x), i)] = 1

mightContain(x): for i in 0..k-1: if bits[index(hash1(x), hash2(x), i)] == 0: return false return true ~~~

复杂度与验证

每次 add 与查询访问 k 个位置，时间是 O(k)，额外空间是 O(m)。测试至少包括：所有已插入值都返回 true；随机未插入样本统计 false positive；n 接近容量时观察误判率；哈希种子、空过滤器、重复插入和并发写入分别验证。

高质量示范回答

“Bloom Filter 是一个概率型成员预过滤器。我会维护 m 位数组和 k 个位置函数。插入时把 k 位设为 1；查询时出现任意 0 就返回 false，否则返回 true，但把 true 解释为‘可能存在’，交给后端存储做最终确认。m 与 k 根据 n 和 p 计算，n=100 万、p=1% 时约需 9.6M bits、7 个哈希位置。标准版本不能删除，因为共享位无法知道由谁设置；删除需求用 Counting Bloom Filter，容量增长则重建或分层。实现会固定编码与哈希种子，测试已插入值不漏报并测量缺失样本的误判率。”

常见错误

把 true 当成存在证明

true 只表示所有对应位都为 1，其他值也可能碰巧置过这些位。调用方仍需访问权威数据源。

用一个哈希函数

单哈希会让位分布和误判率偏离设计目标。可用双重哈希生成 k 个位置，并说明种子和碰撞假设。

直接清除删除值的位

共享位被清零会让其他已插入值返回 false。删除必须改用计数桶或重建过滤器。

忽略容量饱和

持续插入会让更多位变成 1，误判率上升。应记录元素估计量和置位比例，在阈值前扩容。

只测成功路径

没有缺失样本、边界容量和重复插入测试，就无法验证误判率和参数选择。

追问及应对

为什么不能保证 false positive 为零？

不同值可能映射到同一组位；有限位数组必然存在碰撞。空间越大、k 越合适，误判率越低但成本越高。

什么时候用 Cuckoo Filter？

需要删除、较高查询灵活性或希望保存指纹时可比较 Cuckoo Filter；应按内存、写入和删除需求基准测试，不凭名称选择。

如何做持久化？

保存位数组、m、k、哈希算法、种子、编码版本和容量估计。加载时校验版本，避免不同参数读取同一位数组。

如何监控质量？

统计后端确认的 false positive、置位比例、估计元素数、查询延迟和重建次数；超过阈值就扩容或重建。

误判率公式的前提是什么？

公式假设哈希分布近似均匀、插入量接近 n 且位置之间独立性足够。真实数据要用抽样实验校准。

多线程如何避免写丢失？

位数组采用原子置位或分片锁；读路径要看到完整写入。若允许最终一致，可把写入批量合并后发布新快照。