当散列函数中发生重新散列时，赋值运算符重载不起作用

Question

我正在实现一个 HashMap，我有一个复制构造函数和一个赋值运算符重载函数。当 HashMap 中发生重新散列时，赋值运算符重载函数会抛出分段错误。但是，如果没有发生重新散列，则赋值运算符可以正常工作。我想我可能看代码的时间太长了，如果有一组新的眼睛来扫描代码，问题就会变得很明显。

谢谢

以下是我的主要成员函数：

HashMap::HashMap()
    :hasher{hash}, Buckets_Array{new Node* [initialBucketCount]}, currentBucketCount{initialBucketCount}, sz{0}

{
    fillArray(Buckets_Array, currentBucketCount);


}


HashMap::HashMap(const HashMap& hm)
    :hasher{hm.hasher}, Buckets_Array{new Node*[hm.currentBucketCount]},currentBucketCount{hm.currentBucketCount}, sz{hm.sz}
{
    arrayCopy(hm.Buckets_Array, Buckets_Array, currentBucketCount);

}


HashMap::~HashMap()
{
    for(int i = 0; i < currentBucketCount; i++)
    {
        deleteLinkedList(Buckets_Array[i]);
    }

    delete[] Buckets_Array;
}


HashMap& HashMap::operator=(const HashMap& hm)
{

    if (this != &hm)
    {

        Node** newNodeArray = new Node*[hm.currentBucketCount];

        fillArray(newNodeArray, hm.currentBucketCount);

        arrayCopy(hm.Buckets_Array, newNodeArray, currentBucketCount);
        currentBucketCount = hm.currentBucketCount;
        sz = hm.sz;

        for (int i = 0; i < currentBucketCount; i++)
        {
            deleteLinkedList(Buckets_Array[i]);
        }

        delete[] Buckets_Array;
        Buckets_Array = newNodeArray;

    }

    return *this;
} 

void HashMap::add(const std::string& key, const std::string& value)
{
    // REHASH IF EXCEEDED LOAD FACTOR
    double futureLoadFactor = double((sz + 1))/double(currentBucketCount);

    if (futureLoadFactor > maximumLoadFactor)
    {
        rehashKeys();
    }

    unsigned int index = getIndex(key);

    if (!checkExists(Buckets_Array[index], key, value))
    {

        if (Buckets_Array[index] == nullptr)
        {
            Node* n = new Node;
            n->key = key;
            n->value = value;
            n->next = nullptr;
            Buckets_Array[index] = n;
        }

        else
        {

            addToEnd(Buckets_Array[index], key, value);

        }

        sz += 1;
    }


}

以下是我使用的一些辅助成员函数：

void HashMap::fillArray(Node** nodeArray, int size)
{
    for (int i = 0; i < size; i++)
    {
        nodeArray[i] = nullptr;
    }
}

void HashMap::rehashKeys()
{
    currentBucketCount = (currentBucketCount  * 2) + 1;
    Node** tempBucketsArry = new Node* [currentBucketCount];
    fillArray(tempBucketsArry, currentBucketCount);

    std::cout << "MAX INDEX: " << currentBucketCount/2 << std::endl;
    for (int i = 0; i < currentBucketCount/2; i++)
    {
        hashLinkedList(Buckets_Array[i], tempBucketsArry);
        deleteLinkedList(Buckets_Array[i]);

    }
    delete[] Buckets_Array;
    Buckets_Array = tempBucketsArry;

}


 void HashMap::hashLinkedList(Node* node, Node**& node_arry)
 {
    if (node != nullptr)
    {
        int newIndex = getIndex(node->key);          
        addToEnd(node_arry[newIndex], node->key, node->value);
        hashLinkedList(node->next, node_arry);

    }
 }

void HashMap::copyNode(Node* sourceNode, Node* targetNode)
{


    targetNode->key = sourceNode->key;
    targetNode->value = sourceNode->value;
    sourceNode = sourceNode->next;

    while (sourceNode != nullptr)
    {
        Node* tempNode = new Node;
        tempNode->key = sourceNode->key;
        tempNode->value = sourceNode->value;
        targetNode->next = tempNode;
        targetNode = targetNode->next;
        sourceNode = sourceNode->next;

    }

    targetNode->next = nullptr;

}



void HashMap::arrayCopy(Node** source, Node**& target, int arrysz)
{

    for (int i = 0; i < arrysz; i++)
    {
        if (source[i] != nullptr)
        {

            Node* copy = new Node;
            copyNode(source[i], copy);
            target[i] = copy;
        }

        else
        {
            target[i] = nullptr;
        }
    }


}

void HashMap::deleteLinkedList(Node* node)
{




    while (node != nullptr)
    {
        if (node->next == nullptr)
        {
            delete node;
            break;

        }

        else
        {
            Node* next = node->next;
            delete node;
            node = next;
        }
    }

}

//  Adds node to the end of linked list

void HashMap::addToEnd(Node*& node, std::string key, std::string value)
{

    if ( node == nullptr )
    {
        Node* n = new Node;
        n->key = key;
        n->value = value;
        n->next = nullptr;
        node = n;

    }


    else
    {

        addToEnd(node->next, key, value);

    }

}

当我运行 memcheck 它说错误在 deleteLinkedList 函数中，在这一行：

if (node->next == nullptr)

因为只有在重新散列发生时才会出现问题，所以我更倾向于检查重新散列函数，但是如果我不调用赋值运算符重载方法，重新散列函数就可以正常工作。我真的很感激任何帮助。

谢谢。

Answer 1

在 HashMap& HashMap::operator=(const HashMap& hm) 中，您忘记在调用 arrayCopy 之前将 this->currentBucketCount 赋值给 hm.currentBucketCount。

您应该交换两个语句并保留 currentBucketCount 的旧值以调用 deleteLinkedList:

    arrayCopy(hm.Buckets_Array, newNodeArray, currentBucketCount);
    currentBucketCount = hm.currentBucketCount;

将替换为

    int oldBucketCount = currentBucketCount;
    currentBucketCount = hm.currentBucketCount;
    arrayCopy(hm.Buckets_Array, newNodeArray, currentBucketCount);
    ...
    for (int i = 0; i < oldBucketCount; i++)
    {
        deleteLinkedList(Buckets_Array[i]);
    }

或

    arrayCopy(hm.Buckets_Array, newNodeArray, hm.currentBucketCount);
    // currentBucketCount = hm.currentBucketCount;
    // sh = hm.sz;
    for (int i = 0; i < currentBucketCount; i++)
    {
        deleteLinkedList(Buckets_Array[i]);
    }
    currentBucketCount = hm.currentBucketCount;
    sh = hm.sz;

当散列函数中发生重新散列时，赋值运算符重载不起作用

Assignment operator overloading doesn't work when rehashing occurs in a hash function

c++

segmentation-fault

hashtable

assignment-operator

dynamic-allocation