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.

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

advertisement
advertisement
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