Hash Table Implementation in C++ With Example

Introduction

Hash tables, also known as hash maps, are fundamental data structures in computer science that provide efficient key-value pair storage and retrieval. They are widely used to build data storage and indexing systems, databases, and various algorithms and applications that require quick data access. In this article, we will delve into the implementation of a hash table in C++.

What is a Hash Table in C++?

A hash table is a data structure that stores key-value pairs. It uses a hash function to map each key to an index in an array. This index is used to store and retrieve the corresponding value. 

The key idea behind hash tables is to achieve constant-time O(1) average complexity for insertion, deletion, and retrieval operations.

Working of Hash Tables.

To understand the inner workings of a Hash Table, you need to understand the three important terms explained below:

Hash Function: When a key is provided, a hash function converts the key into an integer called a hash code. This hash code is used to determine the index in the hash table where the value associated with the key will be stored.

Index Mapping: The hash code is mapped to an index in the hash table's underlying array. This process ensures that different keys are distributed uniformly across the array.

Collision Handling: Since hash functions can produce the same hash code for different keys (known as collisions), hash tables need collision resolution strategies. There are various methods to handle collisions, such as chaining or open addressing. 

You can read our detailed article on "How To Resolve Collision in Hash Table?" to get a better understanding.

Chaining Method: This strategy involves storing multiple values at the same index using a data structure like a linked list. (alert-passed)

Open Addressing Method: In this approach, when a collision occurs, the algorithm searches for the next available slot (based on a predefined sequence) and places the data there. (alert-passed)

So these are the steps and working of a hash table that we use for solving many complex coding problems.

Implementation of Hash Table in C++.

Implementing a hash table from scratch involves designing the data structure, defining hash functions, handling collisions, and providing methods for insertion, retrieval, and deletion. 

Below we have implemented a simple Hash Table in C++ using Array and Linked List for collision resolution. 

C++ Example Code: 

// C++ code for the implementation of Hash Table
#include <iostream>
#include <list>
using namespace std;

// HashTable class
class HashTable {
private: 
    // Size of the hash table
    static const int tableSize = 10;
    // Array of linked lists
    list<pair<int, int>> table[tableSize];
    
    // Hash function to map key to an index
    int hashFunction(int key) {
        return key % tableSize;
    }

public:
    // Insert a key-value pair into the hash table
    void insert(int key, int value) {
        int index = hashFunction(key);
        table[index].emplace_back(key, value);
    }
    
    // Get the value associated with a key
    int search(int key) {
        int index = hashFunction(key);
        for (const auto& pair : table[index]) {
            if (pair.first == key) {
                return pair.second;
            }
        }
        return -1; // Key not found
    }
    
    // Remove a key-value pair from the hash table
    void remove(int key) {
        int index = hashFunction(key);
        table[index].remove_if([&key](const std::pair<int, int>& pair) {
            return pair.first == key;
        });
    }
};

int main() {
    HashTable ht;

    ht.insert(101, 10);
    ht.insert(201, 20);
    ht.insert(302, 30);

    cout << "Value at key 201: " << ht.search(201) << endl;

    ht.remove(201);
    cout << "Value at key 201 after removal: " << ht.search(201) << endl;

    return 0;
}

Value at key 201: 20
Value at key 201 after removal: -1

Explanation:

// C++ code for working of unordered_map and unordered_list
#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;

int main() {
    unordered_map<string, int> scores;
    scores["Alice"] = 95;
    scores["Bob"] = 85;

    cout << "Alice's score: " << scores["Alice"] << endl;

    unordered_set<int> uniqueNumbers;
    uniqueNumbers.insert(5);
    uniqueNumbers.insert(10);

    if (uniqueNumbers.find(5) != uniqueNumbers.end()) {
        cout << "Number 5 found!" << endl;
    }

    return 0;
}

Alice's score: 95
Number 5 found!