题干与适用场景
请实现一个支持批量构建和 membership 查询的静态 Xor Filter。要求解释三段哈希布局、peeling 队列、指纹回填、构建失败重试、误判率和不支持原地删除的原因。
Xor Filter 是静态 approximate membership query 结构：它为每个 key 保存短指纹，查询时对三个位置的指纹做异或。论文显示它可在空间和查询速度上与 Bloom、Cuckoo Filter 竞争，但构建依赖随机哈希超图可剥离，失败时需要换种子重建；它适合批量生成后只读发布。
面试官考察点
面试官会看你能否正确构造三段数组、处理重复 key 和空集合；能否用度数队列剥离超图并按逆序回填；能否保持查询与构建使用同一指纹函数；能否计算误判概率、识别删除与动态更新限制；能否解释失败重试、内存占用和并发读取安全。
回答前需要澄清的问题
数据集与更新模型
确认 key 数量、是否允许重复、是否批量重建、更新延迟和是否必须支持删除。Xor Filter 默认面向静态集合，动态场景应比较 Cuckoo Filter 或分层重建。
误判与空间目标
确认可接受的 false positive rate、指纹位数、是否允许 false negative，以及查询吞吐和构建峰值内存的优先级。
key 与哈希边界
确认 key 是整数、字节串还是结构化对象，哈希种子如何持久化，跨语言实现是否要求字节序和归一化一致。
30 秒回答框架
“我把数组切成三段，每个 key 的三个哈希位置各落在一段，保存一个固定宽度指纹。构建时记录每个位置的度数和关联边，把度数为 1 的边放入队列并 peeling；若剩余边无法剥离就更换种子重建。按逆序取出边，用三个位置已有值异或出该边的指纹。查询重新计算三位置并异或，等于 key 指纹就返回可能存在。结构静态且允许误判，不提供原地删除。”
分步骤深入解答
第一步：定义布局和指纹
用两个独立的 64 位哈希结果派生三个位置和一个低位指纹。把表分为大小近似的三段，位置函数在各自段内取模；指纹不能为零时要统一约定零值处理，避免空槽与真实指纹混淆。
第二步：建立超图度数
每个 key 是连接三个槽位的超边。构建阶段为每个槽位记录度数和关联边列表，度数为 1 的槽位进入队列。重复 key 必须先去重或明确按同一个集合元素处理，否则同一超边会被重复计数。
第三步：执行 peeling
从队列取出度数为 1 的槽位，找到唯一关联边并记录“边、唯一槽位、其余两个槽位”。移除该边后递减三个槽位的度数，新的度数为 1 的槽位继续入队。若处理完队列仍有未移除边，说明本轮哈希图不可剥离。
第四步：逆序回填指纹
按照 peeling 记录的逆序处理每条边。目标槽位的值设为 key 指纹与另外两个槽位当前值的异或。这样三槽位异或后恰好得到该 key 指纹；尚未写入的槽位按零值参与计算。
第五步：实现查询
查询使用与构建相同的种子、位置函数和指纹函数，读取三段槽位并异或。结果相等只能说明“可能存在”，不能证明 key 在集合中；调用方需要用数据库或精确集合处理误判。
build(keys):
repeat with a new seed:
edges = positions_and_fingerprints(keys, seed)
queue = all degree-1 slots
order = peel(edges, queue)
if order contains every edge:
table = zeroed slots
for edge in reverse(order):
table[edge.unique] = edge.fp XOR table[edge.other1] XOR table[edge.other2]
return seed, table
fail after bounded retries
contains(key):
a, b, c = positions(key, seed)
return table[a] XOR table[b] XOR table[c] == fingerprint(key)第六步：处理失败与资源
构建失败不是查询 false negative，而是当前种子下的图没有可剥离顺序。限制重试次数，改变种子或表大小；达到上限时返回明确错误，不发布半成品。构建保留度数、边列表和 peeling 栈，峰值内存通常高于最终只读表。
第七步：说明更新与验证
Xor Filter 的表是由全体 key 联合求解的，任意插入或删除都可能破坏其他 key 的异或关系。更新采用重新构建、双版本切换或增量小表叠加。测试空集合、单 key、重复 key、极端哈希碰撞、构建失败、序列化恢复、误判率和并发只读查询。
高质量示范回答
我会将 key 集合映射成三段槽位组成的 3-uniform 超图，先用度数队列 peeling，成功后按逆序回填短指纹。查询只做三次取槽和异或，因此是常数时间，但结果是 approximate membership。构建失败表示当前种子图不可剥离，我会更换种子并限制重试，超过上限就拒绝发布。表依赖全体 key，不能安全原地删除或插入；生产更新采用新表构建后原子切换。种子、表大小、指纹宽度和字节序都要随版本持久化，并用精确集合测量 false positive rate。
常见错误
- 错误表现： 构建失败时直接返回部分表。→ 失败原因： 未处理的边会造成 false negative。→ 修正方法： 失败即换种子或表大小，成功覆盖全部边后才发布。
- 错误表现： 查询使用不同的种子或位置分段。→ 失败原因： 构建和查询的槽位不一致。→ 修正方法： 序列化并锁定种子、段边界和哈希版本。
- 错误表现： 把查询结果当作精确存在性。→ 失败原因： 短指纹会产生 false positive。→ 修正方法： 将 filter 作为前置筛选，命中后再查精确存储。
- 错误表现： 支持原地删除。→ 失败原因： 一个槽位被多个 key 共享，修改会破坏其他异或方程。→ 修正方法： 使用重建、双版本或选择动态过滤器。
追问及应对
为什么需要三段而不是一个数组？
三段布局让每条边从固定的三个区域各取一个槽位，便于构造可剥离超图和常数次查询；实际比例与装载因子要通过基准测试确定。
如何选择指纹位数？
指纹越短，空间越小但误判率越高。用独立未命中 key 的实验测量误判率，再结合业务对后端精确查询的成本选择位数。
重试种子会不会让结果不稳定？
表内容会变化，但只要把最终种子、版本和表一起持久化，查询结果可复现。发布流程应把构建元数据写入同一版本清单。
什么时候改用 Bloom 或 Cuckoo Filter？
需要频繁插入、删除、计数或在线扩容时，动态过滤器更合适。Xor Filter 的优势在静态批量构建后的空间和查询效率。