布谷鸟过滤器：会“鸠占鹊巢”的集合管家

可视化演示

Cuckoo Filter是支持删除操作的布隆过滤器替代方案，通过布谷鸟哈希实现动态集合管理。本文讲解布谷鸟哈... 切换模式查看不同维度。

布谷鸟哈希

快递站的登记簿（布隆过滤器）有个致命弱点：不能删除记录。新同事提出的解决方案，源自一种鸟类——布谷鸟的生存智慧。布谷鸟妈妈从不在自己的巢里孵蛋，而是偷偷把蛋下到其他鸟的巢里，让“养父母”代为孵化。更绝的是，小布谷鸟一出壳就会把养父母的蛋挤出巢外，独占养育资源。这套“两个巢”的策略，被计算机科学家巧妙地应用到了哈希表设计中。

布谷鸟哈希是一种解决哈希冲突的奇妙方法。传统的哈希表有一个数组，一个 key 通过哈希函数映射到一个位置。布谷鸟哈希则用两个哈希函数，为每个 key 提供两个候选位置——就像布谷鸟为自己准备了两个备选巢穴。当你插入一个新 key 时，先看第一个候选位置是否有空位；如果有，直接入住；如果没有，就占据这个位置，把原来的住户“踢”出去，让它去它的另一个候选位置安家。

1. 第一个哈希函数：计算 key 的第一个候选巢位。哈希函数把任意长度的键映射到 0 到 n-1 之间的整数。

$$\displaystyle h_1(key) = hash_1(key) \bmod n$$

2. 第二个哈希函数：计算 key 的第二个候选巢位。两个哈希函数必须是相互独立的，这样两个候选巢位才会均匀分布。

$$\displaystyle h_2(key) = hash_2(key) \bmod n$$

回到快递站的场景：每个包裹编号经过两个计算器算出两个“候选货架号”。当新包裹到来，先看第一个候选货架有没有空位，没有就把上面的旧包裹“请”到它的另一个候选货架去。这就是布谷鸟哈希的基本思想。

\displaystyle h_1(key) = hash_1(key) \bmod n

\displaystyle h_2(key) = hash_2(key) \bmod n

踢出机制

被踢的鸟会怎么办呢？它会飞去自己的另一个巢。如果那个巢也被占了，它就再踢走那里的住户，被踢的住户再去自己的另一个巢……这样一环扣一环，像多米诺骨牌一样连锁反应。这种“恶性循环”恰恰保证了哈希表的高空间利用率。

在布谷鸟哈希中，插入操作的流程是这样的：计算 key 的两个候选位置，如果其中一个是空的，直接插入；如果两个都满了，随机踢出其中一个位置的现有元素，把新 key 放进去；被踢出的元素重新计算它的另一个候选位置，如果那个位置有空位就插入，否则继续踢出下一个元素。这个过程不断重复，直到所有元素都找到了自己的巢穴。

1. 控制循环次数：设置最大尝试次数，防止无限循环。现实中，如果布谷鸟一直在踢来踢去永远安定不下来，就需要扩大鸟巢规模。

$$\displaystyle while \ (attempt \leq MaxAttempts)$$

2. 检查空位：如果当前位置是空的，直接安家，插入成功。

$$\displaystyle if \ slot \ empty: \ insert \ and \ done$$

3. 踢出原住户：如果位置被占了，踢出它并取而代之。被踢的住户继续寻找自己的另一个巢。

$$\displaystyle else: \ evict \ occupant, \ swap, \ attempt++$$

这种踢出机制让布谷鸟哈希表的空间利用率可以达到 90% 以上，而普通哈希表超过 70% 就会频繁冲突。就像快递站里，与其让货架空着等包裹来，不如允许“稍后调整位置”——这样整个仓库能装更多包裹。

\displaystyle while \ (attempt \leq MaxAttempts): 

\displaystyle \quad if \ slot \ empty: \ insert \ and \ done

\displaystyle \quad else: \ evict \ occupant, \ swap, \ attempt++

指纹存储

