C++ Program to Implement Hash Tables with Double Hashing

«
»
This C++ Program demonstrates operations on Hash Tables with Double Hashing.

Here is source code of the C++ Program to demonstrate Hash Tables with Double Hashing. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Hash Tables with Double Hashing
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #define MIN_TABLE_SIZE 10
  7. using namespace std;
  8. /*
  9.  * Node Type Declaration
  10.  */
  11. enum EntryType {Legitimate, Empty, Deleted};
  12. /*
  13.  * Node Declaration
  14.  */
  15. struct HashNode
  16. {
  17.     int element;
  18.     enum EntryType info;
  19. };
  20. /*
  21.  * Table Declaration
  22.  */
  23. struct HashTable
  24. {
  25.     int size;
  26.     HashNode *table;
  27. };
  28. /*
  29.  * Function to Genereate First Hash
  30.  */
  31. int HashFunc1(int key, int size)
  32. {
  33.     return key % size;
  34. }
  35. /*
  36.  * Function to Genereate Second Hash
  37.  */
  38. int HashFunc2(int key, int size)
  39. {
  40.     return (key * size - 1) % size;
  41. }
  42. /*
  43.  * Function to Initialize Table
  44.  */
  45. HashTable *initializeTable(int size)
  46. {
  47.     HashTable *htable;
  48.     if (size < MIN_TABLE_SIZE)
  49.     {
  50.         cout<<"Table Size Too Small"<<endl;
  51.         return NULL;
  52.     }
  53.     htable = new HashTable;
  54.     if (htable == NULL)
  55.     {
  56.         cout<<"Out of Space"<<endl;
  57.         return NULL;
  58.     }
  59.     htable->size = size;
  60.     htable->table = new HashNode [htable->size];
  61.     if (htable->table == NULL)
  62.     {
  63.         cout<<"Table Size Too Small"<<endl;
  64.         return NULL;
  65.     }
  66.     for (int i = 0; i < htable->size; i++)
  67.     {
  68.         htable->table[i].info = Empty;
  69.         htable->table[i].element = NULL;
  70.     }
  71.     return htable;
  72. }
  73. /*
  74.  * Function to Find Element from the table
  75.  */
  76. int Find(int key, HashTable *htable)
  77. {
  78.     int hashVal= HashFunc1(key, htable->size);
  79.     int stepSize= HashFunc2(key, htable->size);
  80.     while (htable->table[hashVal].info != Empty &&
  81.            htable->table[hashVal].element != key)
  82.     {
  83.         hashVal = hashVal + stepSize;
  84.         hashVal = hashVal % htable->size;
  85.     }
  86.     return hashVal;
  87. }
  88. /*
  89.  * Function to Insert Element into the table
  90.  */
  91. void Insert(int key, HashTable *htable)
  92. {
  93.     int pos = Find(key, htable);
  94.     if (htable->table[pos].info != Legitimate )
  95.     {
  96.         htable->table[pos].info = Legitimate;
  97.         htable->table[pos].element = key;
  98.     }
  99. }
  100. /*
  101.  * Function to Rehash the table
  102.  */
  103. HashTable *Rehash(HashTable *htable)
  104. {
  105.     int size = htable->size;
  106.     HashNode *table = htable->table;
  107.     htable = initializeTable(2 * size);
  108.     for (int i = 0; i < size; i++)
  109.     {
  110.         if (table[i].info == Legitimate)
  111.             Insert(table[i].element, htable);
  112.     }
  113.     free(table);
  114.     return htable;
  115. }
  116. /*
  117.  * Function to Retrieve the table
  118.  */
  119. void Retrieve(HashTable *htable)
  120. {
  121.     for (int i = 0; i < htable->size; i++)
  122.     {
  123.         int value = htable->table[i].element;
  124.         if (!value)
  125.             cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
  126.         else
  127.             cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
  128.     }
  129.  
  130. }
  131. /*
  132.  * Main Contains Menu
  133.  */
  134. int main()
  135. {
  136.     int value, size, pos, i = 1;
  137.     int choice;
  138.     HashTable *htable;
  139.     while(1)
  140.     {
  141.         cout<<"\n----------------------"<<endl;
  142.         cout<<"Operations on Double Hashing"<<endl;
  143.         cout<<"\n----------------------"<<endl;
  144.         cout<<"1.Initialize size of the table"<<endl;
  145.         cout<<"2.Insert element into the table"<<endl;
  146.         cout<<"3.Display Hash Table"<<endl;
  147.         cout<<"4.Rehash The Table"<<endl;
  148.         cout<<"5.Exit"<<endl;
  149.         cout<<"Enter your choice: ";
  150.         cin>>choice;
  151.         switch(choice)
  152.         {
  153.         case 1:
  154.             cout<<"Enter size of the Hash Table: ";
  155.             cin>>size;
  156.             htable = initializeTable(size);
  157.             break;
  158.         case 2:
  159.             if (i > htable->size)
  160.             {
  161.                 cout<<"Table is Full, Rehash the table"<<endl;
  162.                 continue;
  163.             }
  164.         	cout<<"Enter element to be inserted: ";
  165.         	cin>>value;
  166.             Insert(value, htable);
  167.             i++;
  168.             break;
  169.         case 3:
  170.             Retrieve(htable);
  171.             break;
  172.         case 4:
  173.             htable = Rehash(htable);
  174.             break;
  175.         case 5:
  176.             exit(1);
  177.         default:
  178.            cout<<"\nEnter correct option\n";
  179.        }
  180.     }
  181.     return 0;
  182. }

