RELATED TAGS

data structures
chaining
hashing
list

# How to implement a hash table in C++ Educative Answers Team

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;
}

RELATED TAGS

data structures
chaining
hashing
list 