程式設計面試：如何實作 Robin Hood Hashing？
題幹與適用場景
實作一個固定容量的開放定址雜湊表，槽位陣列長度為 m，每個槽最多存放一個鍵值對。要求支援 insert(key,value)、contains(key) 和 remove(key)；碰撞處理使用 Robin Hood Hashing，不使用鏈結串列，也不使用 tombstone。為了聚焦核心演算法，本題先假設容量不足時回傳失敗，不負責擴容。
這是一道通用程式設計面試題，核心考察資料結構、不變量、邊界測試和複雜度推導。Stanford CS106B 的公開作業要求學生實作 Robin Hood 表，並明確包含「按探測距離交換」、「提前結束查找」和「向後移動刪除」三個差異點。目前的軟體工程面試指南也把資料結構選擇、正確性、複雜度和邊界處理列為程式碼面試的評估訊號。
面試官考察點
- 能否把每個元素的 home bucket 與 PSL（probe sequence length，探測序列長度）存進槽位。
- 能否說明插入時「更窮者優先」：目前元素 PSL 較大時，與較接近 home 的駐留元素交換。
- 能否用 PSL 單調性提前結束失敗查找，而不是無條件掃描整個陣列。
- 能否不用 tombstone 刪除，同時保持同一探測叢集中的查找可達。
- 能否給出平均、最壞複雜度，並說明高負載時延遲和失敗策略。
普通回答會寫出線性探測，卻遺漏刪除後空洞會截斷查找；強回答會把「槽位為空」與「槽位 PSL 小於待查元素 PSL」都變成可證明的停止條件。
回答前需要釐清的問題
- 容量是否固定？固定容量時插入失敗必須是明確結果；允許擴容則需要在負載因子閾值觸發重建。
- 是否允許重複鍵？本題假設重複鍵更新 value，不新增槽位；如果要多值映射，應改變 API 和刪除語意。
- 雜湊函式是否穩定、鍵是否可複製？雜湊結果必須在一次操作中穩定；若雜湊昂貴，可以快取 home bucket，但會增加槽位記憶體。
- 是否要求迭代器或參照穩定？向後移動會搬遷元素，因此不能承諾位址穩定；如果需要穩定參照，應使用間接儲存或鏈式結構。
- 並行是否在範圍內？本題是單執行緒；並行版本需要鎖、分段或無鎖協定，不能把普通實作直接宣稱執行緒安全。
30 秒回答框架
「我會在每個槽位保存 key、value、home bucket 和 PSL。插入從 home bucket 線性探測；如果目前元素的 PSL 大於槽內元素，就交換兩者，讓探測更遠的元素先佔據位置，然後繼續安置被換出的元素。查找遇到空槽，或遇到槽內 PSL 小於目標 PSL 時可以提前失敗，因為後續元素不可能跳回更近的位置。刪除後從下一個槽開始向後搬移，直到遇到空槽或 PSL 為零的元素，逐個把 PSL 減一，避免留下會截斷探測叢集的空洞。平均操作接近 O(1)，最壞仍是 O(m)，空間 O(m)。 」
分步驟深入解答
1. 槽位模型與不變量
每個非空槽保存 (key, value, home, psl)。在容量為 m 的環形陣列中，psl = (index - home + m) % m。必須維護三個不變量：
home是該鍵雜湊後的固定起點。- 從
home沿環向前走psl步正好到達目前 index。 - 同一連續探測叢集內，非空槽的 PSL 不遞減；空槽會結束該叢集。
第三條不變量來自插入時的「更大 PSL 優先」交換。它讓查找可以比較目標 PSL 與目前槽 PSL，而不必檢查後面的所有槽位。
2. 線性探測插入的瓶頸
最簡單的線性探測會從 home 向後找空槽。高負載時，早到的元素可能佔據離 home 很近的位置，晚到且已探測很遠的元素被迫繼續走很長距離；探測長度的方差會拉高尾端延遲。Robin Hood 策略不改變開放定址的陣列布局，只在碰撞時把更遠的元素優先安置。
3. Robin Hood 插入
虛擬碼如下：
insert(key, value):
item = (key, value, home=hash(key), psl=0)
for step in 0 .. m-1:
i = (item.home + item.psl) mod m
if table[i] is empty:
table[i] = item
return success
if table[i].key == key:
table[i].value = value
return updated
if table[i].psl < item.psl:
swap(table[i], item)
item.psl += 1
return full交換後繼續迴圈時，item 是被趕出的元素；它的 PSL 已經對應目前探測位置，下一輪再加一。實作中要避免把「空槽」當成 PSL 為零的元素，否則首次插入和刪除邊界會混淆。
4. 查找與提前終止
查找從目標 home 開始，維護目標 PSL：
contains(key):
home = hash(key)
for psl in 0 .. m-1:
i = (home + psl) mod m
if table[i] is empty:
return false
if table[i].psl < psl:
return false
if table[i].key == key:
return true
return false如果目前槽為空，探測叢集已經結束；如果目前槽 PSL 小於目標 PSL，後續槽位的 PSL 不會下降到能容納目標的位置，因此目標不存在。Stanford 作業把這個提前結束條件列為 Robin Hood 與普通線性探測的核心差異之一。
5. 向後移動刪除
不能直接把槽清空：後面的鍵可能是跨過該槽碰撞後放入的，查找會在空洞處錯誤回傳 false。也不能使用 tombstone，因為題目明確禁止，且長期 tombstone 會拉長探測。
remove(key):
i = find_index_or_not_found(key)
if i is not found:
return false
j = (i + 1) mod m
while table[j] is not empty and table[j].psl > 0:
table[i] = table[j]
table[i].psl -= 1
i = j
j = (j + 1) mod m
table[i] = empty
return true遇到空槽或 PSL 為零的元素就停止：前者代表叢集結束，後者說明該元素就在自己的 home，刪除前面的空位不會截斷它的查找路徑。每次搬移都把 PSL 減一，恢復「目前位置距離 home 一步變短」的不變量。
6. 複雜度與高負載決策
在均勻雜湊和負載因子 α 遠低於 1 時，插入、查找和刪除的期望探測次數為常數級；單次操作最壞可能掃描全部 m 個槽，因此最壞時間是 O(m)，空間是 O(m)。Robin Hood 主要改善探測長度的分布和方差，不改變開放定址的最壞上界。論文分析了高負載下搜尋成本方差仍可保持有界的情形，但工程實作仍應設負載閾值。
當 α 接近閾值時，優先擴容重建，而不是繼續依賴平均 O(1)。如果必須固定容量，應把 full 作為正常業務結果，並監控失敗率、平均 PSL、P99 探測次數和刪除搬移長度。
7. 反例與測試
- 空表插入和查找：確認 home 槽直接放入，查找不存在鍵遇到空槽立即失敗。
- 重複鍵：插入同一 key 只更新 value，元素數量不增加。
- 環形回繞：讓 home 接近陣列尾部，驗證
(index - home + m) % m正確。 - 交換鏈：構造多個碰撞鍵，確認一次插入可連續交換並最終放置所有元素。
- 刪除叢集頭、中間和尾部：每次刪除後檢查原叢集中所有剩餘鍵仍可找到。
- 刪除 home 元素：後繼 PSL 為零時停止搬移，避免把另一叢集錯誤搬進來。
- 滿表：插入第
m+1個不同鍵必須回傳失敗，不能無限迴圈。 - 對抗雜湊：讓大量鍵映射同一 home，確認結果仍正確，且監控能暴露 O(m) 探測。
高品質示範回答
「我會使用固定容量的 Robin Hood 開放定址表，每個非空槽保存鍵值和 PSL。插入時從 home 開始線性探測；目前元素如果比槽內元素離 home 更遠，就交換兩者，繼續安置被換出的元素。這樣一個探測叢集裡的 PSL 保持不遞減。
「查找可以利用這個不變量：遇到空槽直接失敗，遇到槽內 PSL 小於目標 PSL 也失敗，因為後續不會回到更近的距離。刪除不能留下空洞，所以我從刪除點向後搬移 PSL 大於零的元素，並將其 PSL 減一；遇到空槽或 PSL 為零就停止。平均時間接近 O(1)，但最壞是 O(m)，所以我會用負載因子、P99 探測和搬移長度決定擴容或拒絕插入。向後移動會改變元素位址，因此我不會承諾穩定迭代器或參照。」
常見錯誤
- 錯誤表現 → 碰撞時永遠讓先到元素留下 → 後到元素探測距離無限拉長 → 當新元素 PSL 較大時交換。
- 錯誤表現 → 查找只在空槽時失敗 → 失去 PSL 單調性的最佳化 → 目前槽 PSL 小於目標時也應停止。
- 錯誤表現 → 刪除後直接清空槽位 → 空洞截斷後繼鍵的探測路徑 → 使用向後移動並逐步減小 PSL。
- 錯誤表現 → 刪除搬到遇到任意元素就停 → 可能留下無法到達的鍵或跨叢集搬移 → 只搬移連續叢集中 PSL 大於零的元素。
- 錯誤表現 → 把平均 O(1) 寫成最壞 O(1) → 高負載或壞雜湊時結論失真 → 明確最壞 O(m)，並設定負載閾值。
- 錯誤表現 → 承諾參照位址穩定 → 交換和刪除會搬遷元素 → 返回句柄、間接指標或放棄位址穩定承諾。
追問及應對
如果要求動態擴容，什麼時候觸發重建？
按負載因子和探測尾端延遲共同觸發，例如達到預設 α 或 P99 探測超過預算時擴容到更大的陣列。重建時重新計算所有 home 和 PSL，不能直接複製槽位，因為陣列模數改變。擴容期間可用寫入鎖、雙表遷移或背景重建，但要先說明一致性和暫停寫入策略。
為什麼不用 tombstone，向後移動的成本會不會太高？
tombstone 讓刪除 O(1)，但會永久增加查找路徑，除非定期重建；向後移動把成本集中在刪除操作，並保持叢集緊湊。刪除頻率極高、讀取很少時 tombstone 加週期性重建可能更合適；讀取延遲敏感時優先向後移動，並監控單次搬移長度。
並行讀寫怎樣處理？
這份實作是單執行緒。最簡單的並行方案是讀寫鎖，但寫入交換和刪除搬移必須在一個寫入臨界區內完成，讀者不能看到半完成叢集。更高吞吐可以分段加鎖或使用不可變快照；無鎖版本需要版本字、記憶體序和回收協定，不能只給槽位加原子指標就宣稱正確。
Robin Hood 會讓平均查找次數變成常數嗎？
在常見均勻雜湊模型下，開放定址的期望探測成本與負載因子有關，Robin Hood 的主要收益是降低探測長度方差和尾部波動。高負載時平均成本仍會上升，最壞仍可能掃描整個表；因此不能用「方差更小」替代負載控制和實測基準。