題目與適用場景
請實作 Bloom Filter，提供 add(value) 和 mightContain(value)。它適合在昂貴查詢前做預過濾：回傳「不存在」時必須可信，回傳「可能存在」時允許再查一次資料庫。回答需涵蓋 n、p、m、k 的關係，以及刪除、擴容、並行與測試。
面試官考察重點
語意是否正確
標準 Bloom Filter 允許 false positive，不允許 false negative。mightContain 的命名應提醒呼叫方：true 不是存在證明。
參數是否能解釋
位元陣列長度 m 和雜湊數量 k 會影響空間、速度與誤判率。應先確認容量與可接受 p，再給出公式。
邊界是否完整
候選人要主動說明標準結構不能安全刪除單一元素，裝滿後誤判率會上升，擴容需要重建或分層結構。
回答前要釐清的問題
- 預計插入多少元素，目標誤判率 p 是多少？
- 值是否能序列化成穩定位元組串，跨程序雜湊是否需一致？
- 過濾器是否只追加，還是必須支援刪除與更新？
- 記憶體預算、查詢延遲與並行寫入上限是多少？
- 裝滿後要拒絕寫入、重建，還是切換到分層過濾器？
- false positive 造成的後端查詢成本如何監控？
30 秒回答框架
「我會用 m 位元陣列和 k 個獨立性足夠的雜湊位置。add 把 k 個位置設為 1；查詢只要一個位置為 0，就能斷言不存在，否則回傳可能存在。給定 n 與 p，m=-n ln(p)/(ln2)^2，k=(m/n)ln2。標準結構不能刪除，容量變化要重建或分層；測試會涵蓋已插入值、誤判率與並行約束。」
分步深入解答
先寫出不變量與介面
位元陣列初始全為 0。每個值由穩定雜湊函式產生 k 個索引；插入只會把索引設為 1。查詢遇到 0，就能證明這個值沒有被這組雜湊寫入。
計算 m 與 k
預估 n 個元素、誤判率 p 時，近似公式為 m = -n ln(p) / (ln(2)^2)，k = (m/n) ln(2)。例如 n=1,000,000、p=1% 時，m 約 9.6M bits（約 1.14 MiB），k 約 7。
處理雜湊與位元操作
可用雙重雜湊：h_i(x) = h1(x) + i*h2(x)，再對 m 取模，避免維護 k 套完整雜湊函式。必須固定位元組編碼、端序與種子；跨版本改變會讓舊過濾器失效。
說明刪除與擴容
單一位元可能由多個值共用，直接清零會製造 false negative。因此標準 Bloom Filter 不支援安全刪除。需要刪除可採 Counting Bloom Filter，但每個桶更耗空間。容量增長後應重建更大的過濾器，或使用按容量分層的過濾器。
處理並行與生命週期
並行讀通常安全；並行寫至少要保證設定位元不會遺失，分片位元陣列、原子 OR 或寫鎖都可選。過濾器應和容量、雜湊種子及版本一起持久化，重啟不能悄悄換參數。
偽程式碼
~~~text add(x): for i in 0..k-1: bits[index(hash1(x), hash2(x), i)] = 1
mightContain(x): for i in 0..k-1: if bits[index(hash1(x), hash2(x), i)] == 0: return false return true ~~~
複雜度與驗證
每次 add 與查詢存取 k 個位置，時間是 O(k)，額外空間是 O(m)。測試至少包括已插入值都回傳 true、隨機未插入樣本統計 false positive、接近容量時觀察誤判率，以及空過濾器、重複插入和並行寫入。
| 操作 | 保證 | 複雜度 |
|---|---|---|
add(x) | 只設定位元，不移除資訊 | O(k) |
mightContain(x) | false 表示確定不存在，true 表示可能存在 | O(k) |
| 擴容 | 重建或增加分層過濾器 | 依元素數與 m 而定 |
高品質示範回答
「Bloom Filter 是機率型成員預過濾器。我會維護 m 位元陣列與 k 個位置函式。插入時把 k 位設為 1；查詢出現任意 0 就回傳 false，否則回傳 true，但把 true 解讀為『可能存在』，交給後端資料源最終確認。m 與 k 依 n 與 p 計算，100 萬元素、1% 誤判率約需 9.6M bits、7 個位置。標準版本不能刪除，因共享位元無法知道由誰設定；刪除需求用 Counting Bloom Filter，容量增長則重建或分層。我會固定編碼與雜湊種子，測試已插入值不漏報並量測缺失樣本誤判率。」
常見錯誤
把 true 當成存在證明
true 只表示所有對應位元都是 1，其他值也可能碰巧設過這些位元。呼叫方仍需存取權威資料源。
只使用一個雜湊函式
單一雜湊會讓位元分布和誤判率偏離設計目標。可用雙重雜湊產生 k 個位置，並說明種子與碰撞假設。
直接清除刪除值的位元
共享位元被清零會讓其他已插入值回傳 false。刪除必須改用計數桶或重建過濾器。
忽略容量飽和
持續插入會讓更多位元變成 1，誤判率上升。應記錄元素估計量與設定位元比例，在閾值前擴容。
只測成功路徑
沒有缺失樣本、邊界容量與重複插入測試，就無法驗證誤判率與參數選擇。
追問與應對
為什麼不能保證 false positive 為零？
不同值可能映射到同一組位元；有限陣列必然存在碰撞。空間越大、k 越合適，誤判率越低但成本越高。
何時使用 Cuckoo Filter？
需要刪除、較高查詢彈性或保存指紋時可比較 Cuckoo Filter；仍應依記憶體、寫入與刪除需求做基準測試。
如何做持久化？
保存位元陣列、m、k、雜湊演算法、種子、編碼版本與容量估計。載入時驗證版本，避免不同參數讀取同一陣列。
如何監控品質？
統計後端確認的 false positive、設定位元比例、估計元素數、查詢延遲與重建次數；超過閾值就擴容或重建。
誤判率公式的前提是什麼？
公式假設雜湊分布近似均勻、插入量接近 n 且位置獨立性足夠。真實資料要用抽樣實驗校準。
多執行緒如何避免寫遺失？
位元陣列採用原子設定位元或分片鎖；讀路徑要看到完整寫入。若允許最終一致，可批次合併後發布新快照。