C++ Hashing and Separate Chaining Infinite Loop Problem with chained nodes

Question

I am trying to implement hashing with separate chaining. This is for a homework assignment. Yes, I've read the policy here.

My understanding of separate chaining is that I am to implement a linked list for elements that result in the same hash. I have an array that holds all the possible slots for the hash positions and then, when more than one element shares the same hash, use a linked list at that slot position in the array. I assume that none of the insertion values hold 0 since that is the default value of each node (for debugging purposes since you could use NULL).

For the purpose of the assignment, I'm just using an array and a really simple hash function that takes mod of the array size.

There is some kind of issue with my implementation because there is an infinite loop when I execute it. I am very interested to understand why this isn't working. I'm not just looking for an answer but rather an explanation so I can understand why it's not working.

It looks like the issue occurs only in the array elements that are chained. I've rewritten this code many many times trying to understand what's going on. In another version, it was creating the chained nodes correctly but the values were not accessible when I tried to display them (it was outputting garbage values). I suspect there's some kind of reference issue in insertSepChain() or display() that's causing it to break.

#include <iostream>

class ListNode {
public:
    int value;
    ListNode* next;
    ListNode(int newValue) {
        value = newValue;
        next = nullptr;
    }
    ListNode() {
        this->value = 0;
        this->next = nullptr;
    }
};


class HashTest {

private:
    int size;
    ListNode arr[17];//used a number for debugging purposes
public:
    HashTest(int size) {
        this->size = size;
        for (int i = 0; i < size; i++) {
            arr[i] = ListNode(0);
        }
    }
    void insertSepChain(int value) {

        //find the index to place the value
        int index = hash(value);

        if (arr[index].value == 0) {
            //not already filled
            arr[index].value = value;
        }
        //already filled
        else {
            ListNode temp(value);
            arr[index].next = &temp;
        }
    }
    int hash(int value) {
        return value % size;
    }

    void display() {
        using namespace std;

        for (int i = 0; i < size; i++) {
            if (arr[i].value == 0) {
                //not filled
                cout << "0\n";
            }
            else if (arr[i].value != 0 && arr[i].next == nullptr) {
                //filled and no chain
                cout << arr[i].value << "\n";
            }
            else if (arr[i].value != 0 && arr[i].next != nullptr) {
                //filled and chain
                cout << "chain: ";
                ListNode temp = arr[i];
                while (temp.next != nullptr) {
                    cout << temp.value << ", ";
                    temp = *temp.next;
                }
            }
        }
    }
};

int main() {
    HashTest testing(17);

    //9, 34, 49, 16, 32, 51

    using namespace std;

    testing.insertSepChain(9);
    testing.insertSepChain(34);
    testing.insertSepChain(49);
    testing.insertSepChain(16);
    testing.insertSepChain(32);
    testing.insertSepChain(51);

    testing.display();


    return 0;
}

Answer 1

This code stores the address of a local variable into your list. That variable is destroyed and its address is no longer valid, the moment you leave the else block. Therefore your code suffers from undefined behavior when you attempt to dereference that pointer later.

//already filled
else {
    ListNode temp(value);     //<-- temp is a local variable
    arr[index].next = &temp;  //<-- you store a pointer to temp
}                             //<-- temp is destroyed here

You must ensure that your program has allocated memory for the list node that will be valid for at least as long as you need to access it. The standard way to do this is allocate memory on the heap:

//already filled
else {
    ListNode* node = new ListNode(value);
    node->next = arr[index].next;
    arr[index].next = node;
}

The above will allocate a new node, and then insert it into the head of whatever list (if any) is hanging off of arr[index]. Note that I changed the name of the variable to node. I think this is better than temp, which honestly has very little useful meaning.

The other issue lies in your display function, which is using a curious method of traversing the list by copying nodes. It also misses the last node. You should instead use pointers for traversal. That's how lists are designed to be used.

A simple rearrangement of the loop, along with using pointers, and you get this:

//filled and chain
ListNode* node = &arr[i];
cout << "chain: " << node->value;
while (node->next) {
    node = node->next;
    cout << ", " << node->value;
}

Note that now you're using dynamic memory, you must also clean it up later. The modern way to do this is by avoiding raw pointers entirely and managing memory with std::unique_ptr. But either way, you should define a destructor somewhere that cleans up memory. You might choose to make a destructor for ListNode, but it is probably better to do it in HashTest. In fact, ListNode should not be publically accessible anywhere. It's internal to your hash table, and should be defined that way.

~HashTest()
{
    for(auto& entry : arr) {
        while (entry.next)
        {
            ListNode* node = entry.next;
            entry.next = node->next;
            delete node;
        }
    }
}

And finally, since you have a class that manages memory, you must also consider the Rule of Three. Either define a copy-constructor and assignment operator, or explicitly delete them.