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

Question

I'm implementing a HashMap, I have a copy constructor and an assignment operator overload function. When rehashing occurs in the HashMap the assignment operator overload function throws a segmentation fault. However if no rehashing occurred the assignment operator works fine. I think I might have been looking at code for too long and if a new set of eyes to scanned the code the problem would become obvious.

Thanks

Here are my main member functions:

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


}

Here are some helper member functions that I use:

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

    }

}

When I ran memcheck it said that the error is in the deleteLinkedList function, on this line:

if (node->next == nullptr)

Since the problem occurs only when rehashing happens I was more inclined to check the rehashing function, however the rehashing function works fine if I don't invoke the assignment operator overloaded method. I would really appreciate any help.

Thank you.

Answer 1

In HashMap& HashMap::operator=(const HashMap& hm), you forgot to assign this->currentBucketCount with hm.currentBucketCount before the call to arrayCopy.

You should swap both statements and keep the old value of currentBucketCount to call deleteLinkedList:

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

to be replaced by

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

or by

    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;