題干與適用場景
Cuckoo Filter 是一種近似成員查詢結構：查詢返回 false 時可以判定不存在，返回 true 只表示可能存在。與標準 Bloom Filter 相比，它用桶中的短指紋支援刪除與相對靈活的查詢；代價是插入可能需要搬遷，接近裝滿時可能失敗。題目適合考察雜湊、陣列布局、隨機化、邊界處理與基準測試。
面試官考察什麼
- 是否能解釋指紋與兩個候選桶的關係，而不是只背名稱。
- 是否保證 remove 不製造 false negative，並限制搬遷避免無限迴圈。
- 是否能處理重複插入、重複刪除、桶滿、雜湊碰撞與並發邊界。
- 是否能根據容量、指紋位數與誤判目標選擇參數並驗證結果。
回答前需要釐清的問題
先確認預計元素數、單桶槽位數、可接受誤判率與記憶體預算。是否要求刪除、持久化、並發寫入或穩定結果？元素能否編碼成穩定位元組串，雜湊種子是否跨版本固定？插入失敗時是擴容重建、切換分層過濾器，還是允許呼叫方回源？查詢的 false positive 會帶來多少後端成本？
30 秒回答框架
我會為每個值產生非零指紋 f 與主桶索引 i1，用指紋再計算候選桶 i2，讓同一指紋只可能位於兩個桶。查詢檢查兩個桶是否有 f；刪除只清除匹配指紋，因此不會像普通 Bloom Filter 那樣清除共享位元。插入先放入任一有空槽的桶，否則執行有限次隨機搬遷；達到上限就回報失敗並觸發擴容或分層。指紋長度、桶容量與最大負載需要透過誤判率、插入成功率與延遲測試校準。
分步驟深入解答
1. 定義介面與不變量
add(x) 成功後，指紋必須存在於兩個候選桶之一；mightContain(x) 只在兩個桶都找不到指紋時返回 false；remove(x) 只能刪除匹配指紋。若多個值共享同一指紋，刪除其中一個可能讓另一個仍返回 true，這是可接受的 false positive，但不能讓已插入值返回 false。
2. 產生指紋與候選桶
用穩定編碼計算主索引 i1，再取固定長度的非零指紋 f。透過 i2 = i1 XOR hash(f) 得到第二個桶，並對桶數取模。索引與指紋的計算必須固定雜湊演算法、種子、端序與版本；否則持久化資料或擴容遷移時會找不到舊項目。指紋太短會提高誤判率，太長會增加記憶體。
3. 設計桶布局與查詢
每個桶保存固定數量的指紋槽位，而不是完整元素。查詢只讀取 i1 與 i2，任一桶包含 f 就返回可能存在。桶容量影響負載上限與區域碰撞；可以用連續陣列減少指標開銷，並記錄桶數、槽位數、指紋位數與雜湊版本。
4. 處理插入與有界搬遷
插入先嘗試兩個候選桶的空槽。若都滿，隨機選擇一個桶和槽位，交換出舊指紋，再把舊指紋放入它的另一個候選桶。重複搬遷必須有最大次數或訪問桶標記，達到上限就失敗；不能無限迴圈。隨機源、搬遷計數與失敗原因應可觀測，便於判斷負載過高還是雜湊分布異常。
5. 實作刪除與重複操作
刪除只在兩個候選桶中尋找匹配指紋並清空一個槽位。若呼叫方需要嚴格的元素級刪除語義，短指紋可能產生碰撞，應在權威儲存中二次確認，或使用更長指紋。remove 對不存在值應具冪等性；重複 add 是否佔用新槽位要先定義，通常可選擇允許重複或檢測同指紋後不重複寫入。
6. 測試、失敗與擴容
測試必須驗證已插入值不出現 false negative、隨機缺失值的 false positive、刪除後的行為、重複操作、滿桶搬遷與確定性序列。記錄負載因子、搬遷失敗率、查詢延遲與記憶體使用。失敗達到閾值時擴容並重新插入全部項目，或新增一層過濾器；擴容過程要保留舊快照，避免查詢窗口出現遺失。
高品質示範回答
我會產生穩定的非零指紋 f 與主桶 i1，再用 i2 = i1 XOR hash(f) 得到第二候選桶；每個桶保存固定數量的指紋。查詢檢查兩個桶，找不到 f 才返回 false。刪除只清除匹配指紋，因此不會像普通 Bloom Filter 一樣清除共享位元；如果短指紋碰撞帶來業務風險，就用權威儲存複核。插入先試兩個桶，滿了就隨機搬遷並設定最大次數，超過上限返回失敗。實作固定編碼、雜湊種子、桶數、槽位與版本，處理重複操作並提供冪等刪除。測試已插入值不漏報、缺失樣本誤判率、刪除、滿桶、搬遷失敗與並發邊界；當負載或失敗率超過閾值時擴容重建或切換分層過濾器。
常見錯誤
- 把 Cuckoo Filter 當作精確集合，忽略 false positive。
- 只保存一個桶索引，無法根據被搬遷的指紋找到另一候選桶。
- 搬遷沒有上限，遇到環時無限迴圈或阻塞請求。
- 指紋可以為零，導致空槽與真實指紋無法區分。
- 刪除時清除整個桶或錯誤槽位，製造 false negative。
- 忽略重複操作、持久化版本、擴容期間的雙讀與插入失敗。
追問及應對
Cuckoo Filter 為什麼能支援刪除而 Bloom Filter 預設不能？
Cuckoo Filter 刪除的是某個桶中的指紋槽位；Bloom Filter 的一個位元可能由多個元素共享，直接清除會誤傷其他元素。兩者都允許 false positive，嚴格刪除仍需考慮指紋碰撞。
如何選擇指紋長度與桶容量？
先給出元素數、目標誤判率、記憶體與負載目標，再用理論估算確定指紋位數與桶槽位，最後用真實分布壓測。指紋越長誤判越低但空間越大，桶越寬可能提升裝載率卻增加掃描成本。
搬遷達到上限時直接丟棄新元素可以嗎？
只能把失敗作為明確結果返回，不能假裝插入成功。呼叫方可重建更大的過濾器、寫入下一層或回源保存；線上應監控失敗率與負載，避免靜默漏掉成員。
多執行緒如何保證查詢與刪除一致？
需要定義快照或鎖語義：讀寫槽位應使用原子更新、分片鎖或不可變快照切換。刪除與查詢並發時，呼叫方必須接受瞬時 false positive 或明確線性化要求，不能只依賴普通記憶體讀寫。