Открытая адресация: искать свободное место рядом

Коротко

Открытая адресация хранит ключи ПРЯМО в ячейках массива, без списков. Если ячейка h(ключ) занята, ищут следующую свободную по фиксированному правилу - пробированию. Простейшее - линейное: h, h+1, h+2, … по кругу. Поиск идёт по той же цепочке проб, пока не найдёт ключ или пустую ячейку (пустая = «дальше искать незачем»). Плюс - вся таблица в одном массиве, отличная локальность памяти (кеш любит), никаких указателей. Минусы - α < 1 обязателен (в занятую таблицу вставить некуда), удаление хитрое (нельзя просто опустошить ячейку - порвёшь цепочку проб), и кластеризация: занятые ячейки слипаются в длинные сгустки, замедляя пробы. Лечится это лучшими пробированиями - квадратичным и двойным хешированием.

Если ты умеешь вставлять и искать линейным пробированием, понимаешь, почему α < 1 обязателен, почему удаление требует «надгробий» и что такое кластеризация (и как её лечат квадратичное/двойное хеширование), листай до «Теперь сам».

Как думаешь, можно ли обойтись без списков в ячейках

Цепочки просты, но за каждым ключом тянется узел списка - лишняя память и прыжок по куче (процессор не любит: данные разбросаны, кеш промахивается). А что если хранить ключи прямо в массиве, как обычные элементы, - плотно, без указателей? Тогда встаёт вопрос: куда деть ключ, если его ячейка h(ключ) уже занята другим? Ответ открытой адресации - положить в БЛИЖАЙШУЮ свободную по заранее оговорённому правилу. А при поиске идти по тому же правилу, проверяя ячейки одну за другой, пока не встретим искомый ключ или пустоту. Всё в одном массиве, вплотную - но за компактность придётся заплатить новыми сложностями.

На что это похоже

Парковка, где у тебя есть «своё» любимое место (номер h(ключ)). Приехал - место занято. Ты не уезжаешь и не строишь пристройку (это были бы цепочки) - ты едешь к следующему свободному: +1, ещё занято - +2, и так по кругу, пока не встанешь. Когда тебя ищут, делают то же самое: смотрят твоё место, потом следующее, следующее - пока не найдут твою машину или пустое место (пустое значит «дальше он бы не поехал, его тут нет»). Беда в том, что у популярного въезда машины скапливаются в плотный ряд, и объезжать его долго - это и есть кластеризация.

Механизм: линейное пробирование

Ключи лежат в самом массиве. При коллизии пробуем следующие ячейки по кругу:

вставить(ключ):
    i = h(ключ)
    пока ячейка i занята (и не тем же ключом):
        i = (i + 1) mod m          # линейная проба: следующая по кругу
    положить ключ в ячейку i

найти(ключ):
    i = h(ключ)
    пока ячейка i не пуста:
        если в ней ключ - нашли
        i = (i + 1) mod m
    вернуть «нет»                    # дошли до ПУСТОЙ - ключа нет

Пустая ячейка при поиске означает «стоп, дальше его быть не может» - если бы ключ был, при вставке он занял бы эту самую пустую ячейку раньше. Отсюда жёсткое требование: α < 1, хотя бы одна ячейка всегда пуста, иначе поиск несуществующего ключа зациклится, а вставке некуда класть. При равномерном пробировании среднее число проб на неудачный поиск - около 1/(1 − α): при α = 0.5 это 2, при α = 0.9 - уже 10. Поэтому открытую адресацию держат заметно недозаполненной (α ≤ 0.7).

Ключ метит в ячейку 2, но она и 3 заняты (кластер), поэтому он садится в 4. Слипшиеся занятые ячейки - кластеризация - удлиняют цепочки проб для всех, кто в них метит.

Правило

Открытая адресация хранит ключи прямо в массиве; при коллизии ищет свободную ячейку по правилу ПРОБИРОВАНИЯ (линейное: h, h+1, h+2, … по кругу). Поиск идёт по той же цепочке до ключа или до ПУСТОЙ ячейки (пустая = «дальше нет»). Требует α < 1; среднее число проб на неудачный поиск ≈ 1/(1 − α). Достоинство - компактность и локальность (всё в массиве, кеш доволен, нет указателей). Недостатки - кластеризация, хитрое удаление и обязательный запас свободных ячеек.

Разбор: почему удаление требует «надгробий»

Удаление в открытой адресации - коварная ловушка. Нельзя просто опустошить ячейку удаляемого ключа: она стоит в чьей-то цепочке проб, и пустота посреди цепочки оборвёт поиск. Пример: A лёг в ячейку 2, B метил туда же и по пробе сел в 3. Удалим A, опустошив ячейку 2. Теперь ищем B: h(B) = 2, ячейка 2 ПУСТА - поиск говорит «B нет», хотя B рядом, в ячейке 3. Цепочка порвана. Лечат это надгробием (tombstone) - особой пометкой «удалено, но не пусто»: поиск проходит сквозь надгробие дальше (цепочка цела), а вставка может занять надгробие повторно. Расплата - надгробия копятся, удлиняют пробы, и таблицу приходится периодически перестраивать (рехешировать), очищая их. В цепочках такого нет вовсе: удалил узел из списка - и всё. Это ещё один налог открытой адресации за компактность.

