重新表格

Question

我试图通过删除旧表并创建一个具有相同内容的新的更大的表来重新表格.我创建了一个reHash函数,但是这个函数会导致内存泄漏,导致程序在执行函数时崩溃.我找不到我的错误.

void HashMap::reHash()
{
int OldCapacity = cap;
cap = cap * 2 + 1; //set new capacity
Node** newHashTable = new Node*[cap]; //create a temporary table to hold info
for (int i = 0; i < cap; i++)
{
    newHashTable[i] = nullptr;
}

const Node* n;
//fill in the new temp table with old info
for (int i = 0; i < OldCapacity; ++i)
{
    n = HashTable[i];
    while (n != nullptr)
    {
        //initialize new node
        Node* nod = new Node;
        nod->key = n->key;
        nod->value = n->value;
        nod->next = nullptr;
        Node*& bucket = newHashTable[default_hash_function(n->key)/cap];
        nod->next = bucket;
        bucket = nod;
        n = n->next;
    }
}

// delete the links 
for (int i = 0; i < OldCapacity; ++i)
{
    Node *curr = HashTable[i];
    Node *next;
    while (curr != nullptr)
    {
        next = curr->next;
        delete curr;
        curr = next;
    }
}
HashTable = newHashTable;
}

Answer 1

你的根本泄漏是这样的:

HashTable = newHashTable;

你永远不会删除旧的指针数组.它应该是这样的:

delete [] HashTable;
HashTable = newHashTable;

您也没有在重新分配中为您的表大小正确计算散列函数的模数,这对您的散列表来说是毁灭性的.

这个:

Node*& bucket = newHashTable[default_hash_function(tmp->key) / cap];

应该这样:

Node*& bucket = newHashTable[default_hash_function(tmp->key) % cap];
// note modulo operator -------------------------------------^

Rehash Sans-Allocations

老实说,除了分配新床之外,这里不需要任何动态分配.您可以通过将现有节点从旧床移动到新床来使用现有节点.

void HashMap::reHash()
{
    int OldCapacity = cap;
    cap = cap * 2 + 1;

    // allocate new bed. note: uses () to value-initialize nullptr entries
    Node** newHashTable = new Node*[cap]();

    //fill in the new temp table with old info
    for (int i = 0; i < OldCapacity; ++i)
    {
        Node *n = HashTable[i];
        while (n != nullptr)
        {
            // advance n *before* moving node to new hash bed
            Node *tmp = n;
            n = n->next;

            // find the proper collision list pointer.
            Node*& bucket = newHashTable[default_hash_function(tmp->key) % cap];
            tmp->next = bucket;
            bucket = tmp;
        }
    }

    delete [] HashTable;
    HashTable = newHashTable;
}