Dan*_*dox 9 algorithm hashtable
算法简介(CLRS)指出,使用双向链表的哈希表能够比单链表更快地删除项.谁能告诉我在Hashtable实现中使用双链表而不是单链表进行删除有什么好处？
这里的混淆是由于CLRS中的符号.为了与真正的问题保持一致,我在这个答案中使用了CLRS表示法.
我们使用哈希表来存储键值对.CLRS伪代码中未提及值部分,而关键部分定义为k.
在我的CLR副本中(我在这里处理第一版),列出带链接的哈希的例程是插入,搜索和删除(书中有更详细的名称).insert和delete例程采用参数x,该key[x]参数是与key关联的链接列表元素.搜索例程接受参数k,该参数是键值对的关键部分.我相信混淆是你已经将删除例程解释为使用键而不是链表元素.
由于x是链接列表元素,如果它是双向链接列表,单独使用它就足以从h(key[x])哈希表的槽中的链表执行O(1)删除.但是,如果它是一个单链表,那就不够了.在这种情况下,您需要从表的插槽中的链表的头部开始并遍历列表,直到您最终获得其前任.只有当你有前任的时候才能完成删除,这就是为什么书中说明单链接的案例导致搜索和删除的运行时间相同.xh(key[x])xx
虽然CLRS说您可以在O(1)时间内进行删除,但假设有一个双向链表,它还要求您x在调用delete时进行删除.重点是:他们定义了搜索例程来返回一个元素x.该搜索不是任意键的恒定时间k.x从搜索例程中获得后,在使用双向链接列表时,可以避免在删除调用中产生另一个搜索的成本.
如果向用户提供哈希表接口,则伪代码例程的级别低于您使用的级别.例如,k缺少将键作为参数的删除例程.如果该删除被暴露给用户,您可能只是坚持单链接列表并具有特殊版本的搜索以一次性找到x关联的k及其前任元素.