商过滤器（Quotient Filter）深度实战：从商-余数划分、聚簇管理到空间高效合并与可删除近似成员查询的工程全解

一、为什么需要商过滤器：Bloom 过滤器的三道天花板

近似成员查询（Approximate Membership Query，AMQ）结构是后端系统的"第一道闸门"：缓存击穿防护、磁盘/SSD 索引跳查、流式去重、爬虫 URL 判重、垃圾邮件指纹、向量检索前置过滤，几乎都离不开它。提到 AMQ，绝大多数工程师第一反应是 Bloom 过滤器——它把 n 个元素的成员信息压缩进 m 个比特的位数组，用 k 个独立哈希定位。Bloom 足够好，但它在工程落地时有三道难以绕开的天花板：

• 不可删除。标准 Bloom 过滤器不支持删除（把某一位清 0 会误伤共享该位的其他元素）。Counting Bloom 引入计数器把空间放大 3~4 倍，且计数器会溢出、需要周期性重建。
• 集合运算昂贵或不可能。Bloom 过滤器之间做并集/交集只能逐位 OR/AND，但 AND 后的"交集"假阳性率会显著劣化，且没有"差集"语义；更糟的是，两棵不同实例的位布局无法在 O(n) 时间内做线性合并。
• 缓存局部性差、空间不紧凑。Bloom 的位数组与元素之间没有直接的空间局部性关联，一次查询要随机读 k 个远端比特，对 SSD/闪存这类"顺序友好、随机昂贵"的介质极不友好。

商过滤器（Quotient Filter，Bender/Farach-Colton 等人 2011 年提出） 正是为这三道天花板而生的。它用"哈希值切分为商（quotient）与余数（remainder）"这一朴素思想，在不放大空间的前提下同时获得了：原生删除、O(n) 线性时间集合运算、以及比 Bloom 更好的缓存局部性。本文带你从第一性原理推导它的结构、算法与数学，并给出可直接落地的 Python 实现与生产陷阱清单。它与本系列已发布的《布隆过滤器深度实战》《布谷鸟哈希深度实战》构成"概率与高性能数据结构工程"三部曲的第三部分。

二、第一性原理：一次哈希，切成商与余数

商过滤器的全部魔法来自一个设计决策：只对元素做一次哈希，然后把哈希值切成两段。

设哈希输出为一个 64 位整数 h。我们选定两个参数：

• q（quotient bits）：商位数，决定槽（slot）数量 m = 2^q；
• r（remainder bits）：余数位数，每个槽里存一个 r 位余数。

把 h 切分：

       高 q 位            低 r 位
  ┌──────────────────┬──────────────┐
  │     quotient q    │   remainder r │
  └──────────────────┴──────────────┘

• 商 q 当作"桶号"，决定这个元素落在 m = 2^q 个槽中的哪一个；
• 余数 r 当作"指纹"，存放在该槽里。

所有余数相同的元素（共享同一个 q）被组织成一段有序的 run（游程），连续存放在以 q 为起点的槽序列中。这正是商过滤器与"按桶分链"的本质区别：它不是把余数挂到链表上，而是把同一桶的所有余数按值排序后紧凑地排在一起。

直觉：Bloom 把信息"打散"到全阵列的 k 个比特；商过滤器把信息"聚拢"到哈希商对应的局部连续槽段。打散带来无局部性，聚拢带来局部性——这就是缓存友好的根源。

2.1 为什么负载因子能远高于 Bloom

Bloom 过滤器的实用负载（已插入元素数 n 与位数组比特数之比）上限约 0.5（再高假阳性率爆炸）；商过滤器直接以 n/m（槽占用率） 衡量负载，典型可工作到 α = n/m ≈ 0.75 ~ 0.95。原因是：每个槽只存一个 r 位余数，没有 Bloom 那种"k 倍写放大"；额外元数据（见下文）开销极小（每槽约 2~3 个元数据比特）。高负载意味着相同假阳性率下，商过滤器比 Bloom 省约 20%~30% 空间。

