Hash Table with Separate Chaining

[ace8957]

Hi all,
So I'm trying to learn how to do a hash table with separate chaining, but it is giving me several issues. The hash table I'm trying to make will hold instances of a class named Person and uses Person's data member phonenumber for the key.

Currently, the main issue I am having is that I am unsure how to implement the array of linked lists, as this is a configuration I have never come across before. The functions that I have so far are limited by my current implementation of the array of linked lists, but they seem logical to me.

Thus, my question is: What should I change to make the array of linked lists? And how should I initialize it?

Here is what I have come up with to this point:
(note that the prepArray function does not work, but it was my attempt at initializing the head of each linked list to null)

#include <string>
#include <iostream>
//#include "ChainNode.h"
#include "person.h"

#define MAX 200

using namespace std;

class hashTable {
    private:
    struct hashNode
{
        Person data;
        bool filled;
        hashNode * next;
};//end node
    hashNode array[MAX];
    public:
    int hash(string);
    void prepArray();
    void tableInsert(Person p);
    void tableDelete(string);
    Person tableRetrieve(string);
};//end hashTable

Person hashTable::tableRetrieve(string p) {
    int index = hash(p);
    hashNode * hp = &(array[index]);
    //hashNode * hp = array[index];
    if(hp != NULL)
    {
        cout << "in if" << endl;
        while((hp->data.getPhonenumber() != p) && (hp->next != NULL))
        {
            hp = hp->next;
        }//end while
        if(hp->data.getPhonenumber() == p)
        {
            return hp->data;
        }//end if
        else if(hp->next == NULL)
        {
            cout << "No such value" << endl;
        }//end else if
        //if this point in the funtion is reached, there is no member with that key
    }//end if
    cout << "No data found with said key" << endl;
    exit(1);
}//end

void hashTable::tableDelete(string phonenumber)
{
    int index = hash(phonenumber);
    hashNode * hp = &(array[index]);
    //hashNode * hp = array[index];
    if(hp)
    {
        while((hp->data.getPhonenumber() != phonenumber) && (hp->next != NULL))
        {
            hp = hp->next;
        }//end while
        if(hp->next == NULL)
        {
            cout << "No such value" << endl;
            return;
        }//end if
        else if(hp->data.getPhonenumber() == phonenumber)
        {
            hashNode * temp = hp;
            hp = hp->next;
            delete temp;
        }//end else if
    }//end if
    else
    {
        cout << "No value with that phone number." << endl;
        return;
    }//end else

}

void hashTable::tableInsert(Person p)
{
    int index = hash(p.getPhonenumber());
    hashNode *hp = &(array[index]);//hashed position
    //hashNode * hp = array[index];
    //bool filled;
    if(hp == NULL)
    {
        hp = new hashNode;
        hp->data = p;
        hp->next = NULL;
    }
    else if(hp !=NULL)
    {
        while(hp->next!=NULL)
        {
            hp = hp->next;
        }//end while
        //the first empty position has now been found
        hp=hp->next;//move up to the null pointer
        hp = new hashNode;
        hp->data = p;
        hp->filled = true;
        hp->next = NULL;
    }//end else if
}//end tableInsert

void hashTable::prepArray()
{
    hashNode * head = new hashNode;
    for(int i = 0; i < MAX; i++)
    {
        //array[i] = false;
        array[i].data = NULL;
        //head = array[i];
    }//end for
    //all the filled tags are now set to false
}//end prepArray

int hashTable::hash(string phonenumber)
{
    //string str = p.getPhonenumber();
    //int size = str.size();
    int size = phonenumber.size();
    int sum;
    for(int i=0; i < size; i++)
    {
        sum += phonenumber[i];
    }//end for
    int h = sum % size;
    return h;
}

And here is my Person class, which provides the data type for the hashNode:

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <stdio.h>
#include <string>
using namespace std;

class Person{
    private:
    string name;
    string phonenumber;
    string GPA;
    public:
    Person();
    Person(string name, string phonenumber);
    string getName();
    string getPhonenumber();
    void setName(string newname);
    void setPhonenumber(string newphonenumber);
    void setGPA(string);
    string getGPA();
};

Person::Person()
{
}

Person::Person(string newname, string newphonenumber)
{
    name = newname;
    phonenumber = newphonenumber;
}

string Person::getName() {
    return name;
}

string Person::getPhonenumber() {
    return phonenumber;
}

void Person::setName(string newname) {
    name = newname;
}

void Person::setPhonenumber(string newphonenumber) {
    phonenumber = newphonenumber;
}

string Person::getGPA() {
    return GPA;
}//end

void Person::setGPA(string newGPA) {
    GPA = newGPA;
}//end

I hate to ask such an open-ended sort of question of you guys, but I am having a very difficult time finding an example of this situation actually written in C++ that is not immensely complex.

[IamAuser]

Here is something that I wrote a while ago. I use a vector<Node*> to chain data.. Although this may not exactly answer your question it might be nice to see a different implementation.

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>

#define DEFAULT 1024

using namespace std;

class Node {
   friend class HashTable;
   Node* next;
   int data;

  public:
    Node(){
    }
    Node(int d, Node* n){
      data = d;
      next = n;
    }
    ~Node() { 
    }
};

class HashTable {
  public:
   int size;
   vector<Node*>* buckets; 
   HashTable(int s){
        size = s;
        buckets = new vector<Node*>(size);
   }
   HashTable(){
      size = DEFAULT;
      buckets = new vector<Node*>(size);
   }

   ~HashTable(){
   }

   void insert(int data){
      int index = hash(data);
      if(buckets->at(index) == NULL){
         buckets->at(index) = new Node(data,NULL);
         return;
      }
      Node* p = buckets->at(hash(data));
      while(p != NULL){
         if(p->next == NULL){
            p->next = new Node(data,NULL);
            break;
          }
         p = p->next;
      }
   }


   void remove(){
   }
   int getSize(){
      return size;
   }
   int hash(int a){
      a = (a+0x7ed55d16) + (a<<12);
      a = (a^0xc761c23c) ^ (a>>19);
      a = (a+0x165667b1) + (a<<5);
      a = (a+0xd3a2646c) ^ (a<<9);
      a = (a+0xfd7046c5) + (a<<3);
      a = (a^0xb55a4f09) ^ (a>>16);
      return abs(a % getSize());
  }


   void print(int start){
      int lineCount = 0;
      for(int i = start; i < buckets->size(); i++){
          cout<< i << "\t";
          Node* p = buckets->at(i);
          while(p != NULL){
             cout << p->data<<" ";
             p = p->next;
          }
          cout<< endl;
      }
   }


};

int main(int argc, const char* argv[]){
   if(argc < 3){
      cout<< "incorrect arguments" << endl;
      return 1;
   }
   const int TABLE_SIZE = atoi(argv[1]);
   const int NUM_ELEMENTS = atoi(argv[2]);
   HashTable* hash = new HashTable(TABLE_SIZE);
   for(int i = 0; i < NUM_ELEMENTS; i++){
      hash->insert(i);
   }
   hash->print(0);
   cout<< "DONE" <<endl;

   return 0;
}

[hermione.sampsons]

Can you please explain how your hash funcion works? The use of the numbers and letter to add to the value a.

[deceptikon]

Can you please explain how your hash funcion works? The use of the numbers and letter to add to the value a.

It's an integer hash described in detail here. But beware, the design of hash functions is a very deep hole.

[hermione.sampsons]

I think I'm trapped in that hole already.. But this would look good for my assignment.

Thanks. :-)

[hermione.sampsons]

How does the remove function work in this though?

[deceptikon]

How does the remove function work in this though?

Given that it's empty, I'd say it doesn't work. Or it does work, but it doesn't accomplish anything useful. ;) As far as what it should be doing, please see this tutorial for more details than I'd be willing to go through in a post.