Hashtable AddEntry Separate Chaining Segmentation Fault

Question

I am getting a segmentation fault in my Separate Chaining Hash Table object.

bool hashTable::addNode(int id, string information){
bool inserted = false;  
int position = hash(id);
cout << &hashtable[position]<<endl;
if(hashtable[position]==NULL){
    hashtable[position]->data.id = id;
    hashtable[position]->data.information = information;
    hashtable[position]->next = NULL;
    inserted = true;
} else {
    Node* current = new Node;
    current = hashtable[position];
    while(current!=NULL){
        if(id < hashtable[position]->data.id){
            current->data.id = id;
            current->data.information = information;
            current->next = hashtable[position];
            hashtable[position] = current;
            inserted = true;
        } else if(id < current->data.id){
            current->data.id = id;
            current->data.information = information;
            current->next = hashtable[position]->next;
            hashtable[position]->next = current;
            inserted = true;
        } else if(current->next==NULL){
            Node *temp;
            temp->next = NULL;
            temp->data.id = id;
            temp->data.information = information;
            current->next = temp;
            inserted = true;
        } 
        current = current->next;                
    
    }
}
return inserted;

}

Essentially, I have an array of head pointers to handle the separate chaining, but the segmentation fault in addNode is messing me up. To be clear, I am calling a public AddEntry first which calls the AddNode for each individual LinkedList in the array.

#ifndef HASH_H
#define HASH_H

#include <iostream>
#include <string>
#include "data.h"

using std::string;
using std::cout;
using std::endl;

#define SIZE 15

class hashTable{
public:
    hashTable();
    ~hashTable();

    bool addEntry(int id, string information);
    string getEntry(int id);
    bool removeEntry(int id);
    int getCount();
    void displayTable();

private:
    bool removeNode(int id, int position);
    bool addNode(int id, string information);
    int count = 0;
    Node* hashtable = new Node[SIZE]; //array of head pointers
    int hash(int id);
};

#endif

Sorry if I didn't word this the best this is my first time on Stack Overflow.

Answer 1

There are a few spots in your code where it looks like you're using the address-of operator & incorrectly. Let's start with this one:

if (&hashtable[position] == NULL) {
   ...
}

I completely see what you're trying to do here - you're trying to say "if the slot at index position holds a null pointer." However, that's not what this code actually does. This says "if the location in memory where hashtable[position] exists is itself a null pointer." That's not possible - hashtable[position] refers to a slot in an array - so this if statement never fires.

It might be helpful to draw pictures here to get a better sense of what's going on. For example, suppose you have an empty hash table, as shown here:

 +-------+       +------+------+------+------+     +------+
 |       |------>| null | null | null | null | ... | null |
 +-------+       +------+------+------+------+     +------+
 hashtable

Here, hashtable[position] refers to the pointer at index position in the array pointed at by hashtable. With an empty hash table, hashtable[position] will evaluate to NULL because that's the contents of the pointer at that slot. On the other hand, &hashtable[position] refers to something like this:

                    &hashtable[position]
                        +-------+
                        |       |
                        +-------+
                            |
                            v
 +-------+       +------+------+------+------+     +------+
 |       |------>| null | null | null | null | ... | null |
 +-------+       +------+------+------+------+     +------+
 hashtable

Here, &hashtable[position] points to one of the pointers in the array. And while the pointer &hashtable[position] is pointing at something that is a null pointer, it itself is not a null pointer, since it's pointing to a valid object in memory.

Changing the code to read

if (hashtable[position] == NULL) {
     ...
}

correctly expresses the idea of "if the entry at index position within the hashtable array isn't a null pointer."

There are similar errors in your code at a few other points. Read over what you have with an eye toward the following question: do I want the pointer stored in the array at some index, or do I want the location in memory where that pointer happens to live?