Bloom Filter 回答的不是「是」或「不是」，而是「一定不是」或「可能是」。這個「可能」撐起了無數大規模系統。
用一點誤判換巨大空間
Bloom Filter 用極少的空間判斷元素是否存在於集合中。它有假陽性（說存在但其實不在），但絕對沒有假陰性（說不在就一定不在）。不能刪除、不能列舉。用在快取穿透防護、垃圾郵件過濾、URL 去重等場景。
原理：多個 hash + 一個 bit array
bit array（初始全 0）:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
加入 "apple"（3 個 hash function）:
hash1("apple") = 2, hash2("apple") = 5, hash3("apple") = 8
[0, 0, 1, 0, 0, 1, 0, 0, 1, 0]
↑ ↑ ↑
加入 "banana":
hash1("banana") = 1, hash2("banana") = 5, hash3("banana") = 7
[0, 1, 1, 0, 0, 1, 0, 1, 1, 0]
↑ 碰撞！5 已經是 1 了查詢時，算出所有 hash 值，檢查對應的 bit 是不是都是 1：
查 "cherry": hash = 2, 4, 8
bit[2]=1 ✓, bit[4]=0 ✗ → 一定不存在。有一個 0 就能確定。
查 "grape": hash = 1, 5, 8
bit[1]=1 ✓, bit[5]=1 ✓, bit[8]=1 ✓ → 可能存在（但其實是誤判！）這就是假陽性：所有 bit 恰好都被其他元素設成 1 了。
把它的脾氣列成一張表，之後選型時對照著看：
| 特性 | 說明 |
|---|---|
| 空間效率 | 只存 bit，遠小於存實際元素 |
| 假陽性 | 可能說「在」但其實不在 |
| 無假陰性 | 說「不在」就一定不在——這條是它的命根子 |
| 不可刪除 | 清 bit 會連累其他元素 |
| 不可列舉 | 只能問「在不在」，倒不出裡面有誰 |
「無假陰性」那條要記牢：Bloom Filter 敢拿來擋快取穿透、擋去重，全靠這個保證。哪天它說「不在」卻其實在，整套設計就崩了——所以後面「不能刪除」不是懶得做，是不能做。
為什麼能容忍假陽性？
因為大部分場景只需要快速排除「一定不在」的情況。
快取穿透防護：有人狂打一個不存在的 key，每次都穿透快取打到資料庫。用 Bloom Filter 先擋一層——如果它說「不在」，就直接回 404，不查資料庫。偶爾假陽性讓一些不存在的 key 也查了資料庫？沒關係，反正也只是多查一次。
爬蟲 URL 去重：已經爬過的 URL 存進 Bloom Filter。新 URL 先查一下——如果「一定不在」就去爬，如果「可能在」就跳過。漏爬幾個比重爬幾百萬個好太多了。
參數怎麼設？
給定預期元素數 n 和能接受的誤判率 p：
bit array 大小 m = -n × ln(p) / (ln2)²
hash function 數量 k = (m/n) × ln2| 元素數 | 誤判率 | 需要多少 bit | hash 函數數 |
|---|---|---|---|
| 1,000 | 1% | ~1.2 KB | 7 |
| 100,000 | 1% | ~120 KB | 7 |
| 100,000 | 0.1% | ~180 KB | 10 |
十萬個元素只需要 120 KB 就能達到 1% 的誤判率。如果你用 HashSet 存十萬個字串，那是好幾 MB。空間效率差距是數量級的。
🎬 互動視覺化：Hash 與 bit array 怎麼運作 — Bloom Filter 底層就是「多個 hash 打進同一張 bit array」，這個視覺化讓你直接看 key 被 hash 到哪些格、碰撞怎麼疊在一起，正是假陽性的來源。
不能刪除的問題
把某個 bit 從 1 改回 0？不行，因為其他元素可能也 hash 到那個 bit。改了就會讓其他元素產生假陰性——而假陰性是 Bloom Filter 絕對不能有的。
解法：Counting Bloom Filter，把每個 bit 換成計數器。加入 +1，刪除 -1，歸零才真的是 0。代價是空間翻好幾倍。
另一個更現代的選項是 Cuckoo Filter——支援刪除、空間更小、查找更快。如果你的場景需要刪除，直接用 Cuckoo Filter。還有 Quotient Filter，除了刪除還能合併與動態調整大小，適合資料量會長大、事先抓不準容量的場景。
雙重 hash 技巧
不用真的寫 k 個 hash function，兩個就夠了：
int hash_i(String item, int i) {
return (hash1(item) + i * hash2(item)) % m;
}用兩個獨立 hash 線性組合出 k 個，數學上證明效果等價。
Bloom Filter 是工程上「不完美但夠用」的典範——用 1% 的錯誤率換來 99% 的空間節省。完美主義者大概會崩潰，但系統工程師會微笑。
接下來往哪走
- Suffix Array 後綴陣列 — 下一篇：進入競程與進階主題區
- Count-Min Sketch & Cuckoo Filter 串流資料的頻率與過濾 — 文中提到的 Cuckoo Filter 完整版，加上「出現幾次」的頻率問題
- HyperLogLog 用 1.5 KB 計算十億個不同用戶 — 機率型結構家族的另一員：回答「有多少個不同元素」
- 為什麼「加個 cache」常常讓事情更糟：四種你沒想到的翻車法 — 快取穿透在工程上長什麼樣、Bloom Filter 之外還要防什麼