從HashTable中刪除

Question

我使用Tombstone方法從哈希表中刪除元素。

也就是說，不是取消分配節點和重組的哈希表我只是把刪除了被刪除的指數馬克並使其可用於進一步INSERT操作和突破搜索操作避免它。

但是，在這些標記超過某個數字後，我實際上想要釋放這些節點並重新組織我的表。

我想過分配其中有大小的新表：舊錶大小 - 刪除了＃馬克和插入是不是空節點並沒有DELETED馬克到這個新表 使用常規INSERT但這似乎對我來說過分殺傷。有沒有更好的方法去做我想要的？

我的表使用與散列函數，如線性探測開放Adressing，雙散列等

Answer 1

你的描述基本上是老調重彈，這是一個完全合理的解決問題的方法的算法。它具有與哈希表佔用率過大時使用的代碼完全相同的優點。

爲新表估算適當的大小非常棘手。在表格即將開始增長的情況下，通常不要在刪除後積極收縮散列表。