從散列表中刪除條目的最佳方法

Question

從使用線性探測的散列表中刪除條目的最佳方法是什麼？做到這一點的一種方法是使用標誌來指示刪除的元素？有沒有比這更好的方法？

Answer 1

一個簡單的方法是：

1. 查找並刪除所需的元素
2. 轉到下一個桶
3. 如果桶是空的，退出
4. 如果桶已滿，請刪除該桶中的元素並使用常規方法將其重新添加到散列表中。該物品在重新添加之前必須移除，因爲該物品可能會被添加回原來的位置。
5. 重複步驟2

這種技術讓您的桌子整潔的稍微慢一點的缺失爲代價的。

Answer 2

Python哈希表實現（可爭論非常快）使用虛擬元素來標記刪除。隨着你的成長或縮小或桌子（假設你沒有做一個固定大小的桌子），你可以同時放置假人。

如果您有權訪問副本，請參閱Beautiful Code中有關實施的文章。

Answer 3

最好的通用解決方案，我能想到的包括：

• 如果你可以使用一個非const迭代器（ALA C++ STL或Java），你應該能夠爲您遇到他們將其刪除。不過，大概你不會問這個問題，除非你使用了一個const迭代器或者一個枚舉器，如果底層集合被修改了，這個枚舉器將會失效。如你所說，你可以在包含的對象中標記一個已刪除的標誌。這不會釋放任何內存或減少密鑰上的衝突，所以它不是最好的解決方案。還需要在課堂上添加一個屬性，該屬性可能並不屬於此類。如果這會讓你感到困擾，或者你無法爲存儲的對象添加標誌（也許你不控制該類），那麼可以將這些標誌存儲在單獨的散列表中。這需要最長時間的記憶使用。
• 在遍歷散列表的同時，將要刪除的項目的鍵推入向量或數組列表中。釋放枚舉器後，循環訪問該輔助列表並從哈希表中刪除密鑰。如果你有很多項目要刪除和/或鑰匙很大（他們不應該），這可能不是最好的解決方案。
• 如果您最終要從哈希表中刪除比您要離開的項目更多的項目，最好創建一個新的哈希表，並且在遍歷原始哈希表時，添加新的哈希表表只有你要保留的物品。然後用新的哈希表替換你的引用。這樣可以節省次級列表迭代次數，但是如果新哈希表的項目比原始項目少得多，它可能只會有效，當然，只有當您可以更改對原始哈希表的所有引用時，它纔會有效。
• 如果您的散列表允許您訪問其密鑰集合，那麼您可以遍歷這些密鑰並從散列表中刪除項目。
• 如果您的庫中的哈希表或輔助程序爲您提供了基於謂詞的集合修飾符，則可以使用Remove（）函數，您可以將lambda表達式或函數指針傳遞給該函數以標識要刪除的項目。

Answer 4

這取決於你如何處理溢出，以及（1）被移除的項目是否在溢出槽中，以及（2）如果溢出項目被移出項目之外，是否它們具有散列該項目的鍵被刪除或可能是其他一些散列鍵。 [忽略雙倍情況是刪除實現中的錯誤的常見原因。]

如果碰撞溢出到鏈表中，這很容易。您要麼彈出列表（可能已空）或從鏈接列表的中間或末尾刪除成員。這些很有趣，並不特別困難。可以進行其他優化以避免過多的內存分配和釋放，從而使其效率更高。

對於線性探測，Knuth建議一種簡單的方法是將槽標記爲空，刪除或佔用。將已移除的乘員槽標記爲已刪除，以便通過線性探測的溢出將跳過它，但是如果需要插入，則可以填寫您通過的第一個已刪除的插槽[The Art of Computer Programming，vol.3：Sorting and Searching ，第6.4節散列，p。 533（ed.2）]。這假定刪除是非常罕見的。

Knuth給出了一個很好的改進算法R6.4 [pp。 533-534]，而是將單元格標記爲空而不是刪除，然後找到方法將表格條目移回距離初始探針位置較近的位置，方法是移動剛創建的孔直到最後一個孔結束。

Knuth警告說，這將移動現有的仍被佔用的插槽條目，如果指向插槽的指針被保存在哈希表的外部，這不是一個好主意。 [如果在插槽中有垃圾回收或其他管理引用，移動插槽就可以了，因爲它是在表格外使用的引用，並且引用的插槽位置並不重要同一個對象在表中。]

Answer 5

當時間是一個因素時，常見的技術是創建第二個已刪除項目表，並在有空時清理主表。常用於搜索引擎。

Answer 6

如何增強散列表以包含像鏈接列表這樣的指針？ 插入時，如果存儲區已滿，請從此存儲區創建一個指針到存儲新字段的存儲區中。

雖然從散列表中刪除某些東西，但解決方案將等同於您如何編寫函數以從鏈接列表中刪除節點。