快递站的登记簿有个聪明之处：不需要记录包裹的完整运单号，只需要记录一个 “门牌号” ——一段极短的编号。布谷鸟过滤器进一步发扬了这个理念，它不存储完整的 key，而是存储 key 的指纹（fingerprint）：一段非常短的定长比特串。

指纹是怎么产生的？它也是一个哈希函数的产物。只不过这个哈希函数的输出比定位用的哈希函数短得多。例如，我们可以用 8 比特（1 字节）来存储一个指纹。这意味着，无论原始 key 有多长，在过滤器里都只占 1 字节空间。就像无论你的全名多长，门卫登记时只记你的姓和房号。

1. 哈希函数：对 key 进行哈希计算，得到一个较长的整数。

$$\displaystyle hash_f(x)$$

2. 截断处理：对 2 的 f 次幂取模，相当于只保留哈希值的低 f 位，从而得到 f 比特的短指纹。

$$\displaystyle \bmod \ 2^f$$

为什么要存指纹而不是完整 key？因为 Cuckoo Filter 的设计目标就是“空间高效”。完整 key 可能占用几十字节乃至更多，而指纹只占几比特。这就像快递站不记录每件包裹的完整追踪号，只记录货架号和一个两位数的校验码——足以判断“这个包裹以前来过没”。

指纹存储是 Cuckoo Filter 能在空间效率上与布隆过滤器一较高下的关键。布隆过滤器为每个元素设置多个比特位，而 Cuckoo Filter 为每个元素只存一个小指纹。空间上，两者的差别很小，但功能上，Cuckoo Filter 多了删除能力——这完全是拜“门牌号”所赐。

\displaystyle fingerprint(x) = hash_f(x) \bmod 2^f

双桶查找

当我们需要查找一个 key 是否在过滤器中时，流程非常直观：计算出这个 key 的两个候选桶位置，然后在这两个桶中查找完整的指纹。它的查找复杂度是 O(1)——无论集合中有多少元素，都只需要检查两个固定位置。

这种“双桶查找”设计有什么好处？首先它快——只查两个桶，不像布隆过滤器需要检查多个哈希位。其次，它天然支持删除——找到指纹就能抹掉它。但“只查指纹”也带来了一个副作用：假阳性。假设两个不同的 key 拥有相同的指纹（指纹冲突），并且它们被映射到了相同的桶，那么查找时就会误判为“存在”。这就是 Cuckoo Filter 假阳性的根本来源。

1. 指纹的位数决定基数：每个指纹有 2 的 f 次方种可能取值，所以两个元素指纹相同的概率约 1/2^f。

$$\displaystyle \frac{1}{2^f}$$

2. 双桶检查概率：查找需要比较两个桶中最多 2b 个指纹，每个都不匹配的概率是 (1 - 1/2^f) 的 2b 次方。

$$\displaystyle (1 - \frac{1}{2^f})^{2b}$$

3. 求补集：用 1 减去“全部不匹配”的概率，就是“至少有一个误匹配”的概率。

$$\displaystyle 1 - (...)^{2b}$$

回到快递站的比喻：门卫核对包裹时，只看“门牌号+两位校验码”。如果恰好另一个包裹的校验码也是 42，而且它也放在同一排货架，门卫就会误以为它就是那个包裹。门牌号的位数越长，这种误判概率越低，但存储空间也随之增加。

\displaystyle false\_positive \approx 1 - (1 - \frac{1}{2^f})^{2b}

删除操作

布隆过滤器最令人头疼的缺陷是什么？不能删除元素。因为多个元素共享同一个比特位，你无法安全地把某个元素对应的位清零，否则可能导致其他元素被误判为“不存在”。布谷鸟过滤器绕开了这个难题，因为它为每个元素保存了独立的指纹，删除操作只需三步：找到指纹、确认匹配、抹掉指纹。

删除的具体流程是：首先计算 key 的两个候选桶；然后在这两个桶中查找匹配的指纹；如果找到了，就把这个指纹从槽位中移除。这个操作是 O(1) 的，非常高效。但要注意，删除操作只在指纹匹配时才执行——如果因为假阳性而错误匹配，那么删除的是一个本不该删除的指纹，这就是“删除假阳性”问题。

