C++ Program to Implement Hash Tables with Quadratic Probing

«
»
This C++ Program demonstrates operations on Hash Tables with Quadratic Probing.

Here is source code of the C++ Program to demonstrate Hash Tables with Quadratic Probing. 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 Quadratic Probing
  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.  * Returns whether n is prime or not
  30.  */
  31. bool isPrime (int n)
  32. {
  33.     if (n == 2 || n == 3)
  34.         return true;
  35.     if (n == 1 || n % 2 == 0)
  36.         return false;
  37.     for (int i = 3; i * i <= n; i += 2)
  38.         if (n % i == 0)
  39.             return false;
  40.     return true;
  41. }
  42. /*
  43.  * Finding next prime size of the table
  44.  */
  45. int nextPrime(int n)
  46. {
  47.     if (n <= 0)
  48.         n == 3;
  49.     if (n % 2 == 0)
  50.         n++;
  51.     for (; !isPrime( n ); n += 2);
  52.     return n;
  53. }
  54. /*
  55.  * Function To Generate Hash
  56.  */
  57. int HashFunc(int key, int size)
  58. {
  59.     return key % size;
  60. }
  61. /*
  62.  * Function to Initialize Table
  63.  */
  64. HashTable *initializeTable(int size)
  65. {
  66.     HashTable *htable;
  67.     if (size < MIN_TABLE_SIZE)
  68.     {
  69.         cout<<"Table Size Too Small"<<endl;
  70.         return NULL;
  71.     }
  72.     htable = new HashTable;
  73.     if (htable == NULL)
  74.     {
  75.         cout<<"Out of Space"<<endl;
  76.         return NULL;
  77.     }
  78.     htable->size = nextPrime(size);
  79.     htable->table = new HashNode [htable->size];
  80.     if (htable->table == NULL)
  81.     {
  82.         cout<<"Table Size Too Small"<<endl;
  83.         return NULL;
  84.     }
  85.     for (int i = 0; i < htable->size; i++)
  86.     {
  87.         htable->table[i].info = Empty;
  88.         htable->table[i].element = NULL;
  89.     }
  90.     return htable;
  91. }
  92. /*
  93.  * Function to Find Element at a key
  94.  */
  95. int Find(int key, HashTable *htable)
  96. {
  97.     int pos = HashFunc(key, htable->size);
  98.     int collisions = 0;
  99.     while (htable->table[pos].info != Empty &&
  100.            htable->table[pos].element != key)
  101.     {
  102.         pos = pos + 2 * ++collisions -1;
  103.         if (pos >= htable->size)
  104.             pos = pos - htable->size;
  105.     }
  106.     return pos;
  107. }
  108. /*
  109.  * Function to Insert Element into a key
  110.  */
  111. void Insert(int key, HashTable *htable)
  112. {
  113.     int pos = Find(key, htable);
  114.     if (htable->table[pos].info != Legitimate)
  115.     {
  116.         htable->table[pos].info = Legitimate;
  117.         htable->table[pos].element = key;
  118.     }
  119. }
  120. /*
  121.  * Function to Rehash the Table
  122.  */
  123. HashTable *Rehash(HashTable *htable)
  124. {
  125.     int size = htable->size;
  126.     HashNode *table = htable->table;
  127.     htable = initializeTable(2 * size);
  128.     for (int i = 0; i < size; i++)
  129.     {
  130.         if (table[i].info == Legitimate)
  131.             Insert(table[i].element, htable);
  132.     }
  133.     free(table);
  134.     return htable;
  135. }
  136. /*
  137.  * Function to Retrieve Hash Table
  138.  */
  139. void Retrieve(HashTable *htable)
  140. {
  141.     for (int i = 0; i < htable->size; i++)
  142.     {
  143.         int value = htable->table[i].element;
  144.         if (!value)
  145.             cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
  146.         else
  147.             cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
  148.     }
  149.  
  150. }
  151. /*
  152.  * Main Contains Menu
  153.  */
  154. int main()
  155. {
  156.     int value, size, pos, i = 1;
  157.     int choice;
  158.     HashTable *htable;
  159.     while(1)
  160.     {
  161.         cout<<"\n----------------------"<<endl;
  162.         cout<<"Operations on Quadratic Probing"<<endl;
  163.         cout<<"\n----------------------"<<endl;
  164.         cout<<"1.Initialize size of the table"<<endl;
  165.         cout<<"2.Insert element into the table"<<endl;
  166.         cout<<"3.Display Hash Table"<<endl;
  167.         cout<<"4.Rehash The Table"<<endl;
  168.         cout<<"5.Exit"<<endl;
  169.         cout<<"Enter your choice: ";
  170.         cin>>choice;
  171.         switch(choice)
  172.         {
  173.         case 1:
  174.             cout<<"Enter size of the Hash Table: ";
  175.             cin>>size;
  176.             htable = initializeTable(size);
  177.             cout<<"Size of Hash Table: "<<nextPrime(size);
  178.             break;
  179.         case 2:
  180.             if (i > htable->size)
  181.             {
  182.                 cout<<"Table is Full, Rehash the table"<<endl;
  183.                 continue;
  184.             }
  185.         	cout<<"Enter element to be inserted: ";
  186.         	cin>>value;
  187.             Insert(value, htable);
  188.             i++;
  189.             break;
  190.         case 3:
  191.             Retrieve(htable);
  192.             break;
  193.         case 4:
  194.             htable = Rehash(htable);
  195.             break;
  196.         case 5:
  197.             exit(1);
  198.         default:
  199.            cout<<"\nEnter correct option\n";
  200.        }
  201.     }
  202.     return 0;
  203. }

advertisement
$ g++ Quadratic_Probing.cpp
$ a.out
----------------------
Operations on Quadratic Probing
 
----------------------
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
Size of Hash Table: 5
----------------------
Operations on Quadratic Probing
 
----------------------
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
Size of Hash Table: 11
----------------------
Operations on Quadratic Probing
 
----------------------
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 Quadratic Probing
 
----------------------
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: 200
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 300
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 400
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 500
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 600
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 700
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 800
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 900
 
----------------------
Operations on Quadratic Probing
 
----------------------
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 Quadratic Probing
 
----------------------
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: 1100
 
----------------------
Operations on Quadratic Probing
 
----------------------
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 Quadratic Probing
 
----------------------
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: 1100
Position: 2 Element: 100
Position: 3 Element: 200
Position: 4 Element: 300
Position: 5 Element: 400
Position: 6 Element: 500
Position: 7 Element: 600
Position: 8 Element: 700
Position: 9 Element: 800
Position: 10 Element: 900
Position: 11 Element: 1000
 
----------------------
Operations on Quadratic Probing
 
----------------------
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 Quadratic Probing
 
----------------------
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: 300
Position: 3 Element: 600
Position: 4 Element: 900
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: Null
Position: 9 Element: 100
Position: 10 Element: 400
Position: 11 Element: 700
Position: 12 Element: 1000
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: 200
Position: 18 Element: 500
Position: 19 Element: 800
Position: 20 Element: 1100
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: Null
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 2200
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 3300
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 4400
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 5500
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 6600
 
----------------------
Operations on Quadratic Probing
 
----------------------
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: 300
Position: 3 Element: 600
Position: 4 Element: 900
Position: 5 Element: 5500
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: 4400
Position: 9 Element: 100
Position: 10 Element: 400
Position: 11 Element: 700
Position: 12 Element: 1000
Position: 13 Element: 3300
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: 2200
Position: 17 Element: 200
Position: 18 Element: 500
Position: 19 Element: 800
Position: 20 Element: 1100
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: 6600
 
----------------------
Operations on Quadratic Probing
 
----------------------
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