从HashTable中删除

Question

我使用Tombstone方法从哈希表中删除元素。

也就是说，不是取消分配节点和重组的哈希表我只是把删除了被删除的指数马克并使其可用于进一步INSERT操作和突破搜索操作避免它。

但是，在这些标记超过某个数字后，我实际上想要释放这些节点并重新组织我的表。

我想过分配其中有大小的新表：旧表大小 - 删除了＃马克和插入是不是空节点并没有DELETED马克到这个新表 使用常规INSERT但这似乎对我来说过分杀伤。有没有更好的方法去做我想要的？

我的表使用与散列函数，如线性探测开放Adressing，双散列等

Answer 1

你的描述基本上是老调重弹，这是一个完全合理的解决问题的方法的算法。它具有与哈希表占用率过大时使用的代码完全相同的优点。

为新表估算适当的大小非常棘手。在表格即将开始增长的情况下，通常不要在删除后积极收缩散列表。