为什么使用双向链表删除哈希表元素的时间复杂度是O(1)？

Question

在CLRS的《算法导论》教材第258页中有这样一段话：

如果链表是双向链表，我们可以在O(1)时间内删除一个元素。（注意，CHAINED-HASH-DELETE只需要输入元素x而不是它的关键字k，因此我们不必先搜索x。如果哈希表支持删除操作，那么它的链表应该是双向链表，以便我们可以快速删除项。如果链表只是单向连接的，那么要删除元素x，我们首先必须在列表中找到x，以便我们可以更新x的前驱节点的next属性。对于单向连接的列表，删除和搜索都具有相同的渐近运行时间）。

让我困惑的是这个大括号，我无法理解它的逻辑。使用双向链接列表，仍然需要查找x才能将其删除，这与单向链接列表有什么不同呢？请帮助我理解一下！

- John Yang

Answer 1

这里提出的问题是：考虑你正在查看哈希表中的特定元素。删除它的成本有多大？

假设您有一个简单的链表：

v ----> w ----> x ----> y ----> z
                |
            you're here

如果你移除了x，那么你需要连接w和y来保持链表的链接。你需要访问w并告诉它指向y（你希望有w ----> y）。但是你无法从x访问w，因为它只是被简单地链接！因此，你必须遍历整个列表以在O(n)操作中找到w，然后告诉它链接到y。这很糟糕。

然后，假设你是双向链接的：

v <---> w <---> x <---> y <---> z
                |
            you're here

很好，你可以从这里访问w和y，所以你可以使用O(1)操作将两者连接起来 (w <---> y)!

- B. Decoster

---

在你的解释中，你假设你知道指向x的指针，而不仅仅是x本身，但教科书没有说！或者这在教科书中隐含了吗？ - John Yang

请注意，CHAINED-HASH-DELETE 的输入是元素 x 而不是其键 k。是的，教科书上已经说得很清楚了 =)。假设您知道指向 x 的指针。这就是我在答案的第一行中重新编写问题的原因，因为我认为您忽略了这一点。（这也意味着，如果您不知道 x，通常需要花费 O(n) 操作来查找 x，无论是单链表还是双链表）。 - B. Decoster

在书中（11.3）的这段文字前面有一张图片。哈希集合中键的值实际上是它们表示中的指针，因此x是一个指针。 - Horia Toma

尽管我认为这个答案很有道理，但我仍然认为教科书在这里做得不好。它并不清晰，会让人感到困惑。考虑我们在哈希表中有键-值x对（键，值x）。元素X可以是任何东西，不一定是指针或包含链接列表指针的指针。教科书假设元素是“链接列表中的一个元素”，但没有在任何地方提到这一点。教科书实际上定义元素x的数据结构为包含指针和值的结构体会更好。 - Robert Wang

我不确定如何在不搜索链表的情况下获取元素x。这里的背景是，我们试图删除一个具有关键字k的对象v，哈希表使用链式解决冲突机制。如果我有元素x（它包装了对象v和指向其前一个和后一个元素的指针），那么是有帮助的，但实际上我们只有v，因此在最坏情况下删除仍需要O(n)的时间，因为您必须先找到x。我不知道我错过了什么，但我不认为双向链表有帮助。 - Alex

Answer 2

我认为散列表一部分大多是一个红鱼，真正的问题是：“我们能否在常数时间内从链表中删除当前元素？如果可以，如何做到？”答案是：这有点棘手，但实际上，通常情况下，我们是可以做到的。我们通常不必遍历整个链表以找到前一个元素。相反，我们可以交换当前元素和下一个元素之间的数据，然后删除下一个元素。唯一的例外是，当我们需要删除列表中的最后一项时。在这种情况下，没有下一个要交换的元素。如果您真的必须这样做，则无法避免查找前一个元素。但是，通常有方法可以避免这种情况——其中一个方法是使用标记终止链表而不是空指针。在这种情况下，由于我们永远不会删除具有标记值的节点，因此我们永远不必处理删除列表中的最后一项。这使我们拥有相对简单的代码，类似于以下内容：

template <class key, class data>
struct node {
    key k;
    data d;
    node *next;
};

void delete_node(node *item) {
    node *temp = item->next;
    swap(item->key, temp->key);
    swap(item->data, temp->data);
    item ->next = temp->next;
    delete temp;
}

- Jerry Coffin

Answer 3

总的来说您是正确的 - 您发布的算法将一个元素本身作为输入，而不仅仅是它的键：

请注意，CHAINED-HASH-DELETE 以元素x而不是其键k作为输入，因此我们无需先搜索x。

您有元素x - 由于它是双向链表，因此您有前驱和后继指针，因此您可以在O（1）中修复这些元素 - 对于单向链表，仅后继将可用，因此您需要搜索前驱以获得O（n）。

- BrokenGlass

Answer 4

假设您想要删除元素x，通过使用双向链表，您可以轻松地将x的前一个元素连接到x的下一个元素。因此，无需遍历整个列表，时间复杂度为O(1)。

- saddam hussain

Answer 5

编程角度： 可以使用C++中的unordered_map来实现这个功能。

unordered_map<value,node*>mp;

其中node*是指向存储键、左右指针的结构体的指针!

如何使用：

如果您有一个值v并想要删除该节点，只需执行以下操作：

1. 像这样访问该节点的值：mp[v]。

2. 现在只需使其左指针指向右侧节点即可。

是的，您完成了。