1. 计算指纹：对要删除的 key 计算指纹 f，这是查找的依据。

$$\displaystyle f = fingerprint(x)$$

2. 双桶检查：在两个候选桶中查找指纹 f。

$$\displaystyle f \in bucket[h_1(x)] \ or \ f \in bucket[h_2(x)]$$

3. 移除指纹：找到后删除，这就是删除操作的全部。

$$\displaystyle remove \ f \ from \ bucket$$

删错了怎么办？这就是 Cuckoo Filter 在删除场景下的“阿喀琉斯之踵”。因为指纹是短编码，存在碰撞可能，所以删除操作可能误伤。但好在 Cuckoo Filter 的错误不会累积——即使删错了一个指纹，后续的查找和插入依然正常工作。为了减少删除误伤，实际系统常用更大的指纹（如 16 比特）来降低碰撞概率。

快递站的类比：门卫根据门牌号找到包裹记录后，把那张登记卡抽出来撕掉。如果因为门牌号撞号而误删了另一个包裹的记录，只要误删概率足够低（指纹足够长），对日常运营影响不大。这个“可删除”能力，正是 Cuckoo Filter 相对布隆过滤器最大的功能优势。

\displaystyle delete(x): 

\displaystyle \quad f = fingerprint(x)

\displaystyle \quad if \ f \in bucket[h_1(x)] \ or \ f \in bucket[h_2(x)]:

\displaystyle \qquad remove \ f \ from \ bucket

布隆对比

布隆过滤器用多个哈希位标记元素，空间利用率极高，但功能受限：不能删除、查找需要检查多个位。布谷鸟过滤器在两处实现了关键突破：支持删除和更快的查找。二者在空间效率上几乎打平，但在功能完整性和性能表现上，Cuckoo Filter 明显胜出。

让我们从三个维度对比两者：

| 维度 | 布隆过滤器 | 布谷鸟过滤器 |

|------|-----------|-------------|

| 删除操作 | 不支持 | 支持 |

| 查找复杂度 | O(k)，k 个哈希函数 | O(1)，只查两个桶 |

| 空间效率 | 约 0.618 比特/元素/假阳性率 | 约 1.05 比特/元素/假阳性率（f=8 时接近） |

| 假阳性率 | (1 - e^{-kn/m})^k | ≤ (1 - 1/2^f)^{2b} |

1. 布隆的空间需求：达到假阳性率 p，每个元素需要约 1.44×log2(1/p) 比特。

$$\displaystyle 1.44 \times log_2(1/p) \ bits/element$$

2. 布谷鸟的空间需求：每个元素存 2 个指纹副本（两个桶的备份机制），每个 f 比特。

$$\displaystyle 2 \times f \ bits/element$$

值得注意的是，Cuckoo Filter 在查找性能上完胜布隆过滤器。布隆过滤器要计算 k 个哈希函数并检查 k 个位，而 Cuckoo Filter 只需要计算 2 个哈希函数并检查最多 2b 个槽位。在 CPU 缓存友好的场景下，这种差异会更加明显，因为 Cuckoo Filter 的桶可以被紧凑地排列在连续的缓存行中。

快递站的对比很直观：布隆登记簿像是一本不能撕页的账本，空间紧凑但只能“写不能删”；布谷鸟过滤器像一套带抽屉的卡片柜，多了个抽屉但查找时只需要开两个抽屉，而且随时可以抽出卡片销毁。空间差不多，但功能灵活得多。

\displaystyle E_{bloom} \approx \frac{1.44 \times log_2(1/p)}{8} \ bytes/element

\displaystyle E_{cuckoo} \approx \frac{2 \times f}{8} \ bytes/element

应用场景

当你需要在系统中维护一个“可能有也可能没有”的集合，并且这个集合动态变化（有增有删）时，布谷鸟过滤器就是你的首选工具。它在三个领域表现尤为突出：

数据库查询缓存：数据库查询缓存需要跟踪“哪些键存在于缓存中”。当数据被更新或删除时，缓存项需要同步失效。使用布隆过滤器无法删除失效项，而布谷鸟过滤器可以安全移除。例如，Cassandra 数据库内部就用 Bloom Filter 判断 SSTable 是否包含某行数据，但如果换成 Cuckoo Filter，就能在合并 SSTable 时动态删除无效指纹。

