A hash table is a data structure that stores information in key-value pairs. The index of each value to be stored is calculated using a hash function; this process is known as hashing.
Different implementations are possible for a hash table depending on the method for dealing with collisions. In the implementation below, collisions are resolved using chaining, which is why every index of the hash table has a linked list associated with it.
The linked list provided in the C++ Standard Template Library (STL) has been used in the code below.
#include <iostream>#include <list>using namespace std;class HashTable{private:list<int> *table;int total_elements;// Hash function to calculate hash for a value:int getHash(int key){return key % total_elements;}public:// Constructor to create a hash table with 'n' indices:HashTable(int n){total_elements = n;table = new list<int>[total_elements];}// Insert data in the hash table:void insertElement(int key){table[getHash(key)].push_back(key);}// Remove data from the hash table:void removeElement(int key){int x = getHash(key);list<int>::iterator i;for (i = table[x].begin(); i != table[x].end(); i++) {// Check if the iterator points to the required item:if (*i == key)break;}// If the item was found in the list, then delete it:if (i != table[x].end())table[x].erase(i);}void printAll(){// Traverse each index:for(int i = 0; i < total_elements; i++){cout << "Index " << i << ": ";// Traverse the list at current index:for(int j : table[i])cout << j << " => ";cout << endl;}}};int main() {// Create a hash table with 3 indices:HashTable ht(3);// Declare the data to be stored in the hash table:int arr[] = {2, 4, 6, 8, 10};// Insert the whole data into the hash table:for(int i = 0; i < 5; i++)ht.insertElement(arr[i]);cout << "..:: Hash Table ::.." << endl;ht.printAll();ht.removeElement(4);cout << endl << "..:: After deleting 4 ::.." << endl;ht.printAll();return 0;}
Free Resources