Hash Table Example

A hash table is a data structure that provides constant-time average-case access to elements based on their key. A hash table uses a hash function to map the key of each element to an index in an array. Here is an example implementation of a hash table using separate chaining in C++:

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

// Class to represent a node in the hash table
template <typename K, typename V>
class HashNode {
public:
    K key;         // Key of the hash node
    V value;       // Value of the hash node
    HashNode* next; // Pointer to the next node in the same bucket

    // Constructor to initialize the key, value, and next pointer
    HashNode(K key, V value) {
        this->key = key;
        this->value = value;
        this->next = nullptr;
    }
};

// Class to represent the hash table
template <typename K, typename V>
class HashTable {
public:
    static const int TABLE_SIZE = 13; // Size of the table
    vector<HashNode<K, V>*> table;     // Vector to store pointers to hash nodes

    // Constructor to initialize the table with nullptr
    HashTable() {
        table = vector<HashNode<K, V>*>(TABLE_SIZE, nullptr);
    }

    // Destructor to deallocate dynamically allocated memory
    ~HashTable() {
        for (int i = 0; i < TABLE_SIZE; i++) {
            HashNode<K, V>* node = table[i];
            while (node) {
                HashNode<K, V>* nextNode = node->next;
                delete node;
                node = nextNode;
            }
            table[i] = nullptr;
        }
    }

    // Function to compute the hash index for a given key
    int hashFunction(K key) {
        hash<K> hashFunction;
        int index = hashFunction(key) % TABLE_SIZE;
        return index;
    }

    // Function to insert a key-value pair into the hash table
    void put(K key, V value) {
        int index = hashFunction(key);
        HashNode<K, V>* node = table[index];
        while (node) {
            if (node->key == key) {
                node->value = value; // Update value if key already exists
                return;
            }
            node = node->next;
        }
        // Create a new node and insert at the beginning of the bucket
        HashNode<K, V>* newNode = new HashNode<K, V>(key, value);
        newNode->next = table[index];
        table[index] = newNode;
    }

    // Function to retrieve the value associated with a given key
    V get(K key) {
        int index = hashFunction(key);
        HashNode<K, V>* node = table[index];
        while (node) {
            if (node->key == key) {
                return node->value;
            }
            node = node->next;
        }
        throw out_of_range("Key not found");
    }

    // Function to check if a key exists in the hash table
    bool containsKey(K key) {
        int index = hashFunction(key);
        HashNode<K, V>* node = table[index];
        while (node) {
            if (node->key == key) {
                return true;
            }
            node = node->next;
        }
        return false;
    }

    // Function to remove a key-value pair from the hash table
    void remove(K key) {
        int index = hashFunction(key);
        HashNode<K, V>* node = table[index];
        HashNode<K, V>* prevNode = nullptr;
        while (node) {
            if (node->key == key) {
                if (prevNode) {
                    prevNode->next = node->next;
                } else {
                    table[index] = node->next;
                }
                delete node;
                return;
            }
            prevNode = node;
            node = node->next;
        }
        throw out_of_range("Key not found");
    }
};

int main() {
    HashTable<string, int> myHashTable; // Create a hash table
    myHashTable.put("one", 1);          // Insert key-value pairs
    myHashTable.put("two", 2);
    myHashTable.put("three", 3);
    cout << myHashTable.get("two") << endl; // Retrieve and print value for key "two"
    myHashTable.remove("one");              // Remove key-value pair with key "one"
    cout << myHashTable.containsKey("one") << endl; // Check if key "one" exists and print the result
    return 0;
}

Here's an explanation of each part:

HashNode Class:
- HashNode class is defined to represent individual elements within the hash table. Each HashNode object contains a key, a value, and a pointer to the next HashNode in the same bucket (for handling collisions).
HashTable Class:
- TABLE_SIZE: A constant that sets the size of the hash table. It's set to 13 in this code.
- table: A vector of pointers to HashNode objects. Each element of this vector represents a "bucket" in the hash table.
- Constructor: Initializes the table vector with nullptr for all TABLE_SIZE buckets.
- Destructor: Deallocates the memory for each HashNode object in the table.
- hashFunction: A method that takes a key and returns an index into the table vector using the C++ Standard Library's hash function.
- put: Inserts a key-value pair into the table. If the key already exists in the table, it updates the value. Otherwise, it inserts a new HashNode into the corresponding bucket.
- get: Retrieves the value associated with a given key. If the key doesn't exist in the table, it throws an out_of_range exception.
- containsKey: Checks whether a given key exists in the table.
- remove: Removes the key-value pair associated with a given key from the table. If the key doesn't exist, it throws an out_of_range exception.
main Function:
- A HashTable object is created with string keys and integer values.
- The put method is called to insert three key-value pairs into the hash table.
- The get method is called to retrieve the value associated with the key "two", and the result is printed.
- The remove method is called to remove the key-value pair with the key "one".
- The containsKey method is called to check whether the key "one" exists in the table after removal, and the result is printed.

The overall code is a basic implementation of a hash table with separate chaining. It provides a demonstration of how to insert, retrieve, check existence, and remove key-value pairs from the hash table. It also includes proper memory management by deallocating nodes in the destructor.