哈希表：什麼是標記一個空桶的最佳方式？

Question

進入一個惱人的問題 - 我需要一些方法來判斷我試圖填充的桶是否爲空（桶被存儲爲鍵值對的值類型結構數組）。

如果我要保留一個空值標記的關鍵值，那麼這就意味着某些不幸絆倒該散列值的數據將永遠無法訪問。另一方面，在KVP結構中包含一個布爾值會將結構的大小從16增加到24，（這很浪費，而且我對內存很緊張）。有沒有人想出了一個很好的解決方案呢？

Answer 1

這是散列表與碰撞一樣固有的問題。一個相關的問題是在碰撞的情況下再次處理從散列表中刪除。沒有任何解決方案不涉及性能方面的妥協，所以通常會看到散列表實現具有非法的特定密鑰。

到目前爲止，最直接的解決方案是特殊情況下，您使用的關鍵值是空的。也就是說，如果用戶正在嘗試存儲鍵值0，則只需將其放入一個特殊數組中即可。

只有指針才能工作的真正蹩腳的散列表通常不會遇到此問題，因爲您始終可以找到調用方無法傳遞的指針值（例如指向您擁有的對象的指針）。很明顯，使用鏈表或數組元素的哈希表也沒有這個問題，但是，這對於那些人來說會有一個巨大的性能損失。

你或許可以找到一些聰明的方法，通過使用多個元素在表格本身內進行編碼。唯一的方法是更好的是，如果它以某種方式與刪除的元素處理或其他內容相統一，那麼它將比檢查一些單獨的列表免費或更快。