Идеальное ХешированиеPerfect Hashing

Идея строится на простом наблюдении: если у нас есть семейство хеш-функций (например, h(k) = (a·k + b) mod p mod m для случайных a, b — "универсальное семейство хеширования") и мы случайно выбираем функцию из этого семейства, то для фиксированного набора из n ключей и таблицы размера m ≥ n² ожидаемое число коллизий меньше 1 — значит, с достаточной вероятностью случайно выбранная функция вообще не даст коллизий, и её можно найти простым перебором ("пробовать, пока не повезёт"). Для таблицы размера ровно n (без квадратичного разрастания) применяется двухуровневая схема Фредмана-Комлоша-Семереди (FKS, 1984): внешняя хеш-функция распределяет n ключей по n "внешним корзинам" (с коллизиями — это нормально), а для каждой корзины с m_i ключами строится своя внутренняя идеальная хеш-таблица размера m_i² — по той же лотерейной логике, но теперь для гарантированно бесколлизионного случая. Суммарная память остаётся O(n) благодаря лемме о том, что сумма m_i² по всем корзинам ожидаемо O(n) при случайном распределении.The idea rests on a simple observation: if there's a family of hash functions (e.g. h(k) = (a·k + b) mod p mod m for random a, b — a "universal hash family") and one is picked at random from this family, then for a fixed set of n keys and a table of size m ≥ n², the expected number of collisions is less than 1 — meaning a randomly chosen function has a good enough chance of producing zero collisions at all, and it can be found by simple trial-and-error ("try until lucky"). For a table of exactly size n (without quadratic blowup), the two-level Fredman-Komlós-Szemerédi scheme (FKS, 1984) is used: an outer hash function spreads n keys across n "outer buckets" (with collisions — that's fine there), and for each bucket with m_i keys, its own inner perfect hash table of size m_i² is built — using the same lottery logic, but now for a guaranteed collision-free case. Total memory stays O(n) thanks to a lemma showing the sum of m_i² across all buckets is expected O(n) under random distribution.

// упрощённая одноуровневая схема: подбор (a, b) для таблицы размера n² без коллизий// simplified single-level scheme: finding (a, b) for a size-n² table with no collisions
struct PerfectHash {
    long long a, b, p;
    size_t table_size;

    static PerfectHash build(const std::vector<int>& keys) {
        size_t n = keys.size();
        size_t m = n * n;                     // квадратичный размер — гарантия успеха с высокой вероятностью// quadratic size — a high-probability success guarantee
        while (true) {
            long long a = random_nonzero(), b = random();
            std::vector<bool> used(m, false);
            bool collision = false;
            for (int k : keys) {
                size_t idx = ((a * k + b) % PRIME) % m;
                if (used[idx]) { collision = true; break; }
                used[idx] = true;
            }
            if (!collision) return {a, b, PRIME, m};  // нашли — эта функция навсегда идеальна для этого набора// found it — this function is perfect for this set forever
        }
    }

    size_t hash(int key) const { return ((a * key + b) % p) % table_size; }
};

Для фиксированного набора ключей демо перебирает случайные (a, b), проверяя каждую попытку на коллизии. Красный слот — коллизия (попытка отклонена), зелёные — успешное безколлизионное распределение.For a fixed key set, the demo tries random (a, b) pairs, checking each attempt for collisions. A red slot marks a collision (the attempt rejected), green marks a successful collision-free distribution.

Ключевая лемма (следствие неравенства Маркова, применённого к ожидаемому числу пар ключей с одинаковым хешем): для случайной функции из универсального семейства и таблицы размера m ≥ n², вероятность хотя бы одной коллизии среди n ключей меньше 1/2. Значит, вероятность успеха на любой отдельной попытке ≥ 1/2 — ожидаемое число попыток до первого успеха не превышает 2 (геометрическое распределение), что даёт O(n) ожидаемое время построения (n попыток вставки на одну попытку функции, O(1) попыток функций в среднем). Это не эвристика "обычно работает" — это доказанная граница, того же типа рассуждения, что используется при анализе рандомизированных алгоритмов вроде quickselect (2.2.4.1).The key lemma (a consequence of Markov's inequality applied to the expected number of key pairs sharing a hash): for a random function from a universal family and a table of size m ≥ n², the probability of at least one collision among n keys is less than 1/2. So the success probability on any single attempt is ≥ 1/2 — the expected number of attempts before the first success doesn't exceed 2 (a geometric distribution), giving O(n) expected build time (n insertion attempts per function try, O(1) function tries on average). This isn't a "usually works" heuristic — it's a proven bound, the same kind of reasoning used when analyzing randomized algorithms like quickselect (2.2.4.1).