How to implement a hash table in C++

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.

Implementation

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

Copyright ©2024 Educative, Inc. All rights reserved