template
class Hashtable
{
struct node **table; ///pointer to an array of pointers
int current_size;
int table_size;
int hashfn(string key)
{
int idx=0;
int p=1;
for(int j=0;key.length();j++)
{
idx=idx+(key[j]*p)%table_size; ////meaning (a+b+c)%x==( (a%x+b%x+c%x) )%m
idx=idx%table_size;
p=(p*27)%table_size; ////eg batman =b + 27*a + 27*27*t + 27*27*27*m.......
}
return idx;
}
public:
Hashtable(int ts=7) ///initially make an of size 7
{
table_size=ts;
table=new node<T>*[table_size];
current_size=0;
for(int i=0;i<table_size;i++)
{
table[i]=0;
}
}
void insert(string key,T value)
{
int idx=hashfn(key);
struct node <T> *n=new node<T>(key,value);
////Here we are inserting nodes at the head of the index eg
////we add node1 then node 2 then node3 now index will point to node2 and to node 2 and that to node1
n->next=table[idx];
table[idx]=n;
current_size++;
}
void print()
{
for(int i=0;i<table_size;i++)
{
cout<<"Bucket:"<<i<<"->";
struct node<T> *temp;
temp=table[i];
while(temp!=0)
{
cout<<temp->key<<" ";
temp=temp->next;
}
cout<<endl;
}
}
};
int main()
{
Hashtable price_menu;
price_menu.insert(“Burger”,120);
price_menu.insert(“Pepsi”,200);
price_menu.insert(“BurgerPizza”,150);
price_menu.insert(“Noodles”,25);
price_menu.insert(“Coke”,40);
price_menu.print();
}