网络路由：在软件定义网络（SDN）中，流表条目需要频繁添加和删除。路由器使用过滤器来判断一个数据包是否匹配某个流规则。Cuckoo Filter 的删除能力让流表可以动态更新，而无需重建整个过滤器。

存储系统：在 LSM-Tree 存储引擎（如 RocksDB）中，过滤器存储在每个 SSTable 的元数据中。当一个 SSTable 被合并（Compaction）时，过滤器的内容变化很大。Cuckoo Filter 可以支持增量更新，在合并过程中动态插入新键的指纹、删除旧键的指纹。

快递站的最佳折射：如果你管理的是一个不断进新货、退旧货的仓储系统，你会希望登记簿既能记新包裹又能划掉已走的包裹——这就是 Cuckoo Filter 带来的价值。选型时，判断标准很简单：如果集合只增不减，布隆过滤器足够好；如果集合有增有删，Cuckoo Filter 是更合适的选择。

---

\displaystyle app \in \{ \ database \ cache, \ network \ routing, \ storage \ engine \ \}

AI 应用场景

Python 演示

import random class CuckooFilter:    def __init__(self, num_buckets=8, bucket_size=4, max_kicks=100):        self.num_buckets = num_buckets        self.bucket_size = bucket_size        self.max_kicks = max_kicks        self.buckets = [[] for _ in range(num_buckets)]     def _hash1(self, key):        return hash(key) % self.num_buckets     def _hash2(self, key):        return (hash(key) // self.num_buckets) % self.num_buckets     def _fingerprint(self, key):        return f"fp{abs(hash(key)) % 100:03d}"     def insert(self, key):        fp = self._fingerprint(key)        i1, i2 = self._hash1(key), self._hash2(key)        for i in (i1, i2):            if len(self.buckets[i]) < self.bucket_size:                self.buckets[i].append(fp)                return True        cur, fp_cur = i1, fp        for _ in range(self.max_kicks):            j = random.randrange(len(self.buckets[cur]))            fp_cur, self.buckets[cur][j] = self.buckets[cur][j], fp_cur            cur = i2 if cur == i1 else i1            if len(self.buckets[cur]) < self.bucket_size:                self.buckets[cur].append(fp_cur)                return True        return False     def contains(self, key):        fp = self._fingerprint(key)        return fp in self.buckets[self._hash1(key)] or fp in self.buckets[self._hash2(key)]     def delete(self, key):        fp = self._fingerprint(key)        for i in (self._hash1(key), self._hash2(key)):            if fp in self.buckets[i]:                self.buckets[i].remove(fp)                return True        return False     def load_factor(self):        total = sum(len(b) for b in self.buckets)        return total / (self.num_buckets * self.bucket_size) if __name__ == "__main__":    cf = CuckooFilter()    keys = [f"user_{i}" for i in range(20)]    for k in keys:        ok = cf.insert(k)        print(f"insert {k}: {ok}, load={cf.load_factor():.2f}")    print("contains user_5:", cf.contains("user_5"))    print("delete user_5:", cf.delete("user_5"))    print("contains user_5 after delete:", cf.contains("user_5"))

1. fingerprint = f"fp{abs(hash(key)) % 100:03d}"生成 3 位数字指纹，模拟真实系统中的短比特指纹。指纹长度直接决定假阳性率。
2. if len(self.buckets[i]) < self.bucket_size检查桶是否还有空闲槽位，有就直接追加，这是最理想的插入路径。
3. fp_cur, self.buckets[cur][j] = self.buckets[cur][j], fp_cur踢出操作：把原住户的指纹取出来赋给 fp_cur，把自己的指纹放进去。被踢出的继续找下家。
4. cur = i2 if cur == i1 else i1关键步骤：被踢出的元素去它的另一个候选桶。这里简化了真实 Cuckoo Filter 的“异或”重定位公式。
5. def load_factor计算负载因子，用于观察过滤器装满的程度。超过 95% 时插入很容易失败。

常见误区

面试题