Hash表中的删除

Question

当时我正在读“算法入门”一书，我偶然发现：

如果列表是双链接的，我们可以在O(1)时间内删除一个元素。(注意，链式散列删除以一个元素x而不是它的键k作为输入，这样我们就不必先搜索x。如果哈希表支持删除，那么它的链接列表应该是双链接的，以便我们可以快速删除一个项。如果列表仅被单独链接，那么要删除元素x，首先必须在list Th()中找到x，以便更新x的前辈的下一个属性。对于单链表，删除和搜索都有相同的渐近运行时间。)

如果列表是双链接的，我们如何在O(1)时间删除元素？首先，我们需要找到元素，然后可以在O(1)中删除它。但是要找到它，我们需要O(列表的长度)时间。也许在双链接列表中删除比较快(因为我们可以同时从列表的两端进行搜索，但这只是不断的改进)，但我不知道如何在O(1)时间内完成。

提前谢谢你。

Answer 1

答案在课文中；

请注意，链式哈希-DELETE以元素x而不是其键k作为输入，因此我们不必先搜索x。

您已经拥有了该项，因此只需从链中删除它并执行删除操作。

要删除项目X，您需要获取列表中的前一个和下一个节点，并在删除X之前将它们链接到一起，以便列表保持不变。在双链接列表中，您已经有了一个指向前一个和下一个的链接，所以这是常量。在单个链接列表中，您将只有一个指向next的链接，因此您需要扫描该列表以找到前一个节点。

Answer 2

我认为这里的混乱是因为CLRS中隐含的假设。在这本书中，对象通常被视为属性包，在其中所需的属性可以在运行时添加--非常类似于JavaScript，但与Java/C# world不同。因此，如果要将x放入链接列表中，则不一定需要先创建Node对象，然后为前一个、下一个和值添加属性。相反，您只需将这些属性添加到x本身。我们中的许多在静态类型化语言中长大的人都会对这种设计感到震惊，但是对于使用伪代码的算法设计来说，它消除了不必要的混乱。我认为作者应该澄清这一点。在任何情况下，如果不能动态地添加以前的属性和对象的下一个属性，是的，即使具有双链接列表，也不会是O(1)。