+1 (315) 557-6473 

Program To Implement All Hashing Tables in C++ Language Assignment Solution.


Instructions

Objective
Write a program to implement all hashing tables in C++ language in C++ language.

Requirements and Specifications

implement all hashing tables in C++

Source Code

#include <iostream>

#include <fstream>

#include <iomanip>

#include <cstdlib>

using namespace std;

//unsigned for positive numbers or zero only. long takes up 4 bytes. 0-2^32(4294967295)

unsigned long hashNum(const string& key);

class entry //this is basically a node

{

  //What do you do if hashTbl needs to access the private members of entry?

  //If you don't say private or public, it is private by default.

  string ID;

  string name;

  int age;

  double GPA;

  entry* next; //points to the next entry

public:

  entry() { ID = name = "", age = -999, GPA = -999.0, next = NULL; }

  entry(const string& ID, const string& name, int age, double GPA ) { this->ID = ID, this->name = name, this->age = age, this->GPA = GPA, next = NULL; }

  string getID() const { return ID; }

  string getName() const { return name; }

  int getAge() const { return age; }

  double getGPA() const { return GPA; }

  entry* getNext() const { return next; }

  void setNext(entry* nxt) {

  next = nxt;

 }

};

class hashTbl

{

  entry** table; //table points to a dynamic array. Each slot points to an entry, which points to the next entry, ...

  int size; //size of the array

public:

  hashTbl(int size);

  ~hashTbl();

  void put(entry* e); //add a new entry to the table

  entry* get(const string& key) const; //look up a key

  entry remove(const string& key); //remove an entry

  entry** getTbl() const {return table;} //return the pointer to the table

  class underflow //exception class - used when key wasn't found

  {

    string message;

  public:

    underflow(const string& mes) { message = mes; }

    string getMessage() { return message; }

  };

};

//constructor

//s is the size of the table

hashTbl::hashTbl(int s)

{

  //set private member size

  //make a dynamic array that has s slots

  //put NULL in each slot of the array. Remember Each slot contains a pointer to an entry.

 size = s;

 table = new entry*[size];

 for(int i = 0; i<size; i++) {

  table[i] = NULL;

 }

}

//destructor

hashTbl::~hashTbl()

{

  //you need to destroy everything created using new.

  //destroy all the entries belong to each slot of the table

  //don't forget to destroy the dynamic array

 for(int i = 0; i<size; i++) {

  entry* curr = table[i];

  while(curr != NULL) {

   entry* tmp = curr->getNext();

   delete curr;

   curr = tmp;

  }

 }

 delete[] table;

}

//insert an entry to the table

//e is a pointer to an entry

void hashTbl::put(entry* e)

{

  //This function is like LL::addFront() from CS211

  string key = e->getID(); //use ID for key

  //add the entry at the beginning of the list coming out of index

  int index = (hashNum(key)) % size;

 e->setNext(table[index]);

 table[index] = e;

}

//look up key and return the pointer to it. Assume keys are unique.

entry* hashTbl::get(const string& key) const

{

  //This function is like LL::search() from CS211

 int index = (hashNum(key)) % size;

 entry* curr = table[index];

 while(curr != NULL) {

  if (curr->getID() == key) {

   return curr;

  }

  curr = curr->getNext();

 }

 throw underflow(key);

}

//remove the entry with key. Assume keys are unique.

entry hashTbl::remove(const string& key)

{

  //This function is like LL::remove() from CS211

 //Don't forget to return the entry found

 //Don't make a memory leak

 int index = (hashNum(key)) % size;

  entry* curr = table[index];

 if (curr == NULL) {

  throw underflow(key);

 }

 while(curr->getNext() != NULL) {

  if (curr->getNext()->getID() == key) {

   entry* toRemove = curr->getNext();

   entry e(toRemove->getID(), toRemove->getName(), toRemove->getAge(), toRemove->getGPA());

   delete toRemove;

   return e;

  }

  curr = curr->getNext();

 }

 throw underflow(key);

}

//well known hash function called djb2

//http://www.cse.yorku.ca/~oz/hash.html

//For explanation of bit shifting, http://www.cplusplus.com/forum/beginner/95670/

