Hash-table - Array of Linked-list - C++

Question

I'm trying to create a Hash-table by using an array on linked-nodes (making a linked list). But I'm having difficulties inserting a value into the Hash-table. When I run it, I get this:

http://gyazo.com/3a28a70e66b3ea34e08223e5948f49c0.png

Here is my code:

#include <iostream>
using namespace std;

class Node {
public:
  int num;
  Node * next;
};

class intHashTable {
private:
  int size;
  Node ** table;
public:
  intHashTable(int size);  // construct a new hash table with size elements
  ~intHashTable();     // delete the memory for all internal components
  void insert(int num);    // insert num into the hash table, no effect
               // if num is already in table
  void remove(int num);    // remove num from the hash table, no effect if not in table
  int lookup(int num);     // return 1 if num is already in table, 0 otherwise
  void print(void);        // print the elements of the hash table to the screen
};

// construct a new hash table with nelements elements
intHashTable::intHashTable(int nelements)
{
  size = nelements;
  table = new Node*[size];
  for ( int i = 0; i < size; i++ ) {
    table[i] = NULL;
  }
}

intHashTable::~intHashTable()
{
   for(int i=0; i<size; i++)
   {
      Node* temp = table[i];
      while(temp != NULL)
      {
         Node* next = temp->next;
         delete temp;
         temp = next;
      }
   }
   size = 0;
   delete[] table;
}

void intHashTable::insert(int num){
    int location = ((unsigned)num) % size;
    Node *runner = table[location];
    if(runner == NULL ){
    runner->num = num;
     }else{
        while(runner != NULL ){
            runner = runner->next;
        }
        runner->num = num;
    }
   }

int main(){
    intHashTable a (10);
    a.insert(2);
    return 0;
}

Solution 1

the logic here is wrong

int location = ((unsigned)num) % size;
Node *runner = table[location];

if(runner == NULL ) // if null u dereference it!
{
 runner->num = num;
}
else
{
  while(runner != NULL ) {  // u loop until null
    runner = runner->next;
  }
  runner->num = num;  // once u reach null u dereference it!
}

i would suggest instead:

first a ctor for your Node

class Node {
public:
  int num;
  Node * next;

  Node( int _n ) : num(_n), next(NULL) { } 
};

and then

if ( runner != NULL )
{
   while ( runner->next != NULL )
   {
      runner = runner->next;
   }
   runner->next = new Node( num );
}
else
{
  table[location] = new Node( num ); 
}

Solution 2

After construction of intHashTable, all the elements of table are still NULL. However, in the function insert, one element is dereferenced:

Node *runner = table[location];
runner = runner->next;

This makes the program crash, because it is illegal to dereference a null pointer.

Solution 3

Node *runner = table[location];
runner = runner->next;
if(runner == NULL )

You never verified whether table[location] is null. But during construction of your hashtable, there are no nodes inside the node table (you set yourself every entry to null).

The problem with your code is that you never think about allocating your node. You should be doing

Node* toInsert = new Node;
toInsert->next= NULL;
toInsert->num = num;

if(table[location]==NULL){
   table[location] = toInsert;  
}
else{
    Node *runner = table[location];
    while(runner->next != NULL){
         runner = runner->next;
    }
    runner->next = toInsert;
}

Solution 4

This code certainly won't work:

if(runner == NULL ){
runner->num = num;

If runner is NULL, then you should never dereference it (using * or -> on it).

View more solutions

Comments

[Reunanen]

In insert, runner = table[location] is basically NULL, isn't it?

[Caribou]

When you run in a debugger there are no errors or warnings or handy stack traces?

[Caribou]

1 piece of friendly :) advice - using a debugger will give you an edge over other students that don't - it is something I always ask about at interview.

[Peter Wood]

Also, your name is in the screenshot, if that bothers you, ayokunle.