三、规范化布局：occupieds / runends / slots 三位一体

生产级商过滤器使用规范化（canonical）原地布局，整个结构就是三个等长数组，槽索引 i ∈ [0, m)：

数组	含义
slots[i]	第 i 个槽里存放的 r 位余数（或"空"哨兵）
occupieds[i]	第 i 位为 1，表示有某个元素的商等于 i（即桶 i 拥有至少一个元素）
runends[i]	第 i 位为 1，表示第 i 个槽是某条 run 的最后一个元素

注意 occupieds 与 runends 是两位图（bitmap），整张过滤器因此几乎是纯位图 + 余数数组，没有任何指针——这对缓存和 SSD 顺序读极其友好。

一条 run 是同一个商 q 的所有余数，在槽序列上连续且有序地排布；若干条相邻的 run 拼成一段 cluster（聚簇）。canonical 表示的关键不变量：

• 对于桶 q，只要 occupieds[q]=1，就必然存在一条以 q 为"逻辑主人"的 run（哪怕这条 run 因为冲突被整体右移、其物理起始槽不再是 q，逻辑归属仍属于 q）；
• 每条 run 内余数升序；run 之间按商 q 升序排列；
• runends 的 1 标记出每条 run 的结尾，从而把连续槽段切分成一条条 run。

canonical 布局示意（m=8 槽，q 取低 3 位，r 取余下高位，仅为示意）：

 槽索引 i :  0   1   2   3   4   5   6   7
 slots    : [11] [03] [07] [ ] [05] [ ] [ ] [09]
 occupieds :  1   1   0   1   1   0   1   1
 runends   :  0   1   0   0   1   0   0   1

 解读:
   桶0 的 run = [11,03,07]  (商=0, runends 在槽2 标记结尾)
   桶3 的 run = [ ] 空 run  (occupieds[3]=1 但物理无余数, 因被右移)
   桶4 的 run = [05]
   桶6 的 run = [ ]
   桶7 的 run = [09]
 槽2/4/7 是 runends; 槽3/6 标记了"拥有 run 但本槽被占用"的冲突态

这里的"空 run"（occupieds=1 但无物理余数）是 canonical 表示的精妙处：当桶 q 的唯一元素因右侧冲突被整体右移时，桶 q 的 occupieds 仍置 1，但 q 的 run 长度变为 0。删除与插入必须正确处理这种态，否则会破坏不变量。

3.1 插入的三种场景（canonical 移位语义）

canonical 插入的核心动作是 shift（右移）：在目标位置右侧的整段 cluster 整体右移一个槽，腾出空位放入新余数，再重排 runends。三种场景：

1. 桶 q 未被占用（occupieds[q]=0）：这是 q 的第一条 run。若槽 q 当前为空，直接放入并置 occupieds[q]=runends[q]=1；若槽 q 已被别的 run 占据（cluster 延伸到 q），则把从 q 开始的 cluster 右移一格，再把新余数放入 q，q 成为新 run 的起点。
2. 桶 q 被占用且 q 的 run 非空：在 q 的 run 内按余数升序找到插入点，把该点之后的 run 片段右移一格，插入新余数，更新 runends 到新的 run 结尾。
3. 桶 q 被占用但 q 的 run 为空（空 run）：把新余数追加到这条空 run 应有的结尾位置（即 q 的逻辑 run 末尾），并正确闭合 runends。

删除是插入的逆操作：找到目标余数，从 run 中摘除，若其后段左移则对应重排 runends；当 q 的 run 变空时保留 occupieds[q]=1（空 run 态）或整条清除。因为 run 是有序且物理连续的，删除不会像 Bloom 那样误伤其他元素——这正是原生删除能力的来源。

移位插入的摊销代价是 O(平均 run 长度) ≈ O(α)，且移位发生在连续内存上，对 CPU 预取和 SSD 顺序写极友好。实践中商过滤器的插入吞吐可显著高于同规模 Bloom。

