Create a template class for hashtable. If the user does not specify a size in th

Question

Create a template class for hashtable. If the user does not specify a size in the constructor then the default size of 20 will be used. In each slot you store a linkedlist of key-value pairs. The put function is responsible to get a key-value pair and put that pair in the likedlist located in the index of key%size. The get function receives a key and returns a value. If the number of inserted elements to the hashtable become larger than 75% of the size then the rehash function will be called, that creates a hashtable with a larger size (Double times larger) and put all the key-value pairs of the old table in the new table. If the number of elements in the linked list located in the hash bucket be 8 or greater than 8 then the linked list will be converted to a binary search tree (After you learned about balanced binary search trees, you can change to that data structure). The remove function accepts a key and removes the key-value pair. If the number of elements be 6 or smaller than 6 then the tree should be converted to a linked list. You need to have function size which returns the size of the table.

Explanation / Answer

Solution: See the code below:

1. Hashtable.h:

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

#ifndef HASHTABLE_H_
#define HASHTABLE_H_

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;
/**
* Hashtable template class
*/
template <class K, class V> class Hashtable {
private:
   K key;
   V value;
   struct HashEntry
   {
       K key;
       V value;
       HashEntry* next;
   };
   list<HashEntry*>** hashtable;
   int size;
public:
   Hashtable(int n = 20); //constructor
   void put(K key, V value); //puts a key-value pair in hash table
   V get(K key); //gets a value from hash table w.r.t. a given key
   V remove(K key); //removes a value from hash table w.r.t. a given key
   int hash(int key); //hash function for the table
   int getSize(); //returns size of hash table
};
#endif /* HASHTABLE_H_ */

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

2. Hashtable.cpp:

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

#include "Hashtable.h"

/**
* constructor
*/
template<class K, class V> Hashtable<K, V>::Hashtable(int n) {
   size = n;
   hashtable = new list<HashEntry>[size];
   for(int i=0; i<size;i++)
   {
       hashtable[i]=new list<HashEntry>();
   }
}

/**
* puts a key-value pair in hash table
*/
template<class K, class V>
void Hashtable<K, V>::put(K key, V value) {
   HashEntry* entry = new HashEntry;
   entry->key=key;
   entry->value=value;
   entry->next=NULL;
   int index = hash(key);
   hashtable[index]->push_back(entry);
}

/**
* gets a value from hash table w.r.t. a given key
*/
template<class K, class V>
V Hashtable<K, V>::get(K key) {
   int index = hash(key);
   V value;
   for(HashEntry *entry : hashtable[index])
   {
       if (entry->key == key)
       {
           value=entry->value;
           break;
       }
   }
   return value;
}

/**
* removes a value from hash table w.r.t. a given key
*/
template<class K, class V>
V Hashtable<K, V>::remove(K key) {
   int index = hash(key);
   V value;
   for(HashEntry *entry : hashtable[index])
   {
       if (entry->key == key)
       {
           value=entry->value;
           hashtable[index]->remove(entry);
           break;
       }
   }
   return value;
}

/**
* hash function for the table
*/
template<class K, class V>
int Hashtable<K, V>::hash(int key) {
   return key % size;
}

/**
* returns size of hash table
*/
template<class K, class V>
int Hashtable<K, V>::getSize() {
   return size;
}

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

3. main() function:

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

#include <iostream>
using namespace std;

int main() {
   Hashtable<int,int> hashtable;
   hashtable.put(1,1);
   hashtable.put(2,2);
   hashtable.put(3,3);
   cout<<"Value with 1:"<<hashtable.get(1)<<endl;
   return 0;
}

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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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