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.