Hash Table Implementation in CPP

1. Introduction

A Hash Table is a data structure that offers fast insertion, deletion, and search operations. It uses an array-based storage mechanism and a hash function to map keys to specific indices in the array. Collision resolution is essential in hash tables, and one common method is chaining, where each index in the hash table array points to a linked list of entries that hash to the same index.

2. Implementation Steps

1. Define a Node class to represent each individual entry (key-value pair) in the hash table.

2. Create a HashTable class that will manage the operations on the hash table.

3. Implement methods to insert (insert), delete (deleteKey), and retrieve (get) key-value pairs.

4. Implement a hashing function (hashFunction) to distribute the keys across the array.

5. Handle collisions using chaining by having each index of the array point to a linked list.

3. Implementation in C++ Programming

#include<iostream>
#include<list>
template<typename K, typename V>
class Node {
public:
    K key;
    V value;
    Node(K key, V value) : key(key), value(value) {}
};
template<typename K, typename V>
class HashTable {
private:
    std::list<Node<K, V>>* table;
    int capacity;
    int size;
    int hashFunction(K key) {
        return key % capacity;
    }
public:
    HashTable(int capacity) : capacity(capacity), size(0) {
        table = new std::list<Node<K, V>>[capacity];
    }
    void insert(K key, V value) {
        int index = hashFunction(key);
        Node<K, V> newNode(key, value);
        table[index].push_back(newNode);
        size++;
    }
    V get(K key) {
        int index = hashFunction(key);
        for (auto& it : table[index]) {
            if (it.key == key) {
                return it.value;
            }
        }
        return V();  // Returns default value if key not found
    }
    void deleteKey(K key) {
        int index = hashFunction(key);
        table[index].remove_if([&](Node<K, V>& x) { return x.key == key; });
        size--;
    }
    ~HashTable() {
        delete[] table;
    }
};
int main() {
    HashTable<int, std::string> hashTable(10);
    hashTable.insert(1, "One");
    hashTable.insert(2, "Two");
    hashTable.insert(3, "Three");
    std::cout << "Value at key 2: " << hashTable.get(2) << std::endl;
    hashTable.deleteKey(2);
    std::cout << "Value at key 2 after deletion: " << hashTable.get(2) << std::endl;
    return 0;
}

Output:

Value at key 2: Two
Value at key 2 after deletion:

Explanation:

1. The Node class represents individual key-value pairs in the hash table.

2. The HashTable class encapsulates the operations of the hash table.

3. hashFunction: This function takes a key and returns an index in the array. The simple modulus operation is used here, but more complex functions can be implemented based on requirements.

4. insert: This function computes the hash of the key and places the key-value pair in the appropriate linked list.

5. get: Finds the value for a given key by computing its hash, accessing the linked list at the given index, and searching the list.

6. deleteKey: Removes a key-value pair from the table.

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