Can you explain how the data structure of a hash table is implemented?

A hash table is a data structure that allows efficient storage of key-value pairs and quick operations for search, insertion, and deletion. The main idea is to use a hash function that transforms the key into an array index (bucket).

When inserting an element, the key is processed through the hash function, which returns an index where the value is placed. If there is already an element in this bucket (collision), collision resolution methods are usually applied:

• Chaining: each bucket stores a linked list of elements with the same index.
• Open addressing: in case of collision, the next free bucket is searched according to a certain sequence (linear probing, quadratic, etc.).

Example in C++ using chaining:

#include <iostream>
#include <list>
#include <vector>
#include <string>

class HashTable {
    static const int bucket_count = 10;
    std::vector<std::list<std::pair<std::string, int>>> table;

    int hash(const std::string& key) {
        int hash_val = 0;
        for (char c : key) {
            hash_val = (hash_val * 31 + c) % bucket_count;
        }
        return hash_val;
    }

public:
    HashTable() : table(bucket_count) {}

    void insert(const std::string& key, int value) {
        int idx = hash(key);
        for (auto& kv : table[idx]) {
            if (kv.first == key) {
                kv.second = value; // update
                return;
            }
        }
        table[idx].emplace_back(key, value);
    }

    bool find(const std::string& key, int& value) {
        int idx = hash(key);
        for (auto& kv : table[idx]) {
            if (kv.first == key) {
                value = kv.second;
                return true;
            }
        }
        return false;
    }
};

int main() {
    HashTable ht;
    ht.insert("apple", 5);
    int val;
    if (ht.find("apple", val)) {
        std::cout << "Value: " << val << std::endl;
    }
}

Thus, a hash table provides an average access time of O(1), but in the worst case (many collisions), it can degrade to O(n).