fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename T>
  5. class Node {
  6. public:
  7.     string key;
  8.     T value;
  9.     Node<T> *next;
  10.  
  11.     Node( string key , T val ) {
  12.         this->key = key;
  13.         value = val;
  14.         next = NULL;
  15.     }
  16.  
  17.     ~Node() {
  18.         while ( next != NULL ) {
  19.             delete next;
  20.         }
  21.     }
  22.  
  23. };
  24.  
  25. template<typename T>
  26. class Hashtable {
  27.     Node<T>**table;
  28.     int current_Size;
  29.     int table_Size;
  30.  
  31.     int hashFn( string key ) {
  32.         int idx = 0;
  33.         int p = 1; // base 27 integer
  34.         for ( int j = 0 ; j < key.length() ; j++ ) {
  35.             idx = idx + ( ( key[j] * p ) % table_Size );
  36.             idx = idx % table_Size;
  37.             p = ( p * 27 ) % table_Size;
  38.         }
  39.  
  40.         return idx;
  41.     }
  42.  
  43.     void rehash() {
  44.         Node<T>**oldTable = table;
  45.         int oldTableSize = table_Size;
  46.         table_Size = 2 * table_Size+3;
  47.         current_Size = 0;
  48.         table = new Node<T>*[table_Size];
  49.  
  50.         for ( int i = 0 ; i < table_Size ; i++ ) {
  51.             table[i] = NULL;
  52.         }
  53.         current_Size = 0;
  54.         for ( int i = 0 ; i < oldTableSize ; i++ ) {
  55.             Node<T> *temp = oldTable[i];
  56.             while ( temp != NULL ) {
  57.                 insert( temp->key , temp->value );
  58.                 current_Size++;
  59.                 temp = temp->next;
  60.             }
  61.  
  62.             if ( oldTable[i] != NULL ) {
  63.                 delete oldTable[i];
  64.             }
  65.         }
  66.  
  67.         delete [] oldTable;
  68.     }
  69.  
  70. public:
  71.     Hashtable( int ts = 7 ) {
  72.         current_Size = 0;
  73.         table_Size = ts;
  74.         table = new Node<T>*[table_Size]; // table pointer is a pointer containing address of a node pointer ( array of pointers )
  75.  
  76.         for ( int i = 0 ; i < table_Size ; i++ ) {
  77.             table[i] = NULL;
  78.         }
  79.     }
  80.  
  81.     void print() {
  82.         for ( int i = 0 ; i < table_Size ; i++ ) {
  83.             cout << "Bucket " << i << " -> ";
  84.             Node<T> *temp = table[i];
  85.             while ( temp != NULL ) {
  86.                 cout << "( " << temp->key << " , " << temp->value << " ) -> ";
  87.                 temp = temp->next;
  88.             }
  89.             cout << endl;
  90.         }
  91.  
  92.     }
  93.  
  94.     void insert( string key , T value ) {
  95.         int idx = hashFn( key );
  96.  
  97.         Node<T> *n = new Node<T>( key , value );
  98.  
  99.         // insert the given node in the linklist present at the idx in the hashtable
  100.         n->next = table[idx];
  101.         table[idx] = n;
  102.         current_Size++;
  103.  
  104.         // rehashing..
  105.         int loadFactor = current_Size / ( 1.0 * table_Size );
  106.         if ( loadFactor > 0.7 ) {
  107.             rehash();
  108.         }
  109.  
  110.     }
  111.  
  112.     /*
  113.     T search( string key ) {
  114.  
  115.     }
  116.  
  117.     void erase( string key ) {
  118.  
  119.     }
  120.     */
  121.  
  122. };
  123.  
  124. int main() {
  125.     Hashtable<int> food_Menu;
  126.  
  127.     food_Menu.insert("Burger", 120);
  128.     food_Menu.insert("Pizza", 150);
  129.     food_Menu.insert("Coke", 20);
  130.     food_Menu.insert("Noodles", 60);
  131.     food_Menu.insert("Icecream", 40);
  132.  
  133.     food_Menu.print();
  134. }
Success #stdin #stdout 0s 4256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Bucket 0 -> 
Bucket 1 -> 
Bucket 2 -> ( Noodles , 60 ) -> ( Pizza , 150 ) -> 
Bucket 3 -> ( Burger , 120 ) -> 
Bucket 4 -> ( Coke , 20 ) -> 
Bucket 5 -> ( Icecream , 40 ) -> 
Bucket 6 ->
https://ideone.com/ugG03F
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

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!