Хеш-Таблица с ЦепочкамиHash Table with Chaining

Таблица — это массив из cap "корзин", каждая изначально пустой список. Чтобы вставить пару (key, value), вычисляется idx = hash(key) % cap, и пара добавляется в список buckets[idx] (если ключ там уже есть — значение обновляется, а не дублируется). Чтобы найти значение по ключу, вычисляется тот же idx, и внутри buckets[idx] выполняется линейный поиск нужного ключа — короткий, пока корзина не переполнена. Удаление работает так же: вычислить idx, найти ключ в списке корзины, удалить узел — та же операция O(1) из 2.3.1.1, если ключ уже найден.The table is an array of cap "buckets," each initially an empty list. To insert a (key, value) pair, idx = hash(key) % cap is computed, and the pair is added to the list buckets[idx] (if the key is already there, the value is updated, not duplicated). To find a value by key, the same idx is computed, and a linear search for the key runs inside buckets[idx] — short, as long as the bucket isn't overloaded. Deletion works the same way: compute idx, find the key in the bucket's list, remove the node — the same O(1) operation from 2.3.1.1, once the key is located.

Инвариант, который держит эту схему быстрой: средняя длина цепочки в одной корзине равна load factor = n / cap (n элементов, cap корзин). Пока load factor остаётся константой (обычно ≤ 0.75, для чего таблица периодически увеличивается — rehashing), средняя длина цепочки — тоже константа, и поиск/вставка/удаление остаются O(1) в среднем, несмотря на то что внутри каждой корзины поиск линеен.The invariant keeping this scheme fast: the average chain length in one bucket equals the load factor = n / cap (n elements, cap buckets). As long as the load factor stays a constant (usually ≤ 0.75, which is why the table periodically grows via rehashing), the average chain length is also constant, and lookup/insert/delete stay O(1) on average, even though the search inside each bucket is linear.

template<typename K, typename V>
class HashTable {
    std::vector<std::list<std::pair<K, V>>> buckets;
public:
    explicit HashTable(size_t cap) : buckets(cap) {}

    void put(const K& key, const V& val) {
        auto& bucket = buckets[std::hash<K>{}(key) % buckets.size()];
        for (auto& [k, v] : bucket)
            if (k == key) { v = val; return; }  // обновить, не дублировать// update, don't duplicate
        bucket.emplace_back(key, val);
    }

    std::optional<V> get(const K& key) const {
        const auto& bucket = buckets[std::hash<K>{}(key) % buckets.size()];
        for (const auto& [k, v] : bucket)
            if (k == key) return v;
        return std::nullopt;
    }
};

Ключи — целые числа, хеш-функция — просто key % cap, специально выбрана маленькая, чтобы коллизии возникали часто и были наглядны. Каждая корзина — цепочка узлов, растущая вправо. Кнопки put/get/delete выполняют операцию сразу.Keys are integers, the hash function is simply key % cap, deliberately kept small so collisions happen often and are easy to see. Each bucket is a chain of nodes growing to the right. The put/get/delete buttons execute immediately.

Если хеш-функция плохая (или злоумышленник целенаправленно подбирает ключи, дающие одинаковый хеш — атака на хеш-таблицу через coordinated collision), все n элементов могут оказаться в одной корзине, и поиск в ней деградирует до O(n) — таблица превращается в связный список с лишним слоем косвенности. Это не гипотетический риск: несколько веб-фреймворков в 2011-2012 годах пострадали от практических DoS-атак именно через предсказуемые хеш-функции для параметров форм. Защита — использовать криптографически устойчивые к предсказанию хеш-функции с случайным seed (SipHash и подобные), делающие целенаправленный подбор коллизий вычислительно неосуществимым.If the hash function is poor (or an attacker deliberately picks keys yielding the same hash — a hash-table collision attack), all n elements can land in one bucket, and lookup there degrades to O(n) — the table becomes a linked list with an extra layer of indirection. This isn't a hypothetical risk: several web frameworks suffered practical DoS attacks in 2011-2012 through exactly this — predictable hash functions for form parameters. The defense is using hash functions resistant to prediction, with a random seed (SipHash and similar), making deliberate collision crafting computationally infeasible.