散列表的懒惰删除

Question

在我的实现中，我使用了线性或二次探测的懒惰删除来解决碰撞问题。对于插入操作，当遇到一个已经被标记为懒惰删除的项时，我会用要插入的项替换它。这种做法的缺点或不正确之处是什么（无论是线性还是二次还是双重散列冲突解决）？难道这样做不能节省空间吗？

- zzzzzzzzzzz

Answer 1

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

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

当插入/删除大量项目时，闭合地址哈希表的性能会更加稳定。但是，它们不如缓存友好，因为您必须玩弄指针。

因此，如果您有几乎恒定的键，请选择开放寻址；否则，请考虑闭合地址哈希表。

对于某些问题，您可能还需要研究其他概念，如cuckoo哈希。

- Nico Erfurth

Answer 2

在线性探测开放地址哈希表中，没有必要进行懒惰删除。硬删除可以在恒定时间内简单完成，而且不会导致表的退化。维基百科哈希表页面上多年来一直有它的伪代码。我不知道为什么现在没有了，但这里是一个永久链接，指向它曾经存在的地方：旧维基百科哈希表页面，为了方便起见，这里是伪代码：

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

该页面还有一个指向真实代码的引用。我相信这与插入具有完全相同的性能特征，并将表恢复到添加条目之前的状态。

这种删除方法比常用的“标记删除并偶尔重新哈希所有内容”更好，因为上述方法是常数时间，而不是平摊常数时间。如果您有一个包含一百万个项目的哈希表，并且要进行添加和删除，在“标记删除”方法中，偶尔的添加或删除将比之前和之后的操作慢一百万倍，这不是一个良好的性能特征。

- hoopsnake