布谷鳥過濾器 (Cuckoo Filter)

引言：布隆過濾器缺失的功能

布隆過濾器 (4.4 章) 很棒，但她有一個致命缺陷：你不能刪除元素。如果你嘗試將某個位元設為 0，你可能會意外地「刪除」另外 10 個共享該位元的元素。

布谷鳥過濾器 (Cuckoo Filter) 是一種現代概率型資料結構，解決了這個問題。她支援 刪除 操作，在低誤報率下比布隆過濾器更省空間，並且透過「布谷鳥雜湊」技術提供了更快的查詢速度。

演算法要解決什麼問題？

• 輸入： 一個元素。
• 輸出： False (絕對不在) 或 True (可能在)。
• 承諾： 提供支援刪除操作的成員判定，且在高精度需求下空間效率更高。

核心思想 (直覺版)

想像一隻 布谷鳥。她會把其他鳥的蛋踢出巢穴，換成自己的蛋。

1. 桶 (Buckets)： 不同於位元陣列，我們有一組桶，每個桶可以存放幾個「指紋」 (Fingerprints，即元素雜湊後的極小片段)。
2. 兩個巢穴： 每個元素都有兩個可選的桶位置。
3. 踢出 (The Kick Out)： 如果兩個候選桶都滿了，新元素會踢出其中一個舊居民。被踢出的舊居民會飛向她的另一個備選桶，並可能踢出那裡的居民。這種「布谷鳥」行為會持續下去，直到每個人都找到家。

為什麼要用她替代布隆過濾器？

• ✅ 支援刪除： 你可以透過從桶中移除對應的指紋來安全地刪除元素。
• ✅ 查詢性能： 查詢只需要檢查 2 個桶，這對 CPU 快取非常友好（而布隆過濾器需要檢查 $K$ 個隨機位置）。
• ✅ 空間效率： 當要求的誤報率非常低（如 < 3%）時，她比布隆過濾器更省空間。

典型業務場景

• ✅ 動態黑名單： 防火牆需要臨時封禁某些 IP，之後再解封（刪除支援是關鍵）。

• ✅ 庫存管理： 在海量倉庫快取中檢查某個 SKU 是否存在，且商品會頻繁入庫和出庫。

• ✅ 流式去重： 識別在過去一小時內是否見過某個特定的交易 ID。

• ❌ 容量上限： 如果過濾器太滿，「踢出」過程可能會進入死循環或失敗。通常需要保持裝載因子在 95% 以下。

性能與複雜度總結

• 時間： 查找、插入、刪除均為 $O(1)$。
• 空間： 在高精度下略優於布隆過濾器，支援刪除。

小結：一句話記住它

「布谷鳥過濾器是『更聰明的布隆過濾器』。透過儲存指紋並允許元素在巢穴間搬家，她提供了布隆過濾器無法實現的『刪除』功能。」