This document provides a basic implementation of a hash table in C++. A hash table is a data structure that maps keys to values for highly efficient lookup. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Program Structure

The hash table implementation consists of the following components:

• HashNode: A structure representing a key-value pair in the hash table.
• HashTable: A class that manages the array of buckets, handles insertion, deletion, and lookup operations.
• Hash Function: A function that generates an index based on the key.

Code Implementation

#include <iostream>
#include <list>
#include <utility> // for std::pair
#include <string>

using namespace std;

// Node structure for storing key-value pairs
struct HashNode {
    string key;
    int value;

    HashNode(string k, int v) : key(k), value(v) {}
};

// Hash Table class
class HashTable {
private:
    // Array of lists to store hash nodes
    list* table;
    int capacity; // Number of buckets

    // Hash function to compute index for a key
    int hash(string key) {
        int hashValue = 0;
        for (char ch : key) {
            hashValue += ch;
        }
        return hashValue % capacity;
    }

public:
    // Constructor to initialize the hash table
    HashTable(int size) {
        capacity = size;
        table = new list[capacity];
    }

    // Destructor to free allocated memory
    ~HashTable() {
        delete[] table;
    }

    // Function to insert key-value pair
    void insert(string key, int value) {
        int index = hash(key);
        table[index].emplace_back(key, value);
    }

    // Function to get value by key
    int get(string key) {
        int index = hash(key);
        for (const HashNode& node : table[index]) {
            if (node.key == key) {
                return node.value;
            }
        }
        throw invalid_argument("Key not found");
    }

    // Function to remove key-value pair
    void remove(string key) {
        int index = hash(key);
        table[index].remove_if([&](const HashNode& node) { return node.key == key; });
    }
};

// Example usage
int main() {
    HashTable hashTable(10);

    hashTable.insert("apple", 1);
    hashTable.insert("banana", 2);
    hashTable.insert("orange", 3);

    try {
        cout << "Value for 'banana': " << hashTable.get("banana") << endl;
        hashTable.remove("banana");
        cout << "Value for 'banana' after removal: " << hashTable.get("banana") << endl;
    } catch (const exception& e) {
        cout << e.what() << endl;
    }

    return 0;
}

Explanation of the Code

1. Header Files:
   • The program includes necessary header files like <iostream>, <list>, <utility>, and <string> for basic input/output operations and data structures.
2. HashNode Structure:
   • This structure holds the key and value pair.
3. HashTable Class:
   • Contains a dynamic array of lists to manage collisions using separate chaining.
   • A private method hash computes the index based on the key.
   • Public methods include:
     • insert: To add key-value pairs.
     • get: To retrieve values by key.
     • remove: To delete key-value pairs.
4. Main Function:
   • Demonstrates how to create a hash table, insert values, retrieve a value, and remove a key.

Documentation

• HashNode: Represents a node in the hash table containing a key and a corresponding value.
• HashTable(int size): Constructor to initialize the hash table with a specified number of buckets.
• ~HashTable(): Destructor to clean up memory allocated for the table.
• void insert(string key, int value): Inserts a key-value pair into the hash table.
• int get(string key): Retrieves the value associated with the given key. Throws an exception if the key is not found.
• void remove(string key): Removes the key-value pair from the hash table based on the key.

Conclusion

This basic hash table implementation demonstrates the fundamental operations of insertion, retrieval, and deletion. It utilizes separate chaining to handle collisions, ensuring efficient storage and access. This structure can be further enhanced with features like dynamic resizing, improved hash functions, and more sophisticated collision resolution techniques.