精確 vs. 近似，這不是退而求其次，而是選擇付出多少代價換取答案。
Count-Min Sketch：「這個元素出現過幾次？」
你在做即時廣告系統，需要知道每個廣告 ID 今天被點了幾次。廣告 ID 有幾百萬種，如果用 HashMap 存每個 ID 的計數器，記憶體需求隨廣告種類線性增長——幾百萬個 entry，加上 HashMap 本身的 overhead，記憶體壓力不可小覷。
更實際的問題是：你不在乎「廣告 123456 今天被點了 48,231 次」和「48,234 次」的差距，你在乎的是「哪些廣告的點擊量異常高/低」。
Count-Min Sketch 用 w × d 的二維計數器矩陣解決這個問題：
矩陣 w=8, d=3（示意）：
0 1 2 3 4 5 6 7
row 0: [0] [0] [3] [0] [0] [2] [0] [0]
row 1: [0] [2] [0] [0] [3] [0] [0] [0]
row 2: [0] [0] [0] [2] [0] [3] [0] [0]
添加 x：
row 0: counter[0][h0(x) % 8]++
row 1: counter[1][h1(x) % 8]++
row 2: counter[2][h2(x) % 8]++
查詢 x 的頻率：
return min(counter[i][hi(x) % 8]) for i in 0..2
為什麼取 min？因為不同的 key 可能雜湊到同一個格子（碰撞），導致格子的值被多個 key 共同拉高。取 min 可以找到「碰撞最少的那一行」，得到最接近真實值的估計。
Count-Min Sketch 永遠不會低估（因為只會加），但可能略微高估（因為碰撞）。
誤差保證：查詢值 ≤ 真實值 + ε × N，機率 ≥ 1 - δ
w = ⌈e/ε⌉，d = ⌈ln(1/δ)⌉
實際用途：Cloudflare 用它做流量分析、Redis 的 Sorted Set TOP-K 用它找 Heavy Hitter（熱點 key）、Twitter 的即時熱搜底層也是類似結構。
Cuckoo Filter：Bloom Filter 的升級版，支援刪除
Bloom Filter 是個好工具，但有個致命限制：不支援刪除。
Bloom Filter 把每個元素映射到位元陣列的多個 bit，刪除時無法確定哪些 bit 是「只屬於這個元素的」——貿然清除可能影響到其他元素的查詢結果。
Cuckoo Filter 改變了儲存方式：不存 bit，存元素的指紋（fingerprint），放在兩個候選桶的其中一個：
每個元素 x 有兩個候選桶：
i1 = hash(x) % buckets
i2 = i1 XOR hash(fingerprint(x)) ← 兩個桶互相可以從對方推導
插入：
優先放 i1 或 i2 的空位
若兩個桶都滿 → 把現有的指紋踢出去（Cuckoo 布穀鳥策略），
被踢的指紋去它的另一個候選桶
刪除：
在 i1 或 i2 找到指紋 → 直接移除
「Cuckoo」名字來自布穀鳥——它把蛋下在別人的巢裡，把原本的蛋踢出去。插入時如果滿了，就把現有元素踢到它的備用桶，這個動作可能連鎖觸發，但通常很快收斂。
Cuckoo Filter vs Bloom Filter（同樣 1% 誤判率）：
Bloom Filter: 9.6 bits/element
Cuckoo Filter: 8 bits/element（約省 17%）
Bloom Filter: 不支援刪除
Cuckoo Filter: 支援刪除
查詢速度：兩者都是 O(1)，Cuckoo 的常數略小（只查兩個桶）
Cassandra 用 Bloom Filter 擋不存在的 key（避免磁碟查詢）；Elasticsearch 也是類似應用。如果你的場景需要刪除（例如快取失效後要從 filter 移除 key），Cuckoo Filter 是更好的選擇。
三個結構的選擇邏輯
| 問題 | 用什麼 |
|---|---|
| 這個 key 存在嗎（不需要刪除） | Bloom Filter |
| 這個 key 存在嗎（需要刪除） | Cuckoo Filter |
| 這個 key 出現過幾次 | Count-Min Sketch |
| 總共有多少不同 key | HyperLogLog |
這四個概率型結構各自解決不同的問題，不是「哪個更好」，而是「你在問哪個問題」。
概率型資料結構的本質是用精確度換空間——關鍵是你要清楚，你願意接受多少誤差，以及誤差的方向是什麼（高估 vs. 低估）。