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

#include <iostream>
#include <stdlib.h>

using namespace std;

template<class E, class K>
class HashTable {
public:
  HashTable(int divisor = 11);
  ~HashTable() {delete [] ht;
   delete [] empty;}
   int Search(const K& k, E& e) const;
   HashTable<E,K>& Insert(const E& e);
   void Output();// output the hash table
   void del(E e);
private:
   int hSearch(const K& k) const;
   int D; // hash function divisor
   E *ht; // hash table array
   int *empty; // 1D array
};
template<class E, class K>
HashTable<E,K>::HashTable(int divisor)
{// Constructor.
D = divisor;
ht = new E [D];
empty = new int [D];

for (int i = 0; i < D; i++)
  empty[i] = 1;
}
template<class E, class K>
int HashTable<E,K>::hSearch(const K& k) const
{
int i = k % D;
int j = i;
do {
  if (empty[j] || ht[j] == k) return j;
  j = (j + 1) % D; // next bucket
} while (j != i); // returned to home?
return j; // table full
}
template<class E, class K>
void HashTable<E,K>::del(E e)
{
int b=hSearch(e);
if( !empty[b] && ht[b]==e)
{
  ht[b]=0;
  empty[b]=1;
}
else
  cout<<" element not found";

}
template<class E, class K>
int HashTable<E,K>::Search(const K& k, E& e) const
{
int b = hSearch(k);
if (empty[b] || ht[b] != k) return 0;
e = ht[b];
return 1;
}
template<class E, class K>
HashTable<E,K>& HashTable<E,K>::Insert(const E& e)
{// Hash table insert.
K k = e; // extract key
int b = hSearch(k);
if (empty[b]) {empty[b] = 0;
  ht[b] = e;
  return *this;

}
if (ht[b] == k) { cout<<" bad input"; return *this; } // duplicate
cout<<" No memory";// table full
return *this;
}

template<class E, class K>
void HashTable<E,K>::Output()
{
cout<<endl;
for (int i = 0; i< D; i++) {
  if (empty[i]) cout << "0 ";
  else cout << ht[i]<<" ";}
cout<<endl;
}
class element {
public:
operator long() const {return key;}
private:
int data;
long key;
};

int main()
{
HashTable<int , int > h(11);
int e;
e = 80;
h.Insert(e);
e = 40;
h.Insert(e);
e = 65;
h.Insert(e);
cout<<" After inserting 80,40,65:";
h.Output();
cout<<endl;
h.del(40);
cout<<" After deleting 40:";
h.Output();
cout<<endl;
e = 58;
h.Insert(e);
e = 24;
h.Insert(e);
cout<<" after appending 58, 24:";
h.Output();
cout<<" Trying to delete element 25:";
h.del(25);
h.Output();
e = 2;
h.Insert(e);
e = 13;
h.Insert(e);
e = 46;
h.Insert(e);
e = 16;
h.Insert(e);
e = 7;
h.Insert(e);
e = 21;
h.Insert(e);
h.Insert(10);
cout <<"After inserting more values:" << endl;
h.Output();
e = 99;
cout<<" trying to insert 99:";
h.Insert(e);
h.Output();
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.