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;
}

Is there a debugger in Code::Blocks? it will tell you what's wrong... — Caribou
– Caribou, Commented Jan 22, 2013 at 11:53
In insert, runner = table[location] is basically NULL, isn't it? — Reunanen
– Reunanen, Commented Jan 22, 2013 at 11:54
When you run in a debugger there are no errors or warnings or handy stack traces? — Caribou
– Caribou, Commented Jan 22, 2013 at 11:54
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. — Caribou
– Caribou, Commented Jan 22, 2013 at 12:02
Also, your name is in the screenshot, if that bothers you, ayokunle. — Open AI - Opting Out
– Open AI - Opting Out, Commented Jan 22, 2013 at 12:36

Reunanen · Accepted Answer · 2013-01-22 11:56:55Z

3

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.

answered Jan 22, 2013 at 11:56

Reunanen

8,0513 gold badges40 silver badges58 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Caribou Over a year ago

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

UmNyobe Over a year ago

@Caribou best test case ever

Reunanen Over a year ago

@user1965283: not really – now it will crash on the line pointed out by Caribou.

Reunanen Over a year ago

After runner = new Node(), runner will never be NULL.

Caribou Over a year ago

@user1965283 Pukku deserves the thanks - he saw the issue before me

|

AndersK · Accepted Answer · 2013-01-22 12:14:17Z

2

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 ); 
}

answered Jan 22, 2013 at 12:14

AndersK

36.1k6 gold badges64 silver badges86 bronze badges

Comments

Mats Petersson · Accepted Answer · 2013-01-22 11:58:41Z

1

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).

answered Jan 22, 2013 at 11:58

Mats Petersson

130k15 gold badges147 silver badges233 bronze badges

Comments

UmNyobe · Accepted Answer · 2013-01-22 12:07:29Z

1

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;
}

answered Jan 22, 2013 at 12:07

UmNyobe

23.1k10 gold badges64 silver badges90 bronze badges

Collectives™ on Stack Overflow

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

4 Answers 4

7 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

7 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related