如何在 c++ 中编写正确的哈希表析构函数

Question

我正在编写一个 c++ 哈希表

这是我的析构函数：

HashMap::~HashMap()
{
    for (int i=0; i<cap; i++)
    {
        Node* ptr = Hashtable[i];
        while (ptr!=NULL)
        {
            Node* delptr;
            delptr=ptr;
            ptr=ptr->next;
            delete delptr;
        }
    }
    delete [] Hashtable;
}

我的添加功能：

void HashMap::add(const std::string& key, const std::string& value)
{
    int index = hashfunction(key)%cap;;
    Node* ptr=Hashtable[index];
    Node* newnode=new Node;
    if (contains(key)==false)
    {
        if (ptr == nullptr)
        {
            newnode->key=key;
            newnode->value=value;
            newnode->next=NULL;
            Hashtable[index]=newnode;
        }
        else
        {
            newnode->key=key;
            newnode->value=value;
            newnode->next=NULL;
            while(ptr->next != NULL)
            {
                ptr = ptr->next;
            }
            ptr->next=newnode;
         }}}

但是我一直收到内存泄漏错误

==13676== 
==13676== HEAP SUMMARY:
==13676==     in use at exit: 12 bytes in 1 blocks
==13676==   total heap usage: 42 allocs, 41 frees, 669 bytes allocated
==13676== 
==13676== 12 bytes in 1 blocks are definitely lost in loss record 1 of 1
==13676==    at 0x402BE94: operator new(unsigned int) (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==13676==    by 0x804BF8D: HashMap::add(std::string const&, std::string const&) (HashMap.cpp:112)
==13676==    by 0x804AFD2: main (main.cpp:18)
==13676== 
==13676== LEAK SUMMARY:
==13676==    definitely lost: 12 bytes in 1 blocks
==13676==    indirectly lost: 0 bytes in 0 blocks
==13676==      possibly lost: 0 bytes in 0 blocks
==13676==    still reachable: 0 bytes in 0 blocks
==13676==         suppressed: 0 bytes in 0 blocks
==13676== 
==13676== For counts of detected and suppressed errors, rerun with: -v
==13676== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

它指示的行是 Node* newnode=new Node;因为我在这里使用"new"，所以这个 newnode 需要被解除分配，但析构函数只在 Hashtable 中释放内容。如果我不使用"newnode"，我将出现空指针访问错误，因为nullptr无法访问Node（Node是一个具有键和值的结构），我只能让指针指向"newnode"。但是，添加额外的"删除新节点"使我收到 20 多个错误。我真的需要你的帮助！

如果我写这个，我仍然收到一个错误

if (contains(key)==false)
{
    if (ptr == nullptr)
    {
        Node* newnode=new Node;
        newnode->key=key;
        newnode->value=value;
        newnode->next=NULL;
        Hashtable[index]=newnode;
    }
    else
    {
        Node* newnode=new Node;
        newnode->key=key;
        newnode->value=value;
        newnode->next=NULL;
        while(ptr->next != NULL)
        {
            ptr = ptr->next;
        }
        ptr->next=newnode;
     }}

Answer 1

此行

Node* newnode=new Node; 

创建一个本地 newnode 指针，该指针将在 Add 函数退出后超出范围。这将泄漏 new 分配的内存。

Answer 2

问题是你正在这样做：

Node* newnode=new Node;
if (contains(key)==false)
    // ... store it
/*
else
    leak it
*/

您需要做的是在新的之前执行条件。

if(contains(key) == true) {
     // use the existing entry.
     ...
     return;
}
else {
    Node* newnode=new Node;
    // ... rest of your code for inserting a new entry here.
}

----编辑----

ValGrind 告诉你的是，你的代码在 HashMap 第 112 行分配了一个指针.cpp但它从未存储过地址——当有人使用"contains（key）"不返回 false 的键调用 add 函数时，这就是你的代码中发生的情况。您不存储指针，因此您分配的节点保持分配状态，但您的代码没有跟踪它 ->它是泄漏。

Answer 3

只需声明新节点，然后在 if 语句之后分配新节点。你的代码现在的方式是可以分配新节点，if 语句出错，新节点保留在内存中从未使用过。