布隆過濾器 (Bloom Filter)#
布隆過濾器是一種空間效率極高的概率型資料結構，用於快速判斷元素「是否可能存在」。
與快取的關係#
| 機制 | 功能 | 特點 |
|---|---|---|
| Cache | 儲存熱點資料，加速讀取 | 確定性 |
| Filter | 判斷元素「在不在」 | 概率性 |
核心特性
- 說「不在」：100% 準確
- 說「在」：可能誤判（False Positive）
工作原理#
結構#
- 一個長度為 m 的二進位陣列，初始全為 0
- K 個獨立的雜湊函式
寫入操作#
將元素經過 K 個雜湊函式計算，得到 K 個位置，將對應位元設為 1。
查詢操作#
將元素經過相同的 K 個雜湊函式計算：
- 若任一位置為 0 → 肯定不存在
- 若所有位置都為 1 → 可能存在（需二次確認）
誤判案例說明
假設已插入 A 和 E：
- 插入 A：設置位置 [1, 2]
- 插入 E：設置位置 [3, 4]
查詢 B，假設 B 對映到 [1, 3]：
- 位置 1 被 A 設為 1
- 位置 3 被 E 設為 1
- 系統判斷「B 存在」→ 誤判
這就是為什麼布隆過濾器只能作為「過濾器」而非「資料儲存」。
優缺點#
優點#
- 極高空間效率：不儲存原始資料，只存 0/1
- 極快查詢速度：位元運算，O(K) 時間複雜度
缺點#
- 刪除困難：多個元素可能共享同一位元
- 存在誤識別率：需要後端二次確認
布隆過濾器無法刪除元素。如需支援刪除，可考慮使用 Counting Bloom Filter（每個位置用計數器代替單一位元）。
實際應用#
1. 比特幣網路 (SPV 節點)#
輕量級用戶端使用布隆過濾器快速判斷交易是否在某區塊中：
- Filter 返回「不存在」→ 跳過該區塊
- Filter 返回「存在」→ 下載區塊詳細確認
2. 防止快取穿透#
在 Redis 前加一層布隆過濾器：
- Key 不在 Filter → 直接返回空（攔截惡意查詢）
- Key 在 Filter → 查詢 Redis/DB
3. 分散式系統#
判斷資料是否在某節點上，減少無謂的網路請求。
參數設計#
誤判率與以下因素相關：
- m：位陣列長度（越大誤判率越低）
- k：雜湊函式數量（需適當平衡）
- n：預期插入元素數量
常用經驗公式：
- 最佳 k = (m/n) * ln(2)
- 10 億元素，10 倍大小位圖（100 億位元 ≈ 1.2GB），誤判率約 1%