題幹與適用場景
請實作支援批次建構與 membership 查詢的靜態 Xor Filter。要求解釋三段雜湊配置、peeling 佇列、指紋回填、建構失敗重試、誤判率，以及不支援原地刪除的原因。
Xor Filter 是靜態 approximate membership query 結構：它為每個 key 儲存短指紋，查詢時對三個位置的指紋做 XOR。論文顯示它可在空間和查詢速度上與 Bloom、Cuckoo Filter 競爭，但建構依賴隨機雜湊超圖可剝離，失敗時需要換 seed 重建；它適合批次產生後唯讀發布。
面試官考察點
面試官會看你能否正確建構三段陣列、處理重複 key 和空集合；能否用度數佇列剝離超圖並逆序回填；能否保持查詢與建構使用同一指紋函式；能否計算誤判機率、識別刪除與動態更新限制；能否解釋失敗重試、記憶體占用與並行讀取安全。
回答前需要釐清的問題
資料集與更新模型
確認 key 數量、是否允許重複、是否批次重建、更新延遲和是否必須支援刪除。Xor Filter 預設面向靜態集合，動態場景應比較 Cuckoo Filter 或分層重建。
誤判與空間目標
確認可接受的 false positive rate、指紋位元數、是否允許 false negative，以及查詢吞吐與建構峰值記憶體的優先順序。
key 與雜湊邊界
確認 key 是整數、位元組串還是結構化物件，雜湊 seed 如何持久化，跨語言實作是否要求位元組序與正規化一致。
30 秒回答框架
「我把陣列切成三段，每個 key 的三個雜湊位置各落在一段，儲存固定寬度指紋。建構時記錄每個位置的度數與關聯邊，把度數為 1 的邊放入佇列並 peeling；若剩餘邊無法剝離就更換 seed 重建。按逆序取出邊，用三個位置的現有值 XOR 出該邊指紋。查詢重新計算三位置並 XOR，等於 key 指紋就回傳可能存在。結構靜態且允許誤判，不提供原地刪除。」
分步驟深入解答
第一步：定義配置與指紋
用兩個獨立的 64 位元雜湊結果派生三個位置和一個低位指紋。把表分成大小近似的三段，位置函式在各自段內取模；指紋不能為零時要統一約定零值處理，避免空槽與真實指紋混淆。
第二步：建立超圖度數
每個 key 是連接三個槽位的超邊。建構階段為每個槽位記錄度數和關聯邊列表，度數為 1 的槽位進入佇列。重複 key 必須先去重或明確按同一集合元素處理，否則同一超邊會被重複計數。
第三步：執行 peeling
從佇列取出度數為 1 的槽位，找到唯一關聯邊並記錄「邊、唯一槽位、其餘兩個槽位」。移除該邊後遞減三個槽位的度數，新的度數為 1 的槽位繼續入隊。若處理完佇列仍有未移除邊，表示本輪雜湊圖不可剝離。
第四步：逆序回填指紋
按照 peeling 記錄的逆序處理每條邊。目標槽位的值設為 key 指紋與另外兩個槽位目前值的 XOR。這樣三槽位 XOR 後恰好得到該 key 指紋；尚未寫入的槽位按零值參與計算。
第五步：實作查詢
查詢使用與建構相同的 seed、位置函式和指紋函式，讀取三段槽位並 XOR。結果相等只能說明「可能存在」，不能證明 key 在集合中；呼叫方需要用資料庫或精確集合處理誤判。
build(keys):
repeat with a new seed:
edges = positions_and_fingerprints(keys, seed)
queue = all degree-1 slots
order = peel(edges, queue)
if order contains every edge:
table = zeroed slots
for edge in reverse(order):
table[edge.unique] = edge.fp XOR table[edge.other1] XOR table[edge.other2]
return seed, table
fail after bounded retries
contains(key):
a, b, c = positions(key, seed)
return table[a] XOR table[b] XOR table[c] == fingerprint(key)第六步：處理失敗與資源
建構失敗不是查詢 false negative，而是目前 seed 下的圖沒有可剝離順序。限制重試次數，改變 seed 或表大小；達到上限時回傳明確錯誤，不發布半成品。建構保留度數、邊列表和 peeling stack，峰值記憶體通常高於最終唯讀表。
第七步：說明更新與驗證
Xor Filter 的表是由全體 key 聯合求解，任意插入或刪除都可能破壞其他 key 的 XOR 關係。更新採重新建構、雙版本切換或增量小表疊加。測試空集合、單 key、重複 key、極端雜湊碰撞、建構失敗、序列化恢復、誤判率和並行唯讀查詢。
高品質示範回答
我會將 key 集合映射成三段槽位組成的 3-uniform 超圖，先用度數佇列 peeling，成功後逆序回填短指紋。查詢只做三次取槽和 XOR，因此是常數時間，但結果是 approximate membership。建構失敗表示目前 seed 的圖不可剝離，我會更換 seed 並限制重試，超過上限就拒絕發布。表依賴全體 key，不能安全原地刪除或插入；生產更新採新表建構後原子切換。seed、表大小、指紋寬度和位元組序都要隨版本持久化，並用精確集合測量 false positive rate。
常見錯誤
- 錯誤表現： 建構失敗時直接回傳部分表。→ 失敗原因： 未處理的邊會造成 false negative。→ 修正方法： 失敗即換 seed 或表大小，成功覆蓋全部邊後才發布。
- 錯誤表現： 查詢使用不同的 seed 或位置分段。→ 失敗原因： 建構與查詢的槽位不一致。→ 修正方法： 序列化並鎖定 seed、段邊界和雜湊版本。
- 錯誤表現： 把查詢結果當成精確存在性。→ 失敗原因： 短指紋會產生 false positive。→ 修正方法： 將 filter 作為前置篩選，命中後再查精確儲存。
- 錯誤表現： 支援原地刪除。→ 失敗原因： 一個槽位被多個 key 共用，修改會破壞其他 XOR 方程。→ 修正方法： 使用重建、雙版本或選擇動態過濾器。
追問及應對
為什麼需要三段而不是一個陣列？
三段配置讓每條邊從固定的三個區域各取一個槽位，便於構造可剝離超圖和常數次查詢；實際比例與裝載因子要透過基準測試確定。
如何選擇指紋位元數？
指紋越短，空間越小但誤判率越高。用獨立未命中 key 的實驗測量誤判率，再結合業務對後端精確查詢的成本選擇位元數。
重試 seed 會不會讓結果不穩定？
表內容會變化，但只要把最終 seed、版本和表一起持久化，查詢結果可重現。發布流程應把建構中繼資料寫入同一版本清單。
什麼時候改用 Bloom 或 Cuckoo Filter？
需要頻繁插入、刪除、計數或線上擴容時，動態過濾器更合適。Xor Filter 的優勢在靜態批次建構後的空間和查詢效率。