在C++中删除哈希表

Question

我正在使用C++构建一个使用数组和由链表表示的桶的哈希表。当我尝试清除哈希表时，遇到了非常奇怪的问题，我希望有人能解释一下为什么会出现这种情况。

以下代码运行良好：

for(int i = 0; i < bins; i++)
{
    while(map[i]->next != nullptr)
    {
        LN* toDelete = map[i];
        map[i] = map[i]->next;
        delete toDelete;
    }
}

然而，出于某种原因，如果我这样做，它将不再删除任何内容：

for(int i = 0; i < bins; i++)
{
    LN* node = map[i]
    while(node->next != nullptr)
    {
        LN* toDelete = node;
        node = node->next;
        delete toDelete;
    }
}

每个桶都由一个挂接链表表示，这就是为什么我检查 node->next 而不是 node。根据我对指针的基本理解，node 应该引用与 map[i] 相同的内容，因此当我在 node 上调用 delete 时，应该删除 map[i] 和 node 引用的对象。

提前感谢您的帮助。

- Kareem Aboughazala

---

请编辑您的问题，提供一个最小可复现示例（MCVE）。 - Baum mit Augen

我猜你是在做这个哈希表作为练习？否则你应该使用std::unordered_map。 - Some programmer dude

你的代码（两个示例）并没有删除所有节点，它不会删除最后一个节点。 - Some programmer dude

这是一个带有 trailer 的链表，因此如果保留 trailer 不动也没问题。 - Kareem Aboughazala

如果 map [0] 是 nullptr，会发生什么？ - Ed Heal

Answer 1

您的代码确实删除了所有内容。但它没有将map[i]指针更改为指向一个空列表元素（next设置为nullptr），因此它最终指向一个已删除的对象。

这意味着map[i]是“悬空”的。对其进行解引用是未定义的行为。可以通过在循环结束后将map[i]赋值为node的值来修复这个问题：

LN* node = map[i];
while(node->next != nullptr)
{
    LN* toDelete = node;
    node = node->next;
    delete toDelete;
}
map[i] = node;

- Sergey Kalinichenko

---

每个桶都由一个拖车链表表示，因此如果桶中没有值，则map [i]应指向一个空节点。我认为我没有清楚地表达，这段代码并不是在析构函数中实现的，而是用于清除链表的内容。我的问题是，说node * = map [i]是否与使用map [i]相同。由于某种原因，我问题中的第二个代码块无法按预期运行。 - Kareem Aboughazala