C++ Program to Implement a Hash Table

1. Introduction

Hash tables are a type of data structure that offers fast insertion, deletion, and search operations. Underlying a hash table is an array combined with a hashing function. This function maps keys to indices in the array, ensuring a quick retrieval of the value associated with a given key. 

In this post, we'll walk you through a basic implementation of a hash table in C++.

2. Program Overview

Our program will:

1. Define a HashTable class that uses open addressing (linear probing) to handle collisions.

2. The HashTable class will have functions to:

- Insert a key-value pair.

- Search for a key and retrieve its associated value.

- Delete a key-value pair.

3. Demonstrate these functions in the main program.

3. Code Program

#include<iostream>
#include<vector>
using namespace std;

// Size for the hash table
const int TABLE_SIZE = 13;

// Entry for the hash table
class Entry {
public:
    int key;
    int value;
    Entry(int key, int value) {
        this->key = key;
        this->value = value;
    }
};

class HashTable {
private:
    vector<Entry*> table;

    // Hash function to compute index
    int hash(int key) {
        return key % TABLE_SIZE;
    }

public:
    // Constructor to initialize table
    HashTable() {
        table.assign(TABLE_SIZE, nullptr);
    }

    // Insert key-value into the hash table
    void insert(int key, int value) {
        int index = hash(key);
        while(table[index] != nullptr && table[index]->key != key) {
            index = (index + 1) % TABLE_SIZE;  // Linear probing
        }
        if(table[index] != nullptr) {
            delete table[index];
        }
        table[index] = new Entry(key, value);
    }

    // Search for a key and return its value
    int get(int key) {
        int index = hash(key);
        while(table[index] != nullptr && table[index]->key != key) {
            index = (index + 1) % TABLE_SIZE;
        }
        if(table[index] == nullptr) {
            return -1; // Not found
        }
        return table[index]->value;
    }

    // Delete a key from the hash table
    void remove(int key) {
        int index = hash(key);
        while(table[index] != nullptr) {
            if(table[index]->key == key) {
                delete table[index];
                table[index] = nullptr;
                return;
            }
            index = (index + 1) % TABLE_SIZE;
        }
    }
};

int main() {
    HashTable ht;
    ht.insert(1, 10);
    ht.insert(2, 20);
    ht.insert(3, 30);
    cout << "Value for key 2: " << ht.get(2) << endl;
    ht.remove(2);
    cout << "Value for key 2 after removal: " << ht.get(2) << endl;
    return 0;
}

Output:

Value for key 2: 20
Value for key 2 after removal: -1

4. Step By Step Explanation

1. The Entry class represents each key-value pair in the hash table.

2. Our HashTable class uses an array (implemented using a vector) to store these entries.

3. The hash function computes the index in the array for a given key by taking its modulo with the table size.

4. The insert method adds a key-value pair, using linear probing to find an open slot if the initial index is taken.

5. The get method retrieves the value associated with a given key, again using linear probing to handle collisions.

6. The remove method deletes a key-value pair from the hash table.

7. In the main function, we demonstrate inserting key-value pairs, retrieving a value, and deleting a key from the hash table.

Continue Learning with Java Guides

Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.

Explore My Udemy Courses View Developer Roadmaps

By Ramesh Fadatare - Udemy Instructor Partner