我已经看到一两个关于这个的话题了，但我仍然认为它还没有完全清理干净，所以...
我一直在算法简介(第 11 章)中查看带有链接的哈希表。他们说，如果哈希表的链表是双向链接的，则可以在 O(1) 时间内执行删除。但我看不出这是怎么回事。
T is a chained hash table. I want to delete element X from it.
h(X.key) returns the hash of X's key.
So, to delete X, pass X to the delete routine.
Then we can find X's slot in the linked list:
T[ h(X.key) ] = j
j is actually the pointer to the head of the linked list as > 1 key hashes to j.
So we still need to now search the linked list at j to find X to delete it,
regardless of whether or not the list is doubly linked.
And this search is O(n). So deletion is O(n)???
我的观点是，我们不是还需要在链表中搜索 X 吗？ X 是我们想要存储在哈希表中的任意对象。它不包含指针。 链表中持有 X 的元素将包含指向链表中下一个和上一个元素的指针，但不包含 X。
最佳答案
在这里深入挖掘后，我偶然发现了答案。
书中隐含的假设是链表中的链接是元素 X 的一部分，而不是有一个单独的容器节点对象来实现链接并指向元素.也就是说，我们希望删除的对象 X 包含指向链表中下一个和上一个元素的指针。作者真的应该明确这一点。
感谢 RBarryYoung 的回答!
关于algorithm - 如何在具有双向链接的哈希表 O(1) 中进行删除？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26919360/