c++ - 重新哈希表

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-分配

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

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;
}