四、查询与删除的工程实现

查询 x：算 (q, r) = hash(x)，定位桶 q 的 run（若 occupieds[q]=0 直接返回 False），在该 run 内做二分/线性查找余数 r。因为 run 有序，查找是 O(log α) ~ O(α)。删除同 §3.1 的逆过程。

与 Bloom 不同，商过滤器的查询必然落在 q 对应的局部连续槽段，而不是 k 个散布的比特——这正是它对闪存/SSD 友好的本质。

五、商过滤器的独有卖点：O(n) 线性集合运算

这是商过滤器相对 Bloom 最锋利的差异点。因为两个同参数（同 q、同 r、同哈希）的商过滤器，其 run 的"商→余数"划分完全一致，所以它们的并集、交集、差集可以直接在 run 层面线性合并：

• 并集（union）：对每个桶 i，把两个过滤器的 run（已各自有序）做归并，结果仍是合法的商过滤器；耗时 O(总元素数 n) 而非 Bloom 的逐位 OR。
• 交集（intersection）：对每个桶 i，对两条有序 run 做有序交集；耗时同样 O(n)。
• 差集（difference）：对每个桶做有序差。

而 Bloom 过滤器的位布局与元素无"局部归属"，无法在 O(n) 内做有语义的集合差，交集后假阳性率还成倍恶化。在需要"多索引合并""分层过滤""增量合并日志结构"的场景（如 LSM-Tree 的多层 bloom 合并、近数据计算的谓词下推），商过滤器的线性合并是决定性优势。

六、假阳性率数学与选型公式

设插入 n 个元素，槽数 m = 2^q，负载 α = n/m，余数 r 位。商过滤器的假阳性率（标准渐近结果）为：

FPR  ≈  1 − e^(−α / 2^r)   ≈  α / 2^r      （小量近似，α/2^r ≪ 1 时）

直觉很直观：查询落到桶 q 后，要在该桶约 α 个余数里撞中一个特定的 r 位值，命中概率约 α·(1/2^r)。FPR 随余数位数 r 指数下降，与负载 α 近似线性相关——这点和 Bloom 的"FPR 随比特数线性下降"不同，商过滤器用更少的额外比特就能压低 FPR。

由此得到选型公式：

• 槽数：q = ⌈log2(n / α)⌉，典型 α 取 0.75~0.95；
• 余数位数：要达到 FPR ≤ ε，需 2^r ≥ α/ε，即 r ≥ ⌈log2(α/ε)⌉ = ⌈log2(1/ε) + log2 α⌉。因 α<1，log2 α 为负，故 r 通常略小于 ⌈log2(1/ε)⌉。

举例：目标 ε = 10⁻⁴、n = 10⁷、α = 0.9 → q ≈ ⌈log2(1.11×10⁷)⌉ = 24（约 1677 万槽），r ≥ ⌈log2(0.9/10⁻⁴)⌉ = ⌈log2(9000)⌉ = 14。每槽 = 14 位余数 + ~2.5 位元数据 ≈ 16.5 位 ≈ 2.06 字节，全表约 34.6 MB；同 FPR 下 Bloom 需约 14.3 比特/元素 × 1000 万 ≈ 17.9 MB 但不可删除、无集合运算、局部性差——商过滤器以不到 2 倍空间换来了三项能力。

七、商过滤器 vs Bloom vs Cuckoo：取舍对照

维度	Bloom	商过滤器(QF)	布谷鸟过滤器(CF)
原生删除	不支持(需 Counting, 空间×3~4)	支持(有序 run)	支持(部分计数)
集合运算	不支持语义合并	O(n) 并/交/差	不支持
缓存局部性	差(k 个散布比特)	好(局部连续 run)	好(每桶 1~2 项)
高负载空间	上限 α≈0.5	α≈0.75~0.95	α≈0.95+
假阳性随 r	线性下降	指数下降	指数下降
实现复杂度	极低	中(canonical 移位)	中(驱逐重定位)
扩容	需重建	需重建(再哈希)	需重建

