Хеш-таблица — это структура данных, которая позволяет эффективно хранить пары ключ-значение и быстро выполнять операции поиска, вставки и удаления. Основная идея — использовать хеш-функцию, которая преобразует ключ в индекс массива (бакета).

При вставке элемента ключ пропускается через хеш-функцию, которая возвращает индекс, куда помещается значение. Если в этом бакете уже есть элемент (коллизия), обычно применяют методы разрешения коллизий:

Цепочки (chaining): в каждом бакете хранится связанный список элементов с одинаковым индексом.
Открытая адресация: при коллизии ищется следующий свободный бакет по определённой последовательности (линейное пробирование, квадратичное и т.д.).

Пример на C++ с использованием цепочек:

#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; // обновление
                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;
    }
}

Таким образом, хеш-таблица обеспечивает среднее время доступа O(1), но в худшем случае (много коллизий) может деградировать до O(n).

Можете объяснить, каким образом реализована структура данных хеш-таблица?