Разбор: почему кластеризация замедляет линейное пробирование

Линейное пробирование страдает первичной КЛАСТЕРИЗАЦИЕЙ - занятые ячейки слипаются в длинные сгустки, и это самоусиливается. Смотри: чем длиннее сгусток занятых подряд ячеек, тем больше хешей в него метит (любой h, попавший в начало или середину сгустка, докатится до его конца), тем чаще к нему добавляется новый ключ - и сгусток растёт ещё быстрее. Большие кластеры притягивают ключи сильнее маленьких, богатые богатеют. В итоге даже при умеренном α пробы становятся длинными не потому, что таблица полна, а потому что занятость собрана в комки. Лечат это, разрывая линейность: - квадратичное пробирование: пробы h+1², h+2², h+3², … - шаги растут, ключи не липнут в один ряд (но остаётся вторичная кластеризация: одинаковый h даёт одинаковую последовательность проб); - двойное хеширование: шаг пробы задаёт ВТОРАЯ хеш-функция, h₁ + i·h₂(ключ) - у разных ключей разные шаги, кластеры почти исчезают, это лучшее из простых пробирований.

Что ломается без этого

Первая ошибка - допустить α = 1 (заполнить таблицу под завязку): вставить некуда, а поиск несуществующего ключа зациклится (нет пустой ячейки, чтобы остановиться). Держи α < 1, обычно ≤ 0.7. Второе - удалять ключ, просто опустошая ячейку: порвёшь чужие цепочки проб, и рядом лежащие ключи «пропадут». Нужны надгробия. Третье - линейное пробирование на высоком α без нужды: кластеризация сделает пробы длинными; при плотном заполнении бери двойное хеширование. Четвёртое - при поиске остановиться на надгробии как на пустой ячейке: сквозь надгробие надо идти дальше, иначе не найдёшь ключи за ним.

Зачем это в работе

Открытая адресация - выбор большинства СОВРЕМЕННЫХ быстрых хеш-таблиц: dict в Python (с хитрым пробированием), хеш-множества в Rust, flat_hash_map и подобные в C++. Причина - локальность памяти: все ключи лежат вплотную в одном массиве, процессор читает их из кеша пачками, тогда как цепочки прыгают по указателям и промахиваются мимо кеша. На современном железе это часто перевешивает теоретическую простоту цепочек. Понимать открытую адресацию - значит знать, почему dict так быстр, почему его нельзя набивать под завязку (α держат низким), и почему удаление из хеш-таблицы иногда «оставляет мусор» (надгробия), требующий периодической уборки. А знание про кластеризацию и двойное хеширование объясняет, почему авторы библиотек так возятся с выбором функции пробирования - от неё напрямую зависит скорость при высоком заполнении.

Теперь сам

Таблица открытой адресации, m = 7, h(k) = k mod 7, линейное пробирование. Вставляем 10, 17, 3. Куда ляжет каждый? Почему нельзя удалить 10, просто опустошив его ячейку?

Ответ. 10 mod 7 = 3 - ячейка 3 свободна, 10 садится в 3. 17 mod 7 = 3 - ячейка 3 занята десяткой, пробуем 4 - свободна, 17 садится в 4. 3 mod 7 = 3 - ячейка 3 занята, 4 занята (там 17), пробуем 5 - свободна, 3 садится в 5. Итог: ячейка 3 - 10, ячейка 4 - 17, ячейка 5 - 3; получился кластер из трёх подряд. Удалить 10, опустошив ячейку 3, нельзя: и 17, и 3 метили в ячейку 3 (h = 3 у всех троих) и стоят в цепочке проб, начинающейся с 3. Опустошим 3 - и поиск 17 (h = 3, ячейка 3 теперь ПУСТА) решит, что 17 нет, хотя он в ячейке 4. Цепочка порвётся. Поэтому вместо опустошения ставят надгробие: поиск проходит сквозь него к 17 и 3, а новая вставка может занять его место.

Главное

Открытая адресация хранит ключи ПРЯМО в массиве; при коллизии ищет свободную ячейку по правилу пробирования (линейное h, h+1, … по кругу; квадратичное h+i²; двойное h₁ + i·h₂). Поиск идёт по той же цепочке до ключа или до ПУСТОЙ ячейки. Требует α < 1 (обычно ≤ 0.7), среднее число проб ≈ 1/(1 − α). Достоинство - компактность и локальность памяти (кеш, нет указателей), оттого её выбирают быстрые современные dict. Цена: удаление требует НАДГРОБИЙ (пустота порвёт цепочку проб), а линейное пробирование страдает КЛАСТЕРИЗАЦИЕЙ (занятые слипаются, сгустки растут самоусиливаясь) - лечится квадратичным и особенно двойным хешированием.