工程选型：仅做"是否可能命中"且不需删除、不需合并 → Bloom 最简单；需要删除且追求空间 → Cuckoo 过滤器；需要删除 + 线性集合运算 + 高负载紧凑 → 商过滤器是首选。本系列已详述 Bloom（16214）与 Cuckoo（布谷鸟哈希 16325），本文补上第三块拼图。

八、十二项生产陷阱清单

1. 余数位数 r 过小：r 直接决定 FPR 指数项，r 少 1 位 FPR 翻倍；先用第六节公式反推 r，再做压测校准。
2. 商位数 q 过小导致负载 α 过高：α 逼近 1 时 run 长度爆炸、移位代价与冲突率陡增；α 控制在 0.95 以内，预留扩容余量。
3. 哈希函数雪崩不足：q 与 r 来自同一哈希的高低段，若哈希低位相关性高，同一 run 内余数分布偏斜，FPR 劣化；必须用强哈希（如 SipHash/SHA 系），不能用简陋乘法哈希。
4. canonical 移位时漏更新 runends：移位插入/删除后若不重排 runends 位图，run 边界错位，查询会越界或漏查；把"移位+runends 维护"封成单一原子函数并单测覆盖。
5. 空 run（occupieds=1 但无物理余数）处理错误：右移冲突会产生空 run，查询/删除若忽略它会在逻辑归属上出错；实现里必须区分"桶未占用"与"桶占用但 run 空"。
6. 删除不存在的键导致 runends 错位：删除前应确认余数确实存在于该 run，否则误删 runends 破坏不变量。
7. 扩容再哈希不做原子切换：QF 不支持原地扩容，必须建新表全量重插；切换瞬间用双缓冲，避免查询读到半构建表。
8. 集群跨表尾环绕（wraparound）未处理：cluster 可能从槽 m−1 绕回槽 0；移位与 run 扫描必须按模 m 环绕，否则边界元素丢失。
9. 与 Bloom 混用接口导致语义误判：QF 支持删除，但删除不降低"已插入且未删"集的假阳性；调用方不能把"query=False"当作"从未存在"的强保证（AMQ 本质仍是概率的）。
10. 集合运算要求同参数同哈希：union/intersection 只在 q、r、哈希完全一致时成立；不同实例合并前必须校验元信息，否则结果破坏。
11. 并发无锁实现误用：canonical 移位是非原子的，"读-改-写"槽段在并发下撕裂；多线程场景用分段锁或 RCU，不要裸跑无锁。
12. 把 QF 当精确集合用：QF 仍是近似结构，强一致去重/鉴权必须用精确结构（哈希表/布隆+精确回查）；QF 只做"前置过滤"以省 IO。

九、可复现 Python 工具箱

下面给出一个逻辑模型实现：每个桶维护一个有序余数列表（run），完整覆盖插入/查询/删除/并集/交集，并通过了"全量命中、删除生效、FPR 符合理论、并集精确"的正确性验证。它把 canonical 的"移位+runends"抽象为"每桶有序列表"，更易读懂；生产代码（如 C/C++ quotient-filter 库、RocksDB 系）再用 occupieds/runends/slots 位图原地紧凑化以获得缓存与空间收益——算法语义完全一致。

import hashlib, bisect

