Geek asks and answers

Hash Table - Array of a Linked List - C ++

I am trying to create a hash table using an array on linked nodes (creating a linked list). But it's hard for me to insert a value into a Hash table. When I run it, I get the following:

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;
}
+5
source share
4 answers

the logic is wrong here

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 ctorfor 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 ); 
}
+2
source

After building intHashTableall the elements tableare still NULL. However, in a function, insertone element is dereferenced:

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

This causes the program to crash because it is forbidden to dereference a null pointer .

+3

, , :

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

NULL, ( * β†’ ).

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

You have never checked if table[location]null is. But during the construction of your hash table, there are no nodes inside the node table (you set each record to zero).

The problem with your code is that you never think about node allocation. You have to do

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;
}
+1
source

More articles:


All Articles