Robin Hood Hashing

Каждый слот хранит не только ключ и значение, но и probe distance (PSL, probe sequence length) — сколько шагов пробирования потребовалось, чтобы попасть в этот слот от идеальной позиции h(key). При вставке нового ключа, если текущий слот занят другим ключом с меньшим PSL, чем у вставляемого на этом шаге, происходит обмен: новый ключ занимает слот (получая его PSL), а вытесненный ключ продолжает вставку с того же места, как будто он — новый ключ с увеличенным на единицу PSL. Инвариант, поддерживаемый этим правилом: в любой момент максимальная разница PSL между любыми двумя ключами в таблице минимальна — грубо говоря, никто не "застревает" сильно дальше других.Each slot stores not just the key and value but a probe distance (PSL, probe sequence length) — how many probing steps it took to reach this slot from the ideal position h(key). When inserting a new key, if the current slot is occupied by another key with a smaller PSL than the one being inserted at this step, a swap happens: the new key takes the slot (inheriting its PSL), and the displaced key continues insertion from that same spot, as if it were a new key with PSL incremented by one. The invariant this rule maintains: at any moment, the maximum PSL difference between any two keys in the table is minimized — roughly speaking, no one gets stuck much further than anyone else.

Поиск использует этот инвариант для раннего выхода: если во время поиска ключа встречается слот, чей PSL меньше текущего пройденного расстояния поиска, искомого ключа точно нет в таблице (он не мог бы "перепрыгнуть" через элемент с меньшим PSL, не вытеснив его) — поиск может остановиться, не проверяя оставшиеся слоты.Lookup uses this invariant for an early exit: if during a key search a slot is found whose PSL is smaller than the search's current traveled distance, the sought key definitely isn't in the table (it couldn't have "jumped over" an element with a smaller PSL without displacing it) — the search can stop without checking the remaining slots.

struct Entry { int key, val, psl; bool occupied = false; };

void put(std::vector<Entry>& table, int key, int val) {
    size_t idx = h(key) % table.size();
    Entry incoming{key, val, 0, true};
    while (true) {
        if (!table[idx].occupied) { table[idx] = incoming; return; }
        if (table[idx].key == incoming.key) { table[idx].val = incoming.val; return; }
        if (table[idx].psl < incoming.psl)          // incoming "богаче" — забирает слот// incoming is "richer" — takes the slot
            std::swap(table[idx], incoming);
        incoming.psl++;
        idx = (idx + 1) % table.size();
    }
}

Каждый слот показывает ключ и его текущий PSL. Жёлтая рамка — слот, участвующий в текущем шаге. Красная вспышка — момент обмена ("воровство" позиции у ключа с меньшим PSL).Each slot shows its key and current PSL. The yellow outline is the slot involved in the current step. A red flash marks the moment of a swap ("stealing" a spot from a key with a smaller PSL).

Средний случай Robin Hood hashing асимптотически такой же, как у обычной открытой адресации — O(1). Выигрыш не в среднем, а в форме распределения: максимальная длина пробирования (worst PSL по всей таблице) растёт как O(log n) с высокой вероятностью, а не линейно с load factor, как у наивного linear probing. Для систем, чувствительных к задержке хвоста распределения (99-й перцентиль времени ответа, а не среднее) — например, кэшей в реальном времени или сервисов с SLA на задержку — именно эта гарантия по худшему отдельному запросу, а не средняя скорость, определяет практическую пригодность структуры.Robin Hood hashing's average case is asymptotically the same as plain open addressing — O(1). The gain isn't in the average but in the distribution's shape: the maximum probe length (the worst PSL across the whole table) grows as O(log n) with high probability, rather than linearly with the load factor as with naive linear probing. For systems sensitive to tail latency (the 99th percentile response time, not the average) — e.g. real-time caches or services with a latency SLA — it's precisely this guarantee on the single worst request, not average speed, that determines the structure's practical fitness.