C++ Program to Implement Hash Tables chaining with Singly Linked Lists

«
»
This C++ Program demonstrates operations on Hash Tables chaining with Singly Linked Lists.

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

advertisement
$ g++ hash_singly.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: 12
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: 24
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: 36
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: 48
Enter key at which element to be inserted: 2
 
----------------------
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: 60
Enter key at which element to be inserted: 2
 
----------------------
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: 1
Element at key 1 : 12 24 36 
----------------------
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: 2
Element at key 2 : 48 60 
----------------------
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: 4
No Element found at key 4
 
----------------------
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: 1
Element at key 1 : 12 24 36 
----------------------
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: 1
Element Deleted
 
----------------------
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
Element at key 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: 2
Enter key of the element to be searched: 1
Element at key 1 : 12 24 
----------------------
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: 36
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: 2
Enter key of the element to be searched: 1
Element at key 1 : 12 24 36 
----------------------
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: 2
Element at key 2 : 48 60 
----------------------
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
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