Cuckoo Hashing

Используются две таблицы (или одна таблица с двумя хеш-функциями) — T1 и T2, с хеш-функциями h1 и h2. Каждый ключ k может находиться либо в T1[h1(k)], либо в T2[h2(k)] — никогда больше нигде. Это и есть инвариант, который делает поиск гарантированно O(1) в худшем случае: проверить нужно ровно два места, не последовательность произвольной длины, как в открытой адресации.Two tables are used (or one table with two hash functions) — T1 and T2, with hash functions h1 and h2. Every key k can live either in T1[h1(k)] or T2[h2(k)] — never anywhere else. This is precisely the invariant that makes lookup guaranteed O(1) worst case: exactly two places need checking, not a sequence of arbitrary length as in open addressing.

Вставка ключа k: если T1[h1(k)] свободен — готово. Если занят другим ключом k' — k занимает эту позицию, а k' вытесняется и пытается занять T2[h2(k')]; если и там занято другим ключом k'' — тот вытесняется в T1[h1(k'')], и так далее. Если цепочка вытеснений превышает разумный лимит (обычно O(log n)), это означает, что текущий набор хеш-функций создал цикл — таблица целиком перехешируется с новыми хеш-функциями (полный rehash, амортизированно редкий при достаточном запасе по load factor).Inserting key k: if T1[h1(k)] is free, done. If occupied by another key k', k takes the spot, and k' is evicted and tries to occupy T2[h2(k')]; if that's also occupied by k'', it's evicted to T1[h1(k'')], and so on. If the eviction chain exceeds a reasonable limit (usually O(log n)), it means the current hash functions created a cycle — the whole table is rehashed with new hash functions (a full rehash, amortized rare given enough load-factor headroom).

bool put(int key, int val) {
    for (int kicks = 0; kicks < MAX_KICKS; ++kicks) {
        size_t i1 = h1(key) % cap;
        if (!t1[i1].occupied) { t1[i1] = {key, val, true}; return true; }
        std::swap(key, t1[i1].key); std::swap(val, t1[i1].val);  // выселить в T1// evict into T1

        size_t i2 = h2(key) % cap;
        if (!t2[i2].occupied) { t2[i2] = {key, val, true}; return true; }
        std::swap(key, t2[i2].key); std::swap(val, t2[i2].val);  // выселить в T2// evict into T2
    }
    rehash_with_new_hash_functions();  // обнаружен цикл — перехешировать всё// cycle detected — rehash everything
    return put(key, val);
}

Две таблицы показаны рядом. Красная вспышка — момент вытеснения. Наблюдайте, как одна вставка может запустить целую цепочку перемещений между таблицами.The two tables are shown side by side. A red flash marks an eviction moment. Watch how a single insertion can trigger a whole chain of moves between the tables.

Поиск асимметричен по отношению к вставке: инвариант "ключ находится в одной из ровно двух позиций" держится всегда, независимо от истории вставок — поэтому поиск всегда проверяет ровно 2 места, O(1) без всяких "в среднем" или "с высокой вероятностью". Вставка же может потребовать сколь угодно длинной цепочки вытеснений — в редких случаях (обычно при load factor, близком к пределу для двух хеш-функций, теоретически ~50%) цепочка может зациклиться, требуя полного rehash со свежими хеш-функциями. Амортизированная стоимость вставки остаётся O(1), потому что rehash случается редко (экспоненциально редко при растущем n относительно порога), но конкретная отдельная вставка иногда может быть дорогой — тот же тип компромисса, что у амортизированного анализа расширения массива (2.1.1).Lookup is asymmetric relative to insertion: the invariant "the key sits in one of exactly two positions" always holds, regardless of insertion history — so lookup always checks exactly 2 spots, O(1) with no "on average" or "with high probability" caveats. Insertion, though, can require an arbitrarily long eviction chain — in rare cases (usually at a load factor close to the limit for two hash functions, theoretically ~50%) the chain can cycle, requiring a full rehash with fresh hash functions. Insertion's amortized cost stays O(1), because a rehash is rare (exponentially rare as n grows relative to the threshold), but any single specific insertion can occasionally be expensive — the same kind of trade-off as the amortized analysis of array growth (2.1.1).