data-structures - Lazy deletion on hash tables

Question

In my implementation I use lazy deletion with linear or quadratic probing for collision resolution. For insertions, when I encounter a lazily deleted item, I replace it with the item to be inserted. What are the disadvantages or incorrectness of doing it this way(for either linear or quadratic or double hash collision resolution)? Doesn't it save space?

Answer 1

开放寻址哈希表的问题在于它们的性能会随着时间的推移而下降，尤其是当条目非常动态时。

例如，让我们考虑一个简单的线性探测列表。如果您在哈希槽 1 上发生 3 次冲突，则将使用槽 1、2、3。如果 2 被删除，您需要将其标记为“以前使用过”才能在插槽 3 中找到该项目。在某些使用模式下，这会将您的哈希表降级到线性搜索时间越来越长的地步，需要代价高昂的重新调整以使其再次生效。

在插入/删除大量项目时，已关闭地址的哈希表的性能会随着时间的推移更加稳定。但是它们对缓存不友好，因为您必须摆弄指针。

因此，如果您有几乎恒定的键，请使用开放寻址，否则考虑使用封闭寻址哈希表。

对于某些问题，您可能还想研究其他概念，例如布谷鸟哈希。

Answer 2

无需从线性探测的开放寻址哈希表中进行延迟删除。硬删除可以简单地在恒定时间内完成，而无需表降级。多年来，维基百科哈希表页面上都有它的伪代码。我不知道为什么不再存在，但这里有一个永久链接回到它的时候：Old Wikipedia Hash Table page，为了您的方便，这里是伪代码：

function remove(key)
 i := find_slot(key)
 if slot[i] is unoccupied
     return   // key is not in the table
 j := i
 loop
     j := (j+1) modulo num_slots
     if slot[j] is unoccupied
         exit loop
     k := hash(slot[j].key) modulo num_slots
     if (j > i and (k <= i or k > j)) or
        (j < i and (k <= i and k > j)) (note 2)
         slot[i] := slot[j]
         i := j
 mark slot[i] as unoccupied

该页面上还有一些真实代码的参考。我相信这与插入具有完全相同的性能特征，并将表恢复到与从未添加条目一样好的状态。

这种删除方法比常用的“标记已删除并偶尔重新散列所有内容”要好，因为上述方法是恒定时间而不是摊销的恒定时间。如果您有一个包含一百万个要添加和删除的项目的哈希表，在“标记已删除”方法中，偶尔的添加或删除将比之前和之后的时间长一百万倍 - 这不是良好的性能特性。