3file with code.Please Follow Hashtable.cpp main.cpp and hastable.h!! Create a t
ID: 3844930 • Letter: 3
Question
3file with code.Please Follow
Hashtable.cpp
main.cpp
and hastable.h!!
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 t he 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
Here is the c++ code for the above question,
hashtable.h
#include <iostream.h>
#include <stdlib.h>
#include<constream.h>
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
};
Hashtable.cpp
#include <iostream.h>
#include <stdlib.h>
#include<hashtable.h>
#include<constream.h>
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 {
friend void main(void);
public:
operator long() const {return key;}
private:
int data;
long key;
};
main.cpp
#include <iostream.h>
#include <stdlib.h>
#include<hashtable.h>
#include<constream.h>
void main(void)
{
clrscr();
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();
getch();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.