Bloom Filter 與機率性資料結構
當你需要檢查一個元素是否在一個集合中，最簡單的方式是用 HashSet。但如果集合中有數十億個元素呢？HashSet 會佔用大量記憶體。
Bloom Filter 是一個極度節省記憶體的機率性資料結構。它可以告訴你：
- 一定不在（100% 正確）
- 可能在（有機率誤判）
這種取捨在許多大數據場景中非常值得——用微小的誤判率換取 90% 以上的記憶體節省。
實作 Bloom Filter
import math
import mmh3
from bitarray import bitarray
class BloomFilter:
def __init__(self, n, fp_prob):
"""
n: 預計插入的元素數量
fp_prob: 期望的誤判率 (False Positive Probability)
"""
self.fp_prob = fp_prob
self.size = self._get_size(n, fp_prob)
self.hash_count = self._get_hash_count(self.size, n)
self.bit_array = bitarray(self.size)
self.bit_array.setall(0)
def _get_size(self, n, p):
"""計算需要的 bit 數"""
m = -(n * math.log(p)) / (math.log(2) ** 2)
return int(m)
def _get_hash_count(self, m, n):
"""計算需要的 hash 函數數量"""
k = (m / n) * math.log(2)
return int(k)
def add(self, item):
"""加入元素"""
for i in range(self.hash_count):
digest = mmh3.hash(item, i) % self.size
self.bit_array[digest] = True
def check(self, item):
"""檢查元素是否存在"""
for i in range(self.hash_count):
digest = mmh3.hash(item, i) % self.size
if not self.bit_array[digest]:
return False # 一定不在
return True # 可能在
# 使用範例
bf = BloomFilter(1000000, 0.01) # 100 萬個元素，1% 誤判率
print(f"bit 陣列大小: {bf.size/1024/1024:.2f} MB")
print(f"hash 函數數: {bf.hash_count}")
# 加入一些元素
for i in range(10000):
bf.add(f"user_{i}_email@gmail.com")
# 測試
print(f"\n已存在的 email: {bf.check('user_123_email@gmail.com')}")
print(f"不存在的 email: {bf.check('fake_email@gmail.com')}")
# 測試誤判率
test_size = 10000
false_positives = 0
for i in range(test_size):
if bf.check(f"not_in_set_{i}@test.com"):
false_positives += 1
print(f"\n誤判率測試: {false_positives/test_size:.4%} (理論值: 1%)")
記憶體比較
| 資料結構 | 100萬項目 | 記憶體 | 備註 | |---------|----------|--------|------| | HashSet | 100萬字串 | ~50 MB | 100%準確 | | Bloom Filter (1% FP) | 100萬項目 | ~1.2 MB | 節省97.6% | | Bloom Filter (0.1% FP) | 100萬項目 | ~1.8 MB | 節省96.4% | | Bloom Filter (0.01% FP) | 100萬項目 | ~2.4 MB | 節省95.2% |
實際應用場景
1. 快取過濾（防止快取穿透）
當網頁伺服器收到某個 key 的請求時，先檢查 Bloom Filter。如果 filter 說該 key 不存在，直接跳過快取查詢 — 這可以防止快取穿透導致資料庫被擊垮。
2. 爬蟲 URL 去重
搜尋引擎爬蟲使用 Bloom Filter 來追蹤已訪問過的 URL。面對數十億的 URL，Bloom Filter 可比 HashSet 節省數 TB 的 RAM。
3. 垃圾郵件檢測
郵件服務維護已知垃圾郵件發送者地址的 Bloom Filter。如果某發送者「絕對不在」filter 中，郵件可快速送達；如果「可能在」，則觸發更詳細的檢查。
4. 資料庫查詢優化
Apache Cassandra 使用 Bloom Filter 快速判斷某行是否存在於 SSTable 中，避免不必要的磁碟 I/O。PostgreSQL 也有類似的 visibility map 機制。
5. 區塊鏈輕錢包
以太坊輕錢包使用 Bloom Filter 來檢查某筆交易或日誌是否存在於區塊中，而無需下載完整區塊。
時間複雜度
| 操作 | 時間複雜度 | |------|-----------| | add(item) | O(k) — k 個 hash 函數 | | check(item) | O(k) — k 個 hash 函數 | | 空間 | O(m) — m 位元的陣列 |
與 HashSet（需要 O(n) 記憶體且可能需重新調整大小）不同，Bloom Filter 的記憶體使用量是可預測且固定的，無論實際元素數量如何（雖然隨著元素增加，誤判率會上升）。
限制
| 限制 | 說明 | |------|------| | 無法刪除元素 | 標準 BF 不支援刪除（可使用 Counting BF） | | 誤判（False Positive） | 省記憶體的代價，無法完全消除 | | 誤判率會增長 | 當加入的數量超過預期的 n，誤判率會上升 | | 無法列舉 | 不能列出已儲存的所有元素 |
總結
- 節省空間的機率性資料結構
- 100% 召回率 — 保證沒有 false negative
- 可設定誤判率（在記憶體與準確度之間取捨）
- 使用 k 個獨立 hash 函數將元素映射到 bit 位置
- 廣泛應用於資料庫、快取、分散式系統與區塊鏈
真實世界的工程抉擇：何時該用 Bloom Filter？
你的 API 每秒收到 10,000 次請求，需要檢查請求的 IP 是否在黑名單中。
黑名單有 500 萬個 IP。
選項 A：HashSet（100% 準確）
記憶體: 500萬 × ~40 bytes ≈ 200 MB
查詢速度: O(1)，但 200 MB 可能超出快取上限
結果: 每次查詢都要 RAM 存取，延遲 ~100ns
選項 B：Bloom Filter（1% 誤判）
記憶體: ~6 MB（節省 97%）
查詢速度: O(k)，但全部在 CPU 快取內
結果: 查詢延遲 ~10ns（快 10 倍！）
代價: 1% 的 IP 會被誤判為黑名單（接到客服投訴時再用 HashSet 二次確認）
這就是 Bloom Filter 的典型應用場景——用 1% 的誤判率換取 97% 的記憶體節省和 10 倍的查詢速度。在系統設計面試中，這正是面試官想聽到的權衡取捨。
Bloom Filter 的著名使用者
- Cassandra：每個 SSTable 都有一個 Bloom Filter，跳過不包含查詢資料的檔案
- PostgreSQL：Visibility Map 類似 Bloom Filter 的概念
- Google Bigtable：每個 SSTable 使用 Bloom Filter 減少磁碟查找
- Redis：Redis Stack 提供原生 Bloom Filter 資料結構（
BF.ADD、BF.EXISTS） - Ethereum：輕錢用戶端使用 Bloom Filter 檢查交易日誌
- Medium：使用 Bloom Filter 向使用者推薦已讀過的內容
- GitHub：使用 BF 檢查貢獻者是否已簽署 CLA
何時不該用 Bloom Filter
- ✅ 當你必須保證 100% 準確時（銀行交易、醫療記錄）
- ✅ 當資料量很小，HashSet 完全吃得消時
- ✅ 當你需要列出所有儲存的元素時（BF 無法列舉）
- ✅ 當你需要刪除元素時（Counting BF 可解決但更複雜）
下章預告：HyperLogLog——另一種機率性資料結構
如果你覺得 Bloom Filter 用 1.2 MB 取代 50 MB 已經很神奇，那下一章的 HyperLogLog 會讓你更驚訝——它可以用 1.5 KB 的記憶體統計任意大小的集合中有多少個不同元素（例如今天的獨立訪客數 UV）。
Bloom Filter 回答的是「這個元素在不在集合中？」，HyperLogLog 回答的是「這個集合有多大？」。兩者都是大數據場景下的必備工具，但解決的是完全不同的問題。
準備好迎接下一章的基數估計魔法了嗎？