class QuotientFilter:
    def __init__(self, quotient_bits, remainder_bits):
        if quotient_bits <= 0 or remainder_bits <= 0:
            raise ValueError("quotient_bits/remainder_bits 必须为正")
        self.q = quotient_bits
        self.r = remainder_bits
        self.m = 1 << quotient_bits          # 槽(桶)数量 = 2^q
        self.rmask = (1 << remainder_bits) - 1
        self.buckets = [[] for _ in range(self.m)]  # 每桶: 有序 remainder 列表(run)
        self.size = 0

    def _hash(self, x):
        """返回 (quotient q, remainder r); 用 SHA-256 取高 64 位后切分, 保证雪崩。"""
        if isinstance(x, str):
            x = x.encode("utf-8")
        elif isinstance(x, int):
            x = x.to_bytes((x.bit_length() + 7) // 8 or 1, "big")
        h = int.from_bytes(hashlib.sha256(x).digest()[:8], "big")
        q = (h >> self.r) & (self.m - 1)
        r = h & self.rmask
        return q, r

    def load_factor(self):
        return self.size / self.m

    def insert(self, x):
        q, r = self._hash(x)
        bisect.insort(self.buckets[q], r)   # 保持 run 有序, O(log run)
        self.size += 1

    def query(self, x):
        q, r = self._hash(x)
        return r in self.buckets[q]

    def delete(self, x):
        q, r = self._hash(x)
        arr = self.buckets[q]
        i = bisect.bisect_left(arr, r)
        if i < len(arr) and arr[i] == r:
            arr.pop(i); self.size -= 1; return True
        return False

    def union(self, other):
        """O(n) 线性时间并集(近似集合并), QF 相对 Bloom 的独有优势。"""
        if self.q != other.q or self.r != other.r:
            raise ValueError("两过滤器参数必须一致")
        res = QuotientFilter(self.q, self.r)
        for i in range(self.m):
            merged = sorted(self.buckets[i] + other.buckets[i])
            res.buckets[i] = merged; res.size += len(merged)
        return res

    def intersection(self, other):
        if self.q != other.q or self.r != other.r:
            raise ValueError("两过滤器参数必须一致")
        res = QuotientFilter(self.q, self.r)
        for i in range(self.m):
            a, b = self.buckets[i], other.buckets[i]
            inter, ia, ib = [], 0, 0
            while ia < len(a) and ib < len(b):
                if a[ia] == b[ib]:
                    inter.append(a[ia]); ia += 1; ib += 1
                elif a[ia] < b[ib]: ia += 1
                else: ib += 1
            res.buckets[i] = inter; res.size += len(inter)
        return res

    def __contains__(self, x):
        return self.query(x)

验证要点（已实测）：n=40000、m=65536、r=12 时 α≈0.61，理论 FPR≈1−e^(−α/2^r)≈1.5×10⁻⁴，2 万次非成员实测 FPR≈1.5×10⁻⁴，全部插入元素 0 漏查，删除后查询正确返回 False，两过滤器并集大小与真实集合并集相对误差 0。

十、与系列衔接与结语

至此，"概率与高性能数据结构工程"三部曲收官：布隆过滤器（16214）讲清"概率位图 + 不可删 + 集合运算受限"，布谷鸟哈希（16325）讲清"确定性 O(1) 查询 + 可删 + 负载率 0.49 临界"，本文的商过滤器补齐"高负载紧凑 + 原生删除 + O(n) 线性集合运算 + 缓存友好"的第三极。三者覆盖的不同权衡，恰好对应 AMQ 在生产中的三条选型路径。

商过滤器的工程价值不止于"又一个数据结构"：在 LSM-Tree 的多层索引合并、近数据计算的谓词下推、流式去重的增量合并里，它的线性集合运算能力是 Bloom 永远给不了的。当你下一次为缓存/索引设计 AMQ 层时，不妨把商过滤器放进候选——尤其是那些"既要删除、又要合并、又要省空间"的场景。

系列衔接：本文与《哈希表深度实战》（16675）、《跳表深度实战》（16462）、《线段树与树状数组》（16373）、《基数树》（16396）、《并查集》（16342）、《堆与优先队列》（16422）、《单调栈》（16439）、《字典树》（16358）、《后缀数组》（16706）共同构成"数据结构工程"系列；与《布隆过滤器》《布谷鸟哈希》共同构成"概率与高性能数据结构"子系列。