Kareem Aboughazala Kareem Aboughazala - 21 days ago 9
C++ Question

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

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

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;