#include
#include
using namespace std;
template
class node{
public:
string key;
T value;
node* next;
node(string key, T val)
{
this->key=key;
this->value=val;
next=NULL;
}
~node()
{
if(next!=NULL)
{
delete next;
}
}
};
template
class hashtable{
node** table;
int current_size;
int table_size;
int 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=(p*27)%table_size;
}
return idx;
}
void rehash(){
node<T>** oldtable=table;
int oldtablesize=table_size;
table_size=2*table_size;
table=new node<T>*[table_size];
for(int i=0;i<table_size;i++)
{
table[i]=NULL;
}
current_size=0;
for(int i=0;i<oldtablesize;i++)
{
node<T>*temp=oldtable[i];
while(temp!=NULL)
{
insert(temp->key,temp->value);
temp=temp->next;
}
if(oldtable[i]!=NULL)
{
delete oldtable[i];
}
}
delete [] oldtable;
}
public:
hashtable(int ts=7)
{
table_size=ts;
table = new node<T>*[table_size];
current_size=0;
for(int i=0;i<table_size;i++)
{
table[i]=NULL;
}
}
void insert(string key,T value)
{
int idx=hashFn(key);
node<T>*n=new node<T>(key,value);
n->next=table[idx];
table[idx]=n;
float load_factor=current_size/(1.0*table_size);
if(load_factor>0.5)
{
rehash();
}
}
void print()
{
for(int i=0;i<table_size;i++)
{
cout<<"Bucket"<<i<<"->";
node<T>*temp=table[i];
while(temp!=NULL)
{
cout<<temp->key<<"->";
temp=temp->next;
}
cout<<endl;
}
}
};
int main()
{
hashtable price_menu;
price_menu.insert(“Burger”,120);
price_menu.insert(“Pepsi”,20);
price_menu.insert(“BurgerPizza”,150);
price_menu.insert(“Noodles”,25);
price_menu.insert(“Coke”,40);
price_menu.print();
}