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.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.