我已经看到一两个线程了，但我仍然认为它没有被完全清除，所以......
我一直在研究算法导论(第 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/