带有双向链表的哈希表？

Question

Introduction to Algorithms (CLRS)指出，使用双向链表的哈希表能够比使用单链表的哈希表更快地删除项目。谁能告诉我在Hashtable实现中使用双链表而不是单链表删除的好处是什么？

Answer 1

这里的混乱是由于CLRS中的符号造成的。为了与真正的问题保持一致，我在这个答案中使用了CLRS符号。

我们使用哈希表来存储键值对。值部分在CLRS伪代码中没有被提及，而键部分被定义为k。

在我的CLR副本(这里我正在编写第一版)中，为使用链接的散列列出的例程是插入、搜索和删除(本书中有更详细的名称)。insert和delete例程接受参数x，它是与键key[x]关联的链表元素。搜索例程接受参数k，它是键-值对的键部分。我相信混淆之处在于您已经将delete例程解释为接受一个键，而不是一个链表元素。

由于x是一个链表元素，如果它是一个双向链表，那么仅有它就足以从哈希表的h(key[x])槽中的链表中进行O(1)删除。但是，如果它是一个单链表，那么只有x是不够的。在这种情况下，您需要从表的槽h(key[x])中的链表的头部开始，遍历该列表，直到您最终点击x来获取它的前身。只有当您拥有x的前身时，才能完成删除，这就是为什么书中指出，单链接例导致搜索和删除的运行时间相同。

其他讨论

虽然CLRS说你可以在O(1)时间内完成删除，但假设是一个双向链表，它也要求你在调用x时有删除。重点是:他们定义了搜索例程来返回一个元素x。对于任意关键字k，该搜索不是恒定的时间。一旦从搜索例程中获得x，就可以避免在使用双向链表时在调用delete时产生另一次搜索的开销。

伪代码例程比您在向用户呈现哈希表接口时所使用的级别要低。例如，缺少一个以键k作为参数的删除例程。如果删除操作暴露给用户，您可能只会坚持使用单链接列表，并使用特殊版本的搜索来一次查找与k及其前身元素相关联的x。

Answer 2

我能想到一个原因，但这不是一个很好的原因。假设我们有一个大小为100的哈希表。现在假设将值A和G分别添加到表中。也许A散列到75号槽。现在假设G也散列到75，我们的冲突解决策略是以恒定的步长80向前跳跃。所以我们尝试跳到(75 + 80) % 100 = 55。现在，我们可以从当前节点开始并向后遍历20，而不是从列表的前面开始并向前遍历85。当我们到达G所在的节点时，我们可以将其标记为墓碑以删除它。

尽管如此，我仍然建议在实现哈希表时使用数组。

Answer 3

Hashtable通常被实现为列表的向量。其中向量中的索引是键(散列)。

如果每个键不超过一个值，并且对有关这些值的任何逻辑都不感兴趣，那么一个链表就足够了。在选择其中一个值时，更复杂/更具体的设计可能需要双向链表。