fork download
copy 
  1. #include<iostream>
  2. #include<cstring>
  3. using namespace std;
  4.  
  5. template<typename T>
  6. class node{
  7. public:
  8.     string key;
  9.     T value;
  10.     node<T>*next;
  11.     node(string key, T val){
  12.         this->key = key;
  13.         value = val;
  14.         next = NULL;
  15.     }
  16.     ~node(){
  17.         if(next!=NULL){
  18.             delete next;
  19.         }
  20.     }
  21. };
  22. template<typename T>
  23. class HashTable{
  24.     node<T>** table; //pointer to an array of pointers
  25.     int current_size;
  26.     int table_size;
  27.  
  28.     int hashfn(string key){
  29.         int idx = 0;
  30.         int p=1;
  31.         for(int j=0;j<key.length();j++){
  32.             idx = idx + (key[j]*p)%table_size;
  33.             idx = idx%table_size;
  34.             p = (p*27)%table_size;
  35.         }
  36.         return idx;
  37.     }
  38.  
  39.     void rehash(){
  40.         node<T>** oldTable = table;
  41.         int oldTableSize = table_size;
  42.         table_size = 2*table_size;
  43.         table = new node<T>*[table_size];
  44.         //initialize new table buckets with null
  45.         //now oldtable has data and new table is null
  46.         for(int i=0;i<table_size;i++){
  47.             table[i] = NULL;
  48.         }
  49.         current_size = 0;
  50.         //shift data from old table to new table
  51.         for(int i=0;i<oldTableSize;i++){
  52.             node<T>*temp = oldTable[i];
  53.  
  54.             while(temp!=NULL){
  55.                 insert(temp->key,temp->value);
  56.                 temp = temp->next;
  57.             }
  58.             //delete this entire row from oldtable
  59.             if(oldTable[i]!=NULL){
  60.                 delete oldTable[i];
  61.             }
  62.  
  63.         }
  64.         delete [] oldTable;
  65.     }
  66. public:
  67.     HashTable(int ts = 7){
  68.         table_size = ts;
  69.         table = new node<T>*[table_size];
  70.         current_size = 0;
  71.         for(int i=0;i<table_size;i++){
  72.             table[i] = NULL;
  73.         }
  74.     }
  75.  
  76.     void insert(string key , T value){
  77.         int idx = hashfn(key);
  78.         node<T>*n = new node<T>(key,value);
  79.         //insert at head  of linkedlist with id=idx
  80.         n->next = table[idx];
  81.         table[idx]=n;
  82.         current_size++;
  83.  
  84.         //rehash
  85.         float load_factor = current_size/(1.0*table_size);
  86.         if(load_factor>0.7){
  87.             rehash();
  88.         }
  89.     }
  90.     void print (){
  91.         for(int i=0;i<table_size;i++){
  92.            cout<<"bucket"<<i<<"->";
  93.            node<T>*temp = table[i];
  94.            while(temp!=NULL){
  95.                 cout<<temp->key<<"->";
  96.                 temp=temp->next;
  97.            }
  98.             cout<<endl;
  99.         }
  100.     }
  101.  
  102.     T* Search(string key){
  103.         int idx = hashfn(key);
  104.         node<T>*temp = table[idx];
  105.         while(temp!=NULL){
  106.             if(temp->key == key){
  107.                 return &temp->value;
  108.             }
  109.             temp = temp->next;
  110.         }
  111.         return NULL;
  112.     }
  113.  
  114.     void Erase(string key){
  115.         int idx = hashfn(key);
  116.         node<T>*temp = table[idx];
  117.          node<T>*prev = NULL;
  118.  
  119.  
  120.  
  121.         while(temp->next!=NULL){
  122.             if(temp->next->key == key){
  123.                 prev = temp;
  124.                 prev->next = temp->next->next;
  125.                 delete temp->next;
  126.             }
  127.             temp = temp->next;
  128.         }
  129.         return;
  130.     }
  131. };
  132.  
  133. int main(){
  134.     HashTable<int>price_menu;
  135.     price_menu.insert("burger",120);
  136.     price_menu.insert("pepsi",80);
  137.     price_menu.insert("burgerpizza",90);
  138.     price_menu.insert("noodles",150);
  139.     price_menu.insert("coke",50);
  140.     price_menu.print();
  141.     int *price = price_menu.Search("noodles");
  142.     if(price!=NULL){
  143.         cout<<"found "<<*price;
  144.     }
  145.     else{
  146.         cout<<"not found";
  147.     }
  148.     price_menu.Erase("noodles");
  149.     price_menu.print();
  150. return 0;}
  151.  
Success #stdin #stdout 0s 4312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
bucket0->
bucket1->pepsi->
bucket2->
bucket3->
bucket4->
bucket5->
bucket6->noodles->
bucket7->burger->
bucket8->coke->
bucket9->
bucket10->
bucket11->
bucket12->
bucket13->burgerpizza->
found 150bucket0->
bucket1->pepsi->
bucket2->
bucket3->
bucket4->
bucket5->
bucket6->noodles->
bucket7->burger->
bucket8->coke->
bucket9->
bucket10->
bucket11->
bucket12->
bucket13->burgerpizza->
https://ideone.com/w5Iyiy
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!