c++constructorlinked-listhashtablerule-of-three

Hash table - issue with destructor (pointer being freed was not allocated)


I have a HashTable, where collisions are handled by chaining (linked lists). The first node of every linked list has a pointer from each array position. Shown below is a regular constructor along with rule of 3 functions.

Although my code is compiling and my functions (add, remove, etc) are producing the right output, I am having an issue with the destructor (the IDE points to it with a Thread 1: signal SIGABRT) and the console displays "pointer being freed was not allocated" after my driver program finishes running. I can't figure out what went wrong so any help would be appreciated. I did not include my code for any of the other functions (add, remove, etc) aside from constructors/destructors.

Even when I comment out the copy and overloaded= constructors, the same issue still arise with the destructor.

specification:

class HashTable {

public:

    HashTable(int);
    ~HashTable();
    HashTable(const HashTable &);
    HashTable& operator=(const HashTable &);

private:

    struct Node {
        string word;
        int wordCount;
        Node * next;

        // node constructor
        Node(string w, int count) {
            word = w;
            wordCount = count;
            next = nullptr;
        }
    };

    Node** wordList;
    int capacity;

    int hashFunction(string);
};

Implementation of big 4:

constructor:

HashTable::HashTable(int cap) {
    capacity = cap;
    wordList = new Node*[capacity];
    for (int i = 0; i < capacity; i++)
        wordList[i] = nullptr;   
}

destructor (where the problem seems to be)

HashTable::~HashTable() {
    for (int i = 0; i < capacity; i++) {
        Node* curr = wordList[i];
        while (curr != nullptr) {
            Node* prev = curr;
            curr = curr->next;
            delete prev;          
        }
    }
    delete[] wordList;
}

copy constructor:

HashTable::HashTable(const HashTable &obj) {
    capacity = obj.capacity;
    wordList = new Node*[capacity];
    for (int i = 0; i < capacity; i++) {
        if (obj.wordList[i] == nullptr)
            continue;
        Node * newNode = new Node(obj.wordList[i]->word,        
                                  obj.wordList[i]->wordCount);
        wordList[i] = newNode;
    }
}

copy assignment operator:

HashTable& HashTable::operator=(const HashTable &obj) {
    if (this != &obj) {
        for (int i = 0; i < capacity; i++) {
            Node* curr = wordList[i];
            while (curr != nullptr) {
                Node* prev = curr;
                curr = curr->next;
                delete prev;
            }
        }
        delete[] this->wordList;

        this->capacity = obj.capacity;
        this->wordList = new Node*[capacity];
        for (int i = 0; i < this->capacity; i++) {
            if (obj.wordList[i] == nullptr)
                continue;                
            Node * newNode = new Node(obj.wordList[i]->word,
                                      obj.wordList[i]->wordCount);
            this->wordList[i] = newNode;
        }
    }
    return *this;
}

Solution

  • In your copy constructor and copy assignment operator, you are copying the list pointers from obj into this. This leaves the same pointers in both objects, resulting in double free and other issues once one HashTable has been freed,

    When you do the copies, you need to do a Deep Copy, which is to allocate new nodes for the copy of the word list.