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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
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.