Конспект: цепочки и открытая адресация

Понятия

Метод цепочек (chaining) - каждая ячейка хранит СПИСОК попавших в неё ключей. Вставка O(1) (в начало списка ячейки h(ключ)); поиск/удаление - h(ключ) плюс проход по списку. Поиск ≈ 1 + α. Допускает α > 1, простое удаление, не ломается от переполнения. Плата - память на указатели, разброс по куче (плохая локальность).

Открытая адресация (open addressing) - ключи лежат ПРЯМО в массиве; при коллизии пробируют следующие ячейки. Поиск идёт по цепочке проб до ключа или до ПУСТОЙ ячейки. Поиск ≈ 1/(1 − α), α < 1 обязателен. Отличная локальность памяти.

Пробирование - правило обхода ячеек при коллизии: - линейное h, h+1, h+2, … (страдает кластеризацией); - квадратичное h + i² (гасит первичную кластеризацию, остаётся вторичная); - двойное h₁ + i·h₂(ключ) (шаг задаёт вторая функция, кластеры почти исчезают - лучшее).

Надгробие (tombstone) - пометка «удалено, но не пусто». Нужна, потому что опустошить ячейку нельзя - пустота посреди чужой цепочки проб оборвёт поиск. Поиск идёт сквозь надгробие дальше; надгробия копятся и требуют периодической уборки (рехеш).

Кластеризация - слипание занятых ячеек в сгустки; самоусиливается (большие кластеры притягивают ключи сильнее). Удлиняет пробы даже при умеренном α.

Что унести

Два способа - противоположные компромиссы.

Число проб при заданном α:

Правило выбора: до α ≈ 0.7 оба быстры, и открытая адресация ВЫИГРЫВАЕТ по реальному времени за счёт кеша (проба - чтение соседней ячейки, а не прыжок по указателю) - потому её берут быстрые современные dict. Нужна работа под завязку или частые удаления - цепочки (так HashMap в Java, с превращением длинных цепочек в деревья). Асимптотика проб - не единственный критерий: локальность памяти часто решает.

Ловушки джокера

При коллизии положил в соседнюю ячейку, а ищешь только в h(ключ). Не найдёшь. Всё с одним номером - в одном списке (цепочки) или по одной цепочке проб (адресация).

Не сравнил сами КЛЮЧИ при проходе. В одной ячейке/цепочке разные ключи с одним хешем.

Удалил, опустошив ячейку (открытая адресация). Порвал чужую цепочку проб. Нужны надгробия.

Остановился на надгробии как на пустой ячейке. Сквозь надгробие идут ДАЛЬШЕ.

Заполнил открытую адресацию под завязку (α → 1). 1/(1−α) взрывается; вставить некуда, поиск зацикливается.

Выбрал способ по одной асимптотике. При низком α кеш-локальность открытой адресации бьёт «лучшую» формулу цепочек.

Проверь себя

Как цепочки хранят столкнувшиеся ключи и почему поиск O(1 + α)?

Как работает пробирование и почему открытой адресации нужен α < 1?

Зачем нужны надгробия и что будет без них?

Что такое кластеризация и чем её лечат?

При α = 0.9 сколько проб у каждого способа и что это значит для выбора?