（仅提醒，在C++中，unordered_map平均需要O（1）来访问存储的特定值。）

- rahuljain1311

Answer 6

Find(x)通常对于链式哈希表来说是O(1)的，无论你使用单向链表还是双向链表都没有影响。它们在性能上是相同的。

如果在运行Find(x)之后，你决定要删除返回的对象，你会发现，在内部，哈希表可能需要再次搜索你的对象。这仍然通常是O(1)，不是一个大问题，但如果你发现你经常删除，你可以做得更好。而不是直接返回用户的元素，而是返回指向底层哈希节点的指针。然后你就可以利用一些内部结构。所以如果在这种情况下，你选择了双向链表作为表示链接的方式，那么在删除过程中，就没有必要重新计算哈希并再次搜索集合——你可以省略这一步。你有足够的信息从当前位置直接执行删除操作。如果要提交的节点是头节点，则必须特别小心，因此，如果它是链接列表的头部，则可以使用整数标记您的节点在原始数组中的位置。

权衡的是额外指针所占用的保证空间与可能更快的删除（以及稍微更复杂的代码）。随着现代台式机，空间通常非常便宜，因此这可能是一个合理的折衷方案。

- Michael Hays

Answer 7

在阅读教科书时，我也对同一主题感到困惑（“x”是指向一个元素还是元素本身），最终找到了这个问题。但在阅读上面的讨论并重新参考教科书后，我认为在书中，“x”被隐式地假定为一个“节点”，它可能的属性是“key”、“next”。

来自教科书的一些行：

1）CHAINED-HASH-INSERT(T,x) 将x插入到列表T[h(x.key)]的头部

2）如果列表只是单向链接的，那么为了删除元素x，我们首先必须在列表T[h(x.key)]中找到x，以便我们可以更新x的前驱结点的下一个属性。

因此我们可以假设给出元素的指针，我认为Fezvez已经对所问问题给出了很好的解释。

- Pushpendra

Answer 8

教科书是错的。列表的第一个成员没有可用的“previous”指针，因此需要额外的代码来查找并取消链接该元素，如果它恰好是链中的第一个（通常30%的元素是其链的头部，当将N个项目映射到M个插槽时，每个插槽都有一个单独的链）。

编辑：

与其使用反向链接，不如使用指向指向我们的链接的指针（通常是列表中前一个节点的->next链接）。

struct node {
   struct node **pppar;
   struct node *nxt;
   ...
   }

删除操作变成了：

*(p->pppar) = p->nxt;

这种方法的一个好处是，它同样适用于链上的第一个节点（其pppar指针指向的某个指针不是节点的一部分）。

更新2011-11-11

由于人们无法看到我的观点，我将尝试说明。例如，有一个哈希表table（基本上是指针数组）和一堆节点one，two，three，其中一个必须被删除。

    struct node *table[123];
    struct node *one, *two,*three;
    /* Initial situation: the chain {one,two,three}
    ** is located at slot#31 of the array */
    table[31] = one, one->next = two , two-next = three, three->next = NULL;
                one->prev = NULL, two->prev = one, three->prev = two;


    /* How to delete element one :*/
    if (one->prev == NULL) {
            table[31] = one->next;
            }
    else    {
            one->prev->next = one->next
            }
    if (one->next) {
            one->next->prev = one->prev;
            }

现在很明显，上面的代码是O(1)，但有一些麻烦：它仍然需要array和索引31，所以在大多数情况下，一个节点是“自包含的”，并且指向一个节点的指针足以从其链中删除它，除非它恰好是其链中的第一个节点；那么就需要额外的信息来找到table和31。

接下来，考虑具有指向指针的等效结构作为回链。

    struct node {
            struct node *next;
            struct node **ppp;
            char payload[43];
            };

    struct node *table[123];
    struct node *one, *two,*three;
    /* Initial situation: the chain {one,two,three}
    ** is located at slot#31 of the array */
    table[31] = one, one-next = two , two-next = three, three->next = NULL;
                one->ppp = &table[31], two->ppp = &one->next, three->ppp = &two-next;

    /* How to delete element one */
    *(one->ppp) = one->next;
    if (one->next) one->next->ppp = one->ppp;

注意：没有特殊情况，也不需要知道父表。 （考虑存在多个哈希表但具有相同的节点类型的情况：删除操作仍然需要知道应从哪个表中删除节点）。

通常，在 {prev，next} 场景中，通过在双向链表开头添加一个虚拟节点来避免特殊情况；但这也需要分配和初始化。

- wildplasser

---

我认为你没有好好考虑这个问题。请思考一下这段额外代码在大O表示法中需要多少工作量。 - BrokenGlass

@BrokenGlass：当然，找到头部的时间复杂度是O(1)，但仅为此情况编写特殊代码路径只有在链表很长时才值得。存储和维护prev指针也是需要考虑的因素。 - wildplasser

我们还在谈论双向链表吗？ - BrokenGlass

我们正在谈论哈希表和（双）链表的可用性，以我个人看来。 - wildplasser

+1 我相信人们可能没有理解你的观点——这是关于使用双向链表来减轻冲突的哈希表问题。不过，你在这里概述的问题很容易纠正。首先，将你的链接列表存储为循环链接列表。其次，保留每个节点的整数。如果整数为-1，则不应进行任何额外处理。如果它是正数，则标记数组中的索引，其头指针应更新为您自己的下一个指针。最后，您将将存储在下一个指针中的索引设置为您自己的索引。@brc说得对。 - Michael Hays