Bureau du registrar ×YO Yannick Kengne Tat/X cs302-Cloud9 × mn Assignment x Asst

Question

Bureau du registrar ×YO Yannick Kengne Tat/X cs302-Cloud9 × mn Assignment x Asst6.pdf Description In this assignment, you will implement a custom hash class, which will behave similar to an array (you look up items by some index) thus you will overload the square brackets. The indices of this array object will be strings not integers. You will have two hash functions (the second hash function is used when a collisiorn occurs), and the hash table will be an array of linked lists where each element will have up to 2 nodes. Thus this hash table will be a combination of linear probing and chaining, the steps your algorithm will take is explained in the operator (std: :string) function template class m yHash struct node Type item; std::string key node link; 2; public: myHash (int 10) myHash (const myHash &) myHash& operator-(const myHash &) myHash ) Type& operator[] (std:: string); void resize (int); private: void destroyList ) int getIndex1 (std: string); int getIndex2 (std::string); int size; node ** myHashList; Implementation details Each member of the class will will perform/contain the following o struct node is every element in the hash will be of this type

Explanation / Answer

Answer: See the code below:

1. myHash.h: Header file

----------------------------------------------------

#ifndef MYHASH_H_
#define MYHASH_H_

#include <iostream>

using namespace std;

/**
* MyHash class
*/
template <class Type>
class myHash {
   //structure of a node in hash table
   struct node
   {
       Type item;
       std::string key;
       node *link;
   };
public:
   myHash(int = 10); //constrcutor
   myHash(const myHash<Type>&); //copy constructor
   myHash& operator=(const myHash<Type>&); //overloaded operator =
   virtual ~myHash(); //destructor
   Type& operator[](string); //overloaded operator []
   void resize(int); //resize function
private:
   void destroyList(); //destroyList function
   int getIndex1(string); //getIndex1 function
   int getIndex2(string); //getIndex2 function
   int size; //size of hash table
   node **myHashList; //hash table
};

#endif /* MYHASH_H_ */

--------------------------------------------------------

2. myHash.cpp: CPP file

--------------------------------------------------------

#include "myHash.h"

//impelementation of functions of myHash class

//constructor
template <class Type> myHash<Type>::myHash(int init) {
   this->size = init;
   this->myHashList = new node*[this->size];
   for(int i=0;i<this->size;i++)
   {
       this->myHashList[i]=NULL;
   }
}

//copy constructor
template <class Type> myHash<Type>::myHash(const myHash<Type>& copy) {
   this->size = copy.size;
   destroyList();
   this->myHashList = new node*[this->size];
   for(int i=0;i<this->size;i++)
   {
       this->myHashList[i]=copy.myHashList[i];
   }
}

//overloaded operator =
template <class Type> myHash<Type>& myHash<Type>::operator=(const myHash<Type>& rhs) {
   this->size = rhs.size;
   destroyList();
   this->myHashList = new node*[this->size];
   for(int i=0;i<this->size;i++)
   {
       this->myHashList[i]=rhs.myHashList[i];
   }
   return this;
}

//overloaded []
template <class Type> Type& myHash<Type>::operator[](string searchKey)
{
   int index = getIndex1(searchKey); //get index w.r.t searchKey in hashtable
   //hashtable node at given index
   node* entry = myHashList[index];
   //check if entry at given index is empty i.e. NULL
   if(entry == NULL)
   {
       //create a new node to store search key
       node* newNode = new node;
       newNode->link = NULL;
       newNode->key = searchKey;
       //store newNode in hashtable
       entry = newNode;
       return newNode->item; //return item
   }
   else //if entry at given index is not empty
   {
       if(entry->key == searchKey) //searchKey is found in hashtable
       {
           return entry->item; //return item
       }
       else if(entry->link == NULL) //check if there is only one entry at given index
       {
           //create a new node to store search key
           node* newNode = new node;
           newNode->link = NULL;
           newNode->key = searchKey;
           //store newNode in hashtable
           entry->link = newNode;
           return newNode->item; //return item
       }
       else if(entry->link != NULL && entry->link->key == searchKey) //check for another node at the same position
       {
           return entry->link->item; //return item
       }
       else //if searchKey not found at all
       {
           index = getIndex2(searchKey); //get alternate index in hashtable
           entry = myHashList[index];
           //check if entry at given index is empty i.e. NULL
           if(entry == NULL) //first collision
           {
               //create a new node to store search key
               node* newNode = new node;
               newNode->link = NULL;
               newNode->key = searchKey;
               //store newNode in hashtable
               entry = newNode;
               return newNode->item; //return item
           }
           else //after first collision
           {
               int i;
               for(i = 0;i<this->size;i++)
               {
                   index = (index+1)%this->size;
                   entry = myHashList[index];
                   if(entry == NULL)
                   {
                       //create a new node to store search key
                       node* newNode = new node;
                       newNode->link = NULL;
                       newNode->key = searchKey;
                       //store newNode in hashtable
                       myHashList[index] = newNode;
                       return newNode->item; //return item
                   }
               }
               if(i==this->size) //overflow. searchKey cannot be stored
               {
                   cerr<<"Hashtable overflow!!! Can't perform operation."<<endl;
                   return;
               }
           }
       }
   }
}

//resize function
template <class Type> void myHash<Type>::resize(int amount)
{
   int sz = this->size + amount; //new size of hashtable
   node** newHashList = new node*[sz]; //resized hashtable
   //initialize new hashtable
   for(int i = 0;i<sz;i++)
   {
       newHashList[i]=NULL;
   }
   //rehash all entries of hash table
   for(int i=0;i<this->size;i++)
   {
       node* entry = this->myHashList[i];
       //rehashed index
       int index = (i+1)%sz;
       newHashList[index]=entry; //store entry at rehashed location in hashtable
   }
   //update references
   this->size=sz;
   this->myHashList = newHashList;
}

//destructor
template <class Type> myHash<Type>::~myHash() {
   // TODO Auto-generated destructor stub
   destroyList();
}

//destroyList function
template <class Type> void myHash<Type>::destroyList()
{
   //delete hashtable entries
   for(int i=0;i<this->size;i++)
   {
       node* entry = this->myHashList[i];
       //fist check if entry has more than one node
       //if yes, then delete that node first
       if(entry->link != NULL)
       {
           delete entry->link;
       }
       //now delete entry
       delete entry;
   }
   //delete hashtable once all entries are deleted.
   delete this->myHashList;
}

//getIndex1 function
template <class Type> int myHash<Type>::getIndex1(string str)
{
   return str[0]%this->size;
}

//getIndex1 function
template <class Type> int myHash<Type>::getIndex2(string str)
{
   return str[str.length()-1]%this->size;
}

-------------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.