advertisement
$ g++ Double_Hashing.cpp
$ a.out
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 5
Table Size Too Small
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 10
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: Null
Position: 3 Element: Null
Position: 4 Element: Null
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: Null
Position: 9 Element: Null
Position: 10 Element: Null
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 10
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 20
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 30
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 40
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 50
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 60
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 70
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 80
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 90
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 100
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 10
Position: 2 Element: 100
Position: 3 Element: 90
Position: 4 Element: 80
Position: 5 Element: 70
Position: 6 Element: 60
Position: 7 Element: 50
Position: 8 Element: 40
Position: 9 Element: 30
Position: 10 Element: 20
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 4
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 100
Position: 2 Element: Null
Position: 3 Element: Null
Position: 4 Element: Null
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: 30
Position: 8 Element: 50
Position: 9 Element: 70
Position: 10 Element: 90
Position: 11 Element: 10
Position: 12 Element: Null
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: 20
Position: 18 Element: 40
Position: 19 Element: 60
Position: 20 Element: 80
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 2000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 3000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 4000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 5000 
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 100
Position: 2 Element: Null
Position: 3 Element: Null
Position: 4 Element: Null
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: 30
Position: 8 Element: 50
Position: 9 Element: 70
Position: 10 Element: 90
Position: 11 Element: 10
Position: 12 Element: 5000
Position: 13 Element: 4000
Position: 14 Element: 3000
Position: 15 Element: 2000
Position: 16 Element: 1000
Position: 17 Element: 20
Position: 18 Element: 40
Position: 19 Element: 60
Position: 20 Element: 80
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 6000
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 100
Position: 2 Element: Null
Position: 3 Element: Null
Position: 4 Element: Null
Position: 5 Element: Null
Position: 6 Element: 6000
Position: 7 Element: 30
Position: 8 Element: 50
Position: 9 Element: 70
Position: 10 Element: 90
Position: 11 Element: 10
Position: 12 Element: 5000
Position: 13 Element: 4000
Position: 14 Element: 3000
Position: 15 Element: 2000
Position: 16 Element: 1000
Position: 17 Element: 20
Position: 18 Element: 40
Position: 19 Element: 60
Position: 20 Element: 80
 
----------------------
Operations on Double Hashing
 
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 5
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn