Цепочки против открытой адресации: что выбрать

Если ты можешь сравнить цепочки (≈1+α) и открытую адресацию (≈1/(1−α)) по числу проб при заданном α и знаешь, когда какой способ выбрать, листай до «Теперь сам».

Как думаешь, какой способ быстрее

Мы разобрали цепочки и открытую адресацию - оба решают коллизии, но устроены противоположно: одни выносят лишние ключи в списки, другие теснят их в тот же массив. Значит у них разная цена, и она по-разному зависит от заполнения α. Наивный ответ «открытая адресация быстрее, потому что без указателей» верен не всегда: при высоком заполнении она резко проседает. Чтобы выбирать осознанно, надо СРАВНИТЬ их по главной метрике - числу проб на поиск - при разных α, и увидеть, где проходит граница. Тогда «что выбрать» перестанет быть догадкой.

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

Два способа рассадить гостей на переполненном банкете. Цепочки - поставить к каждому столу приставные стулья: сколько гостей ни придёт, всех усадим (стульев подтащим), но зал загромождён, и официант бегает между приставками. Открытая адресация - жёстко N стульев, занял свой - ищи ближайший свободный: пока зал полупуст, садишься мгновенно и всё компактно; но когда занято 95%, ты обходишь полстолов в поисках места, а при 100% сесть НЕКУДА. Пока свободно - тесная рассадка быстрее; под завязку - приставные стулья спасают.

Механизм: две формулы числа проб

Главная метрика - среднее число ячеек, которые надо проверить на поиск, как функция от α.

Цепочки: поиск проходит список ячейки, средняя длина которого α, плюс сама ячейка:

проб ≈ 1 + α          # линейно и мягко; α может быть любым (даже > 1)

Открытая адресация (при равномерном пробировании), неудачный поиск:

проб ≈ 1 / (1 − α)    # взрывается у α = 1; требует α < 1

Подставим значения и сравним:

Видно: до α ≈ 0.7 оба дёшевы и близки, после - открытая адресация улетает вверх, а цепочки растут еле-еле.

Правило

Цепочки: поиск ≈ 1 + α проб (растёт мягко, α любой, удаление простое, память на указатели, плохая локальность). Открытая адресация: поиск ≈ 1/(1 − α) проб (взрывается у α = 1, α < 1 обязателен, удаление через надгробия, отличная локальность памяти). До α ≈ 0.7 оба быстры и открытая адресация обычно выигрывает по КЕШУ; выше - она резко деградирует, а цепочки лишь плавно замедляются. Правило: держи α низким и бери открытую адресацию ради локальности; нужна устойчивость к переполнению или много удалений - бери цепочки.

Разбор: почему 1/(1−α) взрывается, а 1+α - нет

Разница в формулах отражает разную природу. В цепочках лишние ключи уходят В СПИСОК, вне массива: сколько бы ни было коллизий, они не мешают ЧУЖИМ ячейкам. Средняя длина списка α растёт линейно с числом ключей - отсюда мягкое 1 + α. В открытой адресации лишний ключ занимает ЧУЖУЮ ячейку, удлиняя пробы для всех, кто в неё метил, - коллизии взаимодействуют, эффект нелинеен. Когда свободных ячеек почти не осталось (α → 1), каждая проба редко попадает в пустую, и их число 1/(1−α) устремляется в бесконечность: при α = 0.99 это 100 проб, при α = 0.999 - 1000. Знаменатель 1 − α - это доля свободных ячеек, и деление на неё показывает: чем меньше свободного места, тем дольше его искать. Поэтому открытую адресацию НЕЛЬЗЯ подпускать к полному заполнению, а цепочки терпят его спокойно.

Разбор: почему на практике часто выбирают открытую адресацию, хоть формула хуже

Парадокс: формула проб у открытой адресации хуже (1/(1−α) против 1+α), но быстрые современные библиотеки выбирают именно её. Причина - КОНСТАНТА за одной пробой, которую асимптотика не видит. Проба в открытой адресации - это чтение СОСЕДНЕЙ ячейки того же массива, а он лежит в памяти сплошняком: процессор подтягивает его в кеш пачками, и десять проб подряд - это десять чтений из быстрого кеша. Шаг по цепочке - это прыжок по УКАЗАТЕЛЮ на узел, разбросанный по куче: почти каждый такой шаг - промах мимо кеша и поход в медленную основную память, а он в разы дороже. Поэтому при низком α (где проб и там, и там мало) открытая адресация с её кеш-дружелюбием выигрывает по РЕАЛЬНОМУ времени, хотя «проб» у неё формально больше. Это тот же урок, что в разделе про массивы: асимптотика считает операции, а железо ещё и любит локальность - и на практике второе часто решает.

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

Первая ошибка - выбирать способ по одной асимптотике, игнорируя кеш: «у цепочек 1+α меньше, значит они быстрее» - неверно на практике при низком α, где локальность открытой адресации перевешивает. Второе - гнать открытую адресацию к высокому α (0.9+): 1/(1−α) взрывается, и она становится драматически медленной; там либо рехешь раньше, либо цепочки. Третье - брать цепочки, когда важны память и скорость, а удалений и переполнения нет: заплатишь указателями и промахами кеша зря. Четвёртое - забыть, что обе формулы предполагают РАВНОМЕРНУЮ функцию: на плохой функции обе деградируют к O(n) независимо от α.

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

Выбор между цепочками и открытой адресацией - реальное инженерное решение, которое авторы библиотек делают за тебя, но понимать его нужно. Оно объясняет, почему современные dict (Python, Rust, быстрые C++) - открытая адресация (кеш решает при низком α), а HashMap в Java - цепочки (с превращением длинных цепочек в деревья ради защиты худшего случая). Для своего кода вывод практический: если делаешь хеш-таблицу сам или настраиваешь чужую - держи α низким (≤ 0.7) при открытой адресации, не жди чуда от неё под завязку, а при массовых удалениях помни про надгробия (или бери цепочки). А главная мысль - что асимптотика проб не единственный критерий: локальность памяти на реальном железе часто важнее, и именно поэтому «худшая по формуле» открытая адресация побеждает в бенчмарках. Это зрелый взгляд: считать не только операции, но и то, как они ложатся на память.

Теперь сам

При α = 0.9 посчитай среднее число проб для цепочек и для открытой адресации. Во сколько раз разница, и что она говорит о выборе способа при высоком заполнении?