Цепочки: в каждой ячейке - список

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

Как думаешь, куда деть второй ключ, попавший в занятую ячейку

Коллизия случилась: h(8) = h(15) = 1, ячейка 1 уже занята восьмёркой, а надо положить и пятнадцать. Выбросить восьмёрку нельзя - потеряем данные. Класть пятнадцать в другую ячейку? Тогда при поиске мы посчитаем h(15) = 1, посмотрим ячейку 1, там восьмёрка - и решим, что пятнадцати нет, хотя она есть. Значит всё, что имеет один номер, должно лежать ТАМ ЖЕ, где его будут искать - в ячейке 1. Но ячейка одна, а ключей два. Простейший выход - пусть ячейка хранит не один ключ, а СПИСОК: и восьмёрку, и пятнадцать, и всех, кто ещё сюда попадёт. Поиск тогда - зайти в ячейку и пройти её список.

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

Многоквартирный дом с почтовыми ящиками, подписанными по первой букве фамилии. Все жильцы на «К» - Кузнецов, Ковалёв, Кириллов - бросают письма в ОДИН ящик «К». Почтальон не мечется по дому: он открывает ящик «К» и перебирает небольшую стопку писем внутри, пока не найдёт нужное. Ящиков всего 33 (по буквам), жильцов сотни - но в каждом ящике лежит лишь горстка. Ячейка хеш-таблицы с цепочкой - этот самый ящик: номер (буква) приводит к ящику мгновенно, а внутри - короткий список, который быстро перебрать.

Механизм: список в каждой ячейке

Таблица - массив из m ячеек, но каждая ячейка хранит СПИСОК (цепочку) попавших в неё ключей (с их значениями).

положить(ключ, значение):
    i = h(ключ)
    добавить (ключ, значение) в список таблица[i]     # O(1) - в начало списка

найти(ключ):
    i = h(ключ)
    пройти по списку таблица[i], сравнивая ключи        # длина списка ≈ α
    вернуть значение или «нет»

удалить(ключ):
    i = h(ключ)
    выкинуть узел с этим ключом из списка таблица[i]

Вставка - O(1): посчитали номер, добавили в начало списка ячейки. Поиск и удаление - O(1) на подсчёт h плюс проход по списку этой ячейки. При равномерной функции n ключей размазаны по m спискам, средняя длина списка - α = n/m, поэтому поиск - O(1 + α). Пока α небольшой, это почти константа.

Правило

Метод цепочек хранит в каждой ячейке СПИСОК попавших в неё ключей. Вставка - добавить в список ячейки h(ключ) за O(1); поиск и удаление - посчитать h(ключ) и пройти список этой ячейки. При равномерной функции средняя длина списка α = n/m, поэтому поиск - O(1 + α). Плата за простоту - память на указатели списков и то, что элементы разбросаны по памяти (плохая локальность). Зато α может быть и больше 1 (списки просто длиннее), а таблица не «портится» от заполнения.

Разбор: почему поиск - это O(1 + α), а не O(α)

Мелочь «1 +» важна, и вот почему. Любой поиск, даже в ПУСТОЙ ячейке, делает фиксированную работу: посчитать h(ключ) и обратиться к ячейке - это O(1), и оно есть всегда. Дальше идёт проход по списку - в среднем α шагов. Складываем: O(1) + O(α) = O(1 + α). Почему не просто O(α)? Потому что при α = 0 (пустая таблица) поиск всё равно стоит O(1) - подсчёт h никуда не девается, а O(0) неверно описал бы это. При маленьком α (скажем, 0.5) главный член - именно 1, поиск почти константа. При большом α (переполнение) главным становится α, и поиск деградирует к линейному по длине цепочек. Запись O(1 + α) честно показывает оба режима: константа плюс длина списка.

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

Ключевое достоинство цепочек - устойчивость к высокому α. Можно положить в таблицу из m = 100 ячеек хоть 1000 ключей (α = 10): просто списки станут в среднем по 10 элементов, поиск замедлится до O(1 + 10), но НИЧЕГО не сломается. Список растёт неограниченно. Это резко отличает цепочки от открытой адресации (следующий урок), где ключи лежат прямо в ячейках массива: там при α → 1 свободных ячеек не остаётся, и вставить некуда - таблица физически переполняется. Цепочки допускают α > 1, открытая адресация требует α < 1 жёстко. Поэтому цепочки прощают ошибку с размером: забыл рехешировать - получишь медленно, но верно; в открытой адресации забыл - получишь сбой вставки. За эту устойчивость цепочки платят памятью на указатели и разбросом элементов по куче.

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

Первая ошибка - при коллизии класть второй ключ в СОСЕДНЮЮ ячейку, но при поиске смотреть только h(ключ): положил в одну ячейку, ищешь в другой - не находишь. В цепочках всё с одним номером лежит в ОДНОМ списке. Второе - не сравнивать ключи при проходе по цепочке, а верить номеру ячейки: в списке лежат РАЗНЫЕ ключи с одним хешем, надо сверять сам ключ, а не только попадание в ячейку. Третье - думать, что цепочки дают O(1) независимо от α: при переполнении списки длинные, поиск O(1 + α) деградирует. Четвёртое - забыть про память: на каждый ключ - накладные расходы на узел списка (указатель), и на миллионах ключей это заметный перерасход против открытой адресации.

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

Метод цепочек - классическая и самая понятная реализация хеш-таблицы; так устроены HashMap в Java (при коллизиях - список, а при очень длинных цепочках он даже превращается в дерево для защиты худшего случая), хеш-таблицы в старых версиях Python и многих библиотеках. Знание цепочек объясняет, почему словарь остаётся рабочим даже при переполнении (просто медленнее) и почему рекомендация «сравнивай сами ключи, а не только хеши» - не педантизм, а необходимость (в одной ячейке разные ключи). Понимание O(1 + α) даёт практическое правило: держи α небольшим - и цепочки почти константны; дай ему вырасти - и получишь линейный поиск. А сравнение цепочек с открытой адресацией (следующие уроки) - это выбор, который делают авторы каждой стандартной библиотеки, и понимать его компромиссы полезно, чтобы знать, чего ждать от dict своего языка.

Теперь сам

В таблице с цепочками m = 4, h(k) = k mod 4. Кладём ключи 5, 9, 13, 2 по очереди. Как будут выглядеть цепочки и сколько сравнений займёт поиск 13?