Разрешение коллизий: Chaining vs Open Addressing

Цели урока

• Понять почему коллизии неизбежны
• Освоить метод цепочек (chaining)
• Изучить открытую адресацию и стратегии пробирования
• Научиться выбирать метод под задачу

Предварительные знания

• Хеш-таблицы: основы

• Хеш-таблицы: O(1) доступ

Два гостя приходят в отель и оба получают номер 42. Что делать администратору? Выгнать одного? Поселить в коридоре? Или придумать умную систему?

• Python dict - open addressing в действии
• Java HashMap - chaining с деревьями
• Redis - open addressing для скорости
• Базы данных - разные стратегии для индексов

Полвека идей разрешения коллизий

Метод цепочек предложил ещё Ханс Петер Лун в той же записке IBM 1953 года, где он впервые описал хеширование. Открытую адресацию с линейным пробированием придумали примерно в 1954 году инженеры IBM, работавшие над машиной 701, среди них Джин Амдал, Элейн Бойм и Натаниэль Рочестер. Идея простая: если слот занят, идём по таблице дальше, пока не найдём пустой. Анализ линейного пробирования стал классической задачей, и его подробно разобрал Дональд Кнут в третьем томе The Art of Computer Programming. Дальше схемы становились всё умнее. В 1985 году Педро Селис предложил Robin Hood hashing: при вставке элемент с большим смещением от своего идеального слота вытесняет элемент с меньшим, выравнивая длины проб. В 2001 году Расмус Паг и Фледжер Родлер описали cuckoo hashing с гарантированным O(1) в худшем случае для поиска: каждый ключ имеет два возможных места, и при конфликте старый элемент выселяется во второе место, как кукушка выталкивает чужие яйца.

Почему коллизии неизбежны

**Принцип голубятни (Pigeonhole Principle):** если у вас 11 голубей и 10 клеток - минимум в одной клетке будет 2 голубя.

Аналогично: если возможных ключей бесконечно много, а слотов в таблице конечно - коллизии **гарантированы**.

**Вопрос не "будут ли коллизии?"**, а **"как их обрабатывать?"**

Метод цепочек (Chaining)

**Идея:** каждый слот хранит не один элемент, а **связный список** всех элементов с таким хешем.

• Простая реализация
• Удаление элемента - просто
• Таблица никогда не переполняется
• Минус: дополнительная память на указатели
• Минус: плохая локальность кеша (элементы разбросаны)

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

**Идея:** если слот занят - ищем следующий свободный слот в самой таблице.

Нет дополнительных структур - все данные хранятся прямо в массиве.

• Лучшая локальность кеша (данные рядом в памяти)
• Меньше памяти (нет указателей)
• Минус: сложнее удаление (нужен маркер DELETED)
• Минус: при высоком Load Factor - кластеризация

Стратегии пробирования

Как именно искать следующий слот при коллизии?

1. Линейное пробирование

2. Квадратичное пробирование

3. Двойное хеширование

Chaining vs Open Addressing: Что выбрать?

**Python dict** использует open addressing с двойным хешированием. **Java HashMap** использует chaining (с переходом в дерево при длинных цепочках).

**Практическое правило:** для высокопроизводительных систем с контролируемым Load Factor выбирайте open addressing. Для общего использования - chaining проще и надёжнее.

Итоги

• Коллизии неизбежны (принцип голубятни)
• Chaining: каждый слот - список элементов
• Open Addressing: ищем следующий свободный слот
• Линейное < Квадратичное < Двойное хеширование по качеству
• Выбор метода зависит от требований к памяти и производительности

Дальше

Теперь когда устройство хеш-таблиц понятно - время применить их на практике!

• Two Sum и другие хиты — Классические задачи на хеш-таблицы

Связанные уроки

• ds-06-hash-intro — Hash table basics before collision resolution
• ds-08-hash-applications — Collision strategy choice affects application performance
• ds-02-linked-lists — Chaining uses linked lists to store colliding elements
• ds-01-arrays — Open addressing probes within the array itself
• crypto-19-hash-functions