[解決済み] テーブルの再ハッシュ化

質問

古いテーブルを削除して、同じ内容の新しい大きなテーブルを作成することによって、テーブルをリハッシュしようとしています。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;
}

解決方法は？

根本的な漏れはこれだ。

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 -------------------------------------^

リハーサルサンスアロケーション

正直なところ。 なし の動的割り当てが必要なのは、新しいベッドを割り当てるときだけです。既存のノードを古いベッドから新しいベッドに移動させることで使用することができます。

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