//unsigned for positive numbers or zero only. long takes up 8 bytes (8 bytes * 8 bits = 64 bits). The range in decimal is 0 through 2^64 - 1(18446744073709551615)

unsigned long hashNum(const string& key)

{

  const char* cstr = key.c_str(); //converting C++ string to c-string. A c-string is a character array that is terminated by a '\0' (NULL terminator).

  unsigned long hash = 5381;

  int c;

  while (c = *cstr++) //checking each character until it reaches '\0'. When it reaches '\0', c gets the ascii number of '\0', which is 0. 0 means false -> getting out of while.

    {

      hash = ((hash << 5) + hash) + c;//hash * 33 + c;

    }

  return hash;

}

void showInfo(const entry& e);

void showTable(const int count[], const hashTbl& students);

const int SIZE = 1009; //For closed addressing, you don't need to worry about load factor.

                       //The table size still should be at least the number of items and also a prime number.

                       //There are 1000 people in the input file.

int main()

{

  //make a hash table object called students with SIZE slots

  int count[SIZE] = {0}; //set all slots to 0. Used to see count in each index

  ifstream fin;

  fin.open("hash.in");

  string id;

  string name;

  int age;

  double gpa;

 hashTbl students(50);

  if(!fin)

    {

      cout << "The input file doesn't exist" << endl;

      return 0;

    }

  //adding entries from the input file

  fin >> id >> name >> age >> gpa;

  while(fin)

    {

      count[hashNum(id)%SIZE]++;//trying to see how many entries go into each slot

      students.put(new entry(id, name, age, gpa));

      fin >> id >> name >> age >> gpa;

    }

  //show the statistic about the table

  showTable(count, students);

  //put entries into the table

  students.put(new entry("T1234567891", "Tom", 23, 4.0));

  students.put(new entry("F5432112345", "Fred", 45, 3.5));

  students.put(new entry("L1357915987", "Linsey", 48, 2.0));

  //searches and returns students in table without removing

  try

    {

      cout << "trying to search" << endl;

      showInfo(*(students.get("P1429911332")));//middle at index 377

      showInfo(*(students.get("Y1098431884"))); //first entry at index 377

      showInfo(*(students.get("V1025438181"))); //last entry at index 377

      showInfo(*(students.get("A1234567891"))); //probably doesn't exist

      //search for key and show their info

    }

  catch (hashTbl::underflow obj)

    {

      cout << "Student with ID: " << obj.getMessage() << " could not be found" << endl;

    }

  //Try to remove a student from table

  try

    {

      cout << "trying to remove" << endl;

      showInfo((students.remove("P1429911332"))); //3rd entry at index 377

      showInfo((students.remove("V1025438181"))); //last entry(now 4th) at index 377

      showInfo((students.remove("Y1098431884"))); //first entry at index 377

      showInfo((students.remove("A1234567891"))); //probably it doesn't exist

    }

  catch (hashTbl::underflow obj)

    {

      cout << "Student with ID: " << obj.getMessage() << " could not be removed" << endl;

    }

  return 0;

}

//Show the information about an entry

void showInfo(const entry& e)

{

 cout << e.getID() << " " << e.getName() << " " << e.getAge() << " " << e.getGPA() << endl;

}

//Show the statistic about the hash table

void showTable(const int count[], const hashTbl& students)

{

  //we want to know the highest, lowest and empty counts

  int lowest = 1001;

  int highest = -1;

  int empty = 0;

  int hi_i; //index of the highest count

  cout << "print table" << endl;

  for(int i = 0; i < SIZE; i++)

    {

      if(count[i] < lowest)

        lowest = count[i];

      if(count[i] > highest)

 {

   highest = count[i];

   hi_i = i;

 }

      if(count[i] == 0)

        empty++;

      cout << setw(3) << count[i];

      if((i+1)%50 == 0)//Show 50 numbers per line

        cout << endl;

    }

  cout << endl << endl << "lowest is " << lowest << " highest is " << highest << " empty is " << empty << endl;

  cout << "highest count is at " << hi_i << endl;

  //Show the entries at the index that has the highest count

  entry* p = students.getTbl()[hi_i];

  while(p != NULL)

  {

      showInfo(*p);

      p = p->getNext();

    }

  cout << endl;

}