哈希表上的延迟删除

Question

在我的实现中，我使用惰性删除和线性或二次探测来解决冲突。对于插入，当我遇到延迟删除的项时，我会将其替换为要插入的项。这种方式的缺点或不正确之处是什么(对于线性、二次或双哈希冲突解决方案)？它不是节省了空间吗？

Answer 1

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

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

当插入/删除大量项目时，封闭寻址的哈希表的性能将随着时间的推移而更加稳定。但是它们不是缓存友好的，因为你必须摆弄指针。

所以，如果你有几乎不变的键，使用开放寻址，否则考虑关闭寻址的哈希表。

对于某些问题，您可能还需要研究其他概念，如布谷鸟散列。

Answer 2

不需要从线性探测的开放地址哈希表中执行惰性删除。硬删除可以在固定的时间内简单地完成，而不会出现表失真。多年来，维基百科的哈希表页面上都有它的伪代码。我不知道为什么is不存在了，但这里有一个追溯到它存在时的永久链接：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

在该页面上还有对一些real code的引用。我相信这与插入具有完全相同的性能特征，并将表恢复到与从未添加条目的状态一样好的状态。

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