#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include<unordered_set>
#include<unordered_map>
#include
#include
#include
using namespace std;
template
class node{
public:
string key;
T value;
nodenext;
node(string key,T val)
{
this->key=key;
value=val;
next=nullptr;
}
~node()
{
if(next!=nullptr)
delete next;
}
};
template
class hashtable{
private:
node**table;
int current_size;
int table_size;
int hashfn(string key);
void rehash();
public:
hashtable(int ts=7);
void insert(string key,T val);
T search(string key);
void erase(string key);
void print();
};
template
hashtable::hashtable(int ts)
:current_size{0},table_size{ts},table{new node[table_size]}
{
for(int i{0};i<table_size;i++)
table[i]=nullptr;
}
template
int hashtable::hashfn(string key)
{
int idx=0;
int p=1;
for(int j{0};j<key.length();j++)
{
idx=idx+(key[j]p)%table_size;
idx=idx%table_size;
p=(p27)%table_size;
}
return idx;
}
template
void hashtable::rehash()
{
node**old_table=table;
int old_size=table_size;
table_size=2table_size;
table=new node*[table_size];
for(int i=0;i<table_size;i++)
table[i]=nullptr;
current_size=0;
for(int i=0;i<old_size;i++)
{
node *temp=old_table[i];
while(temp!=nullptr)
{
insert(temp->key,temp->value);
temp=temp->next;
}
if(old_table[i]!=nullptr)
delete old_table[i];
}
delete[]old_table;
}
template
void hashtable::insert(string key,T val)
{
int idx=hashfn(key);
noden=new node(key,val);
n->next=table[idx];
table[idx]=n;
current_size++;
float loading_factor=current_size/(1.0table_size);
if(loading_factor>0.70)
rehash();
}
template
void hashtable::print()
{
for(int i=0;i<table_size;i++)
{
cout<<“bucket: “<<i<<”---->”;
nodetemp=table[i];
while(temp!=nullptr)
{
cout<key<<"->";
temp=temp->next;
}
cout<<endl;
}
}
template
T hashtable::search(string key)
{
int idx=hashfn(key);
node*temp=table[idx];
while(temp!=nullptr)
{
if(temp->key==key)
return temp;
temp=temp->next;
}
return nullptr;
}
template
void hashtable::erase(string key)
{
int idx=hashfn(key);
node*temp=table[idx];
node*tail=nullptr;
while(temp!=nullptr)
{
if(temp->key==key)
{
if(temp==table[idx])
{
node*Node=temp->next;
delete temp;
table[idx]=Node;
}
else
{
tail->next=temp->next;
delete temp;
}
}
tail=temp;
temp=temp->next;
}
return;
}
int main()
{
hashtablemenu(7);
menu.insert(“burger”,150);
menu.insert(“pizza”,200);
menu.insert(“pepsi”,57);
menu.print();
}
What is the problem in the hash table code?!
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.