Идеальное хеширование: O(1) в худшем случае для статичного набора

Если ты понимаешь, зачем нужен статичный набор, как устроены два уровня идеального хеширования и почему второй уровень берут размером k² (парадокс дней рождения наоборот), листай до «Теперь сам».

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

Коллизии неизбежны, когда ключей больше, чем ячеек, - это мы доказали (Дирихле). Но что, если ячеек взять БОЛЬШЕ, чем ключей, да ещё знать все ключи ЗАРАНЕЕ? Тогда можно перебирать хеш- функции, пока не найдётся такая, что разложит именно эти ключи вообще без столкновений. Загвоздка в памяти: чтобы гарантированно избежать коллизий среди n ключей, ячеек нужно очень много (порядка n² - следствие парадокса дней рождения), а это неприемлемый расход. Кажется, выбор между «мало памяти, но коллизии» и «нет коллизий, но памяти квадрат». Идеальное хеширование находит третий путь - двухуровневую схему, где квадрат берётся только ВНУТРИ маленьких корзин, и суммарная память остаётся линейной.

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

Библиотека с фиксированным, никогда не меняющимся собранием книг. Раз состав известен и постоянен, библиотекарь может ОДИН РАЗ продумать идеальную расстановку: у каждой книги свой единственный адрес, и находишь её мгновенно, без поиска по полке. Такую расстановку нельзя сделать для магазина, куда книги приходят и уходят каждый день (динамический набор) - при каждом изменении всё пришлось бы перекраивать. Но для АРХИВА с неизменным составом идеальный план окупается: строишь его однажды и потом всегда попадаешь в цель с первого раза. Идеальное хеширование - такой план для заранее известного, неизменного набора ключей.

Механизм: два уровня

Уровень 1. Универсальной функцией h раскидываем n ключей по n корзинам (таблица размером m = n). Коллизии будут: в какие-то корзины попадёт по несколько ключей. Пусть в корзину j попало kⱼ ключей.

Уровень 2. Для КАЖДОЙ корзины j заводим отдельную маленькую таблицу размером kⱼ² со своей универсальной функцией hⱼ, подобранной так, чтобы kⱼ ключей корзины легли в неё БЕЗ единой коллизии.

поиск(ключ):
    j = h(ключ)                    # уровень 1: номер корзины, O(1)
    i = h_j(ключ)                  # уровень 2: место внутри корзины, O(1)
    вернуть таблица[j][i]          # ровно один ключ - без перебора
# два подсчёта хеша - и ты на месте. O(1) в ХУДШЕМ случае.

Поиск - два обращения по хешу, без всякого перебора цепочек: O(1) ГАРАНТИРОВАННО. Ключевой факт про память: хотя корзины второго уровня квадратичны (kⱼ²), их СУММА при хорошей функции первого уровня - всего O(n), а не O(n²).

Правило

Идеальное хеширование даёт поиск O(1) в ХУДШЕМ случае и память O(n) - но только для СТАТИЧНОГО набора ключей (известен заранее, не меняется). Схема двухуровневая: верхняя функция раскидывает n ключей по n корзинам (с коллизиями), а каждая корзина из kⱼ ключей разворачивается во вторичную таблицу размером kⱼ² со своей функцией БЕЗ коллизий. Размер k² берётся потому, что при m = k² ячейках k ключей укладываются без коллизий с вероятностью > 1/2 (парадокс дней рождения наоборот), так что нужную функцию находят за пару попыток. Сумма Σ kⱼ² при хорошей верхней функции - O(n). Динамический набор так не захешируешь - при каждом изменении схему пришлось бы перестраивать.

Разбор: почему второй уровень размером k², а не k

Ключевой выбор - квадрат размера корзины. Возьми во вторичную таблицу m = k ячеек (столько же, сколько ключей) - и по парадоксу дней рождения коллизии почти неизбежны (k ключей на k ячеек - это α = 1, ожидаемых коллизий порядка k). Не годится: нам нужен НОЛЬ коллизий. Возьми m = k² ячеек - вот тут парадокс дней рождения работает НА нас: ожидаемое число коллизий ≈ k²/(2m) = k²/(2k²) = 1/2, то есть в среднем меньше одной. Значит вероятность, что СЛУЧАЙНАЯ функция уложит k ключей в k² ячеек вообще без коллизий, больше 1/2 - и, перебирая функции из семейства, мы находим бескризисную за пару попыток (в среднем меньше двух). Тот же парадокс дней рождения, что раньше пугал ранними коллизиями, здесь работает в нашу пользу: дай ячеек КВАДРАТ от числа ключей - и коллизии становятся редкостью, которую легко обойти выбором функции.

Разбор: почему суммарная память всё-таки O(n), а не O(n²)

Пугает квадрат: если каждая из n корзин имеет размер kⱼ², не выйдет ли суммарно O(n²)? Нет - и здесь важна МАТЕМАТИКА распределения. Сумма Σ kⱼ² велика, только если ключи собрались в немногих больших корзинах (одна корзина с n ключами дала бы n²). Но верхняя функция - универсальная, она раскидывает ключи РОВНО, и корзины выходят маленькими: можно доказать, что при m = n корзинах ожидаемая сумма Σ kⱼ² не превышает 2n - то есть O(n). Интуиция: квадрат наказывает большие корзины, но универсальная функция их не создаёт - все kⱼ малы, а сумма квадратов маленьких чисел мала. Если случайный выбор верхней функции дал слишком большую Σ kⱼ² (скажем, больше 4n - при ожидании до 2n так выходит не чаще чем в половине выборов), её просто ПЕРЕВЫБИРАЮТ: в среднем хватает двух попыток. Так квадрат живёт лишь ВНУТРИ маленьких корзин, а снаружи всё линейно - в этом вся хитрость двухуровневой схемы.

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

Первая ошибка - применять идеальное хеширование к ДИНАМИЧЕСКОМУ набору (ключи добавляются и удаляются): вся схема построена под конкретный набор, и добавление ключа может создать коллизию во вторичной таблице, требуя перестройки корзины или всей структуры. Идеальное хеширование - только для статики. Второе - брать вторичную таблицу размером k вместо k²: коллизии вернутся, «идеальность» пропадёт. Третье - пугаться квадрата и решить, что память O(n²): при универсальной верхней функции Σ kⱼ² = O(n), надо лишь перевыбрать функцию, если не повезло. Четвёртое - путать идеальное хеширование (гарантия O(1) в худшем, но статика) с универсальным (ожидание O(1), но динамика): это разные инструменты под разные условия.

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

Идеальное хеширование применяют там, где набор ключей ФИКСИРОВАН и важна гарантия скорости: таблицы зарезервированных слов компилятора (ключевые слова языка известны заранее - if, while, return, …), статические словари, таблицы маршрутизации, наборы допустимых команд. Инструменты вроде gperf генерируют идеальную хеш-функцию для заданного списка строк на этапе компиляции - и распознавание ключевого слова становится O(1) без единой коллизии. Понимать идеальное хеширование - значит знать, что бывает O(1) в ХУДШЕМ случае (не только в среднем), но за него платят условием статичности. А пара «универсальное (ожидание, динамика) + идеальное (гарантия, статика)» показывает общий принцип: чем больше знаешь о данных заранее, тем более сильную гарантию можно выжать. Это перекликается с сортировками (знаешь диапазон - сортируешь за линию) и с выбором алгоритма вообще: гарантии покупаются знанием о входе.

Теперь сам

В корзину идеального хеширования попало k = 4 ключа. Какого размера будет её вторичная таблица и почему такой размер гарантирует, что подходящую функцию (без коллизий) найдут быстро?