C++ Program to Implement Hash Tables with Linear Probing

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

Here is source code of the C++ Program to demonstrate Hash Tables with Linear 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 Linear Probing
  3.  */
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. using namespace std;
  8. const int TABLE_SIZE = 5;
  9.  
  10. /*
  11.  * HashNode Class Declaration
  12.  */
  13. class HashNode
  14. {
  15.     public:
  16.         int key;
  17.         int value;
  18.         HashNode(int key, int value)
  19.         {
  20.             this->key = key;
  21.             this->value = value;
  22.         }
  23. };
  24.  
  25. /*
  26.  * DeletedNode Class Declaration
  27.  */
  28. class DeletedNode:public HashNode
  29. {
  30.     private:
  31.         static DeletedNode *entry;
  32.         DeletedNode():HashNode(-1, -1)
  33.         {}
  34.     public:
  35.         static DeletedNode *getNode()
  36.         {
  37.             if (entry == NULL)
  38.                 entry = new DeletedNode();
  39.             return entry;
  40.         }
  41. };
  42. DeletedNode *DeletedNode::entry = NULL;
  43. /*
  44.  * HashMap Class Declaration
  45.  */
  46. class HashMap
  47. {
  48.     private:
  49.         HashNode **htable;
  50.     public:
  51.         HashMap()
  52.         {
  53.             htable = new HashNode* [TABLE_SIZE];
  54.             for (int i = 0; i < TABLE_SIZE; i++)
  55.             {
  56.                 htable[i] = NULL;
  57.             }
  58.         }
  59.  
  60.         ~HashMap()
  61.         {
  62.             for (int i = 0; i < TABLE_SIZE; i++)
  63.             {
  64.                 if (htable[i] != NULL && htable[i] != DeletedNode::getNode())
  65.                     delete htable[i];
  66.             }
  67.             delete[] htable;
  68.         }
  69.         /*
  70.          * Hash Function
  71.          */
  72.         int HashFunc(int key)
  73.         {
  74.             return key % TABLE_SIZE;
  75.         }
  76.         /*
  77.          * Insert Element at a key
  78.          */
  79.         void Insert(int key, int value)
  80.         {
  81.             int hash_val = HashFunc(key);
  82.             int init = -1;
  83.             int deletedindex = -1;
  84.             while (hash_val != init && (htable[hash_val]
  85.                             == DeletedNode::getNode() || htable[hash_val]
  86.                             != NULL && htable[hash_val]->key != key))
  87.             {
  88.                 if (init == -1)
  89.                     init = hash_val;
  90.                 if (htable[hash_val] == DeletedNode::getNode())
  91.                     deletedindex = hash_val;
  92.                 hash_val = HashFunc(hash_val + 1);
  93.             }
  94.             if (htable[hash_val] == NULL || hash_val == init)
  95.             {
  96.                 if(deletedindex != -1)
  97.                     htable[deletedindex] = new HashNode(key, value);
  98.                 else
  99.                     htable[hash_val] = new HashNode(key, value);
  100.             }
  101.             if(init != hash_val)
  102.             {
  103.                 if (htable[hash_val] != DeletedNode::getNode())
  104.                 {
  105.                     if (htable[hash_val] != NULL)
  106.                     {
  107.                         if (htable[hash_val]->key == key)
  108.                             htable[hash_val]->value = value;
  109.                     }
  110.                 }
  111.                 else
  112.                     htable[hash_val] = new HashNode(key, value);
  113.             }
  114.         }
  115.         /*
  116.          * Search Element at a key
  117.          */
  118.         int Search(int key)
  119.         {
  120.             int hash_val = HashFunc(key);
  121.             int init = -1;
  122.             while (hash_val != init && (htable[hash_val]
  123.                             == DeletedNode::getNode() || htable[hash_val]
  124.                             != NULL && htable[hash_val]->key != key))
  125.             {
  126.                 if (init == -1)
  127.                     init = hash_val;
  128.                 hash_val = HashFunc(hash_val + 1);
  129.             }
  130.             if (htable[hash_val] == NULL || hash_val == init)
  131.                 return -1;
  132.             else
  133.                 return htable[hash_val]->value;
  134.         }
  135.         /*
  136.          * Remove Element at a key
  137.          */
  138.         void Remove(int key)
  139.         {
  140.             int hash_val = HashFunc(key);
  141.             int init = -1;
  142.             while (hash_val != init && (htable[hash_val]
  143.                             == DeletedNode::getNode() || htable[hash_val]
  144.                             != NULL && htable[hash_val]->key != key))
  145.             {
  146.                 if (init == -1)
  147.                     init = hash_val;
  148.                 hash_val = HashFunc(hash_val + 1);
  149.             }
  150.             if (hash_val != init && htable[hash_val] != NULL)
  151.             {
  152.                 delete htable[hash_val];
  153.                 htable[hash_val] = DeletedNode::getNode();
  154.             }
  155.         }
  156. };
  157.  
  158. /*
  159.  * Main Contains Menu
  160.  */
  161. int main()
  162. {
  163.     HashMap hash;
  164.     int key, value;
  165.     int choice;
  166.     while(1)
  167.     {
  168.         cout<<"\n----------------------"<<endl;
  169.         cout<<"Operations on Hash Table"<<endl;
  170.         cout<<"\n----------------------"<<endl;
  171.         cout<<"1.Insert element into the table"<<endl;
  172.         cout<<"2.Search element from the key"<<endl;
  173.         cout<<"3.Delete element at a key"<<endl;
  174.         cout<<"4.Exit"<<endl;
  175.         cout<<"Enter your choice: ";
  176.         cin>>choice;
  177.         switch(choice)
  178.         {
  179.         case 1:
  180.             cout<<"Enter element to be inserted: ";
  181.             cin>>value;
  182.             cout<<"Enter key at which element to be inserted: ";
  183.             cin>>key;
  184.             hash.Insert(key, value);
  185.             break;
  186.         case 2:
  187.             cout<<"Enter key of the element to be searched: ";
  188.             cin>>key;
  189.             if(hash.Search(key) == -1)
  190.             {
  191.                 cout<<"No element found at key "<<key<<endl;
  192.                 continue;
  193.             }
  194.             else
  195.             {
  196.                 cout<<"Element at key "<<key<<" : ";
  197.                 cout<<hash.Search(key)<<endl;
  198.             }
  199.             break;
  200.         case 3:
  201.             cout<<"Enter key of the element to be deleted: ";
  202.             cin>>key;
  203.             hash.Remove(key);
  204.             break;
  205.         case 4:
  206.             exit(1);
  207.         default:
  208.            cout<<"\nEnter correct option\n";
  209.        }
  210.     }
  211.     return 0;
  212. }

advertisement
$ g++ Linear_Probing.cpp
$ a.out
 
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 100
Enter key at which element to be inserted: 1
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 300
Enter key at which element to be inserted: 3
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 500
Enter key at which element to be inserted: 5
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 600
Enter key at which element to be inserted: 6
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 800
Enter key at which element to be inserted: 8
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 1000
Enter key at which element to be inserted: 10
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 3
Element at key 3 : 300
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 7
No element found at key 7
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 10
Element at key 10 : 1000
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 5
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 6
Element at key 6 : 600
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 5
No element found at key 5
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 700
Enter key at which element to be inserted: 7
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 7
Element at key 7 : 700
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 4
 
------------------
(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.