布隆過濾器 (Bloom Filter)

引言：「可能」機器

假設你想知道一個使用者名稱是否在 10 億個已註冊使用者中被佔用。

• 雜湊表： 需要 20GB+ 記憶體。太貴了。
• 布隆過濾器： 只需要 100MB。雖然它有時會誤報（當使用者不存在時說「存在」），但如果它說「不存在」，那就 100% 確定不存在。

布隆過濾器 是一種節省空間的概率型資料結構，專門用於測試一個元素是否屬於一個集合。

演算法要解決什麼問題？

• 輸入： 一個元素。
• 輸出： False (絕對不在) 或 True (可能在)。
• 承諾： 在成員判定任務中實現海量的記憶體節省。

核心思想 (直覺版)

想像一個長度為 $M$ 的 位元陣列 (Bit Array)，初始全是 0。

1. 添加元素： 將元素透過 $K$ 個不同的雜湊函數。每個雜湊函數會給你一個索引。將位元陣列中這 $K$ 個索引位置全部設為 1。
2. 查詢元素： 同樣使用這 $K$ 個雜湊函數計算索引。
   • 如果 任何一個 位置是 0：該元素 絕對 沒有被添加過。
   • 如果 全部 位置都是 1：該元素 可能 被添加過（也可能是其他元素的雜湊值碰巧湊齊了這幾個 1）。

為什麼要用它？

它充當 昂貴操作 前面的 廉價過濾器。

• 先查布隆過濾器。
• 如果結果是「不在」：跳過昂貴的資料庫/磁碟查詢。
• 如果結果是「在」：再執行昂貴的查詢以進行確認。

典型業務場景

• ✅ 弱密碼檢測： 檢查使用者密碼是否在包含 1000 萬個洩漏密碼的黑名單中，而無需將黑名單全部加載到記憶體。

• ✅ 惡意網址攔截： Google Chrome 使用它快速檢查 URL 是否為已知的惡意網站。

• ✅ 資料庫性能最佳化： Cassandra 和 BigTable 使用它來避免在磁碟上搜尋不存在的行鍵。

• ✅ CDN 快取過濾： 只有當一個資源被請求過至少一次後才進行快取（防止「一過性」流量浪費快取空間）。

• ❌ 刪除： 標準布隆過濾器 不支援刪除。如果你把某個位元設回 0，可能會誤刪其他共享該位元的元素。如果需要刪除，請使用 計數布隆過濾器 (Counting Bloom Filter)。

性能與複雜度總結

• 時間： $O(K)$，$K$ 是雜湊函數的個數（常數級）。
• 空間： $O(M)$，$M$ 是位元陣列的大小。通常 1% 誤報率下每個元素只需約 10 個位元位。

小結：一句話記住它

「布隆過濾器是終極保鏢。它能瞬間告訴你誰肯定『不在名單上』，讓你免於在整個夜店裡尋找那些根本沒來的人。」