Открытая АдресацияOpen Addressing

Вставка ключа k пробует позиции probe(k, 0), probe(k, 1), probe(k, 2), ... до первой свободной. Три классические схемы пробирования различаются только формулой probe: linear probing — probe(k, i) = (h(k) + i) mod cap, простой сдвиг на 1 при каждой коллизии; quadratic probing — probe(k, i) = (h(k) + i²) mod cap, шаги растут квадратично, разбивая длинные последовательные "заторы"; double hashing — probe(k, i) = (h₁(k) + i·h₂(k)) mod cap, шаг зависит от второй хеш-функции самого ключа, что делает последовательности проб разными для разных ключей даже при одинаковой начальной позиции.Inserting key k tries positions probe(k, 0), probe(k, 1), probe(k, 2), ... until the first free one. The three classic probing schemes differ only in the probe formula: linear probing — probe(k, i) = (h(k) + i) mod cap, a simple shift by 1 on each collision; quadratic probing — probe(k, i) = (h(k) + i²) mod cap, steps grow quadratically, breaking up long consecutive "clusters"; double hashing — probe(k, i) = (h₁(k) + i·h₂(k)) mod cap, the step depends on the key's own second hash function, making probe sequences different for different keys even from the same starting position.

Удаление вносит осложнение, не существующее в цепочках: слот нельзя просто пометить пустым — если он лежит на пути пробирования для какого-то другого ключа, поиск этого ключа прервётся раньше времени, ошибочно решив "ключа нет" при первой встреченной пустой ячейке. Решение — маркер-tombstone ("удалено, но не пусто"): поиск проходит сквозь него дальше, а вставка может переиспользовать эту позицию.Deletion introduces a complication that doesn't exist with chaining: a slot can't simply be marked empty — if it lies on some other key's probe path, that key's search will stop prematurely, wrongly concluding "not present" at the first empty cell encountered. The fix is a tombstone marker ("deleted, but not empty"): a search keeps going past it, while an insertion can reuse that position.

enum class Slot { EMPTY, OCCUPIED, DELETED };

template<typename K, typename V>
class OpenAddrTable {
    std::vector<Slot> state;
    std::vector<K> keys;
    std::vector<V> vals;

    size_t probe(const K& k, size_t i) const {
        return (h1(k) + i) % state.size();   // линейное пробирование// linear probing
    }
public:
    bool put(const K& key, const V& val) {
        size_t first_deleted = SIZE_MAX;
        for (size_t i = 0; i < state.size(); ++i) {
            size_t idx = probe(key, i);
            if (state[idx] == Slot::EMPTY) {
                size_t target = (first_deleted != SIZE_MAX) ? first_deleted : idx;
                keys[target] = key; vals[target] = val; state[target] = Slot::OCCUPIED;
                return true;
            }
            if (state[idx] == Slot::DELETED && first_deleted == SIZE_MAX) first_deleted = idx;
            else if (state[idx] == Slot::OCCUPIED && keys[idx] == key) { vals[idx] = val; return true; }
        }
        return false;  // таблица полна// table full
    }
};

Переключатель схемы меняет формулу probe. Кнопки put/get/delete запускают всю последовательность проб автоматически — оранжевая рамка показывает текущую проверяемую позицию, серая штриховка — tombstone (удалённый слот, который поиск должен пропускать, а вставка — может переиспользовать).The scheme switch changes the probe formula. The put/get/delete buttons run the whole probe sequence automatically — the orange outline shows the currently checked position, gray hatching is a tombstone (a deleted slot that search must skip past, and insertion may reuse).

Linear probing страдает от первичной кластеризации: как только образуется последовательный блок занятых слотов, любой новый ключ, хешируемый в него или рядом, удлиняет этот блок ещё больше — блоки растут непропорционально быстро относительно load factor. Quadratic probing смягчает это (растущий шаг i² быстро уводит пробирование прочь от кластера), но подвержено более мягкой версии — вторичной кластеризации: два ключа с одинаковым h(k) всегда порождают идентичную последовательность проб, даже если сами ключи разные. Double hashing устраняет и это: шаг зависит от второй хеш-функции конкретного ключа, поэтому даже при совпадении h₁ последовательности проб для разных ключей расходятся с первого же шага.Linear probing suffers from primary clustering: once a consecutive block of occupied slots forms, any new key hashing into or near it lengthens that block further — blocks grow disproportionately fast relative to the load factor. Quadratic probing eases this (the growing i² step quickly moves probing away from the cluster), but is subject to a milder version — secondary clustering: two keys with the same h(k) always produce an identical probe sequence, even though the keys themselves differ. Double hashing eliminates this too: the step depends on the specific key's second hash function, so even when h₁ matches, different keys' probe sequences diverge from the very first step.