От ключа к номеру ячейки: зачем нужна хеш-функция

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

Как думаешь, как искать по имени, а не по номеру

Массив ищет мгновенно, но только по ЦЕЛОМУ индексу: a[5] - сразу, без перебора. А если ключ - это строка «Иванов» или число-паспорт из десяти цифр? По имени в массив не обратишься. Наивный ответ - хранить пары «ключ-значение» в списке и искать перебором, но это O(n) на каждый поиск. Хочется сохранить магию массива - доступ за O(1), - но по ЛЮБОМУ ключу. Для этого нужен переводчик: устройство, которое из произвольного ключа делает целый номер ячейки. Тогда «положить по ключу» и «взять по ключу» станут обращением к массиву по вычисленному индексу - и снова O(1).

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

Гардероб в театре. Ты сдаёшь пальто и получаешь номерок - и работница НЕ обходит все крючки в поисках твоего пальто, когда ты возвращаешься. Номерок сразу указывает крючок. Хеш-функция - это машинка, которая по твоему пальто (ключу) выдаёт номер крючка: одинаковое пальто - всегда тот же номерок (детерминизм), номерки распределены по всем крючкам ровно (равномерность), выдаются мгновенно (быстрота). Сдал - повесили на крючок h(пальто), пришёл - сняли с того же крючка. Ни одного лишнего шага по гардеробу.

Механизм: хеш-функция и деление по модулю

Хеш-таблица - это массив из m ячеек плюс хеш-функция h, отображающая ключ в индекс [0, m). Операции:

положить(ключ, значение):  таблица[h(ключ)] = значение
взять(ключ):               вернуть таблица[h(ключ)]

От хеш-функции требуют три свойства:

1. Детерминированность - один и тот же ключ всегда даёт один и тот же номер (иначе положишь в одну ячейку, а искать будешь в другой).
2. Равномерность - ключи разбрасываются по ячейкам РОВНО, без перекосов (иначе всё свалится в пару ячеек, и поиск выродится в перебор).
3. Быстрота - сам подсчёт h(ключ) должен быть O(1), иначе выигрыш съедается.

Простейшая хеш-функция для целых - деление по модулю: h(k) = k mod m - остаток от деления на размер таблицы. Он всегда в [0, m) - как раз номер ячейки. Ключ-строку сперва превращают в число (например, складывая коды символов с весами), а потом берут по модулю.

Правило

Хеш-функция h(ключ) → [0, m) превращает произвольный ключ в номер ячейки массива из m клеток, давая доступ по ключу за O(1) в среднем. Она обязана быть ДЕТЕРМИНИРОВАННОЙ (ключ → всегда тот же номер), РАВНОМЕРНОЙ (ключи ложатся по ячейкам ровно) и БЫСТРОЙ (O(1) на подсчёт). Простейшая - деление по модулю h(k) = k mod m с ПРОСТЫМ m. На хеш-функции стоят словарь (map) и множество (set) - структуры, которые кладут, берут и проверяют наличие ключа почти за константу.

Разбор: почему m берут простым, а не степенью двойки

Соблазн взять m степенью двойки (mod 2^b - это дёшево, просто младшие биты). Но тогда h(k) зависит ТОЛЬКО от младших b бит ключа, а старшие отбрасываются. Если ключи похожи в младших битах (например, все чётные, все кратные 4, все с одинаковым окончанием - а такое в реальных данных сплошь и рядом: адреса, идентификаторы с шагом), они посыплются в одни и те же ячейки - равномерность рухнет. Простое m (не делящее типичные закономерности в данных) перемешивает ВСЕ биты ключа в остаток: k mod m при простом m зависит от всего числа, а не от его хвоста. Поэтому классический совет - брать m простым и подальше от степеней двойки. Это тот же урок, что и везде в хешировании: равномерность не даётся сама, её обеспечивает устройство хеш-функции.

Разбор: почему это O(1) в среднем, а не всегда

Важная оговорка в определении - «O(1) в СРЕДНЕМ». Сам подсчёт h(ключ) и обращение к таблица[индекс] - честная константа. Но два разных ключа могут дать ОДИН номер ячейки (как 8 и 15 на схеме) - это коллизия, и она неизбежна, когда ключей больше, чем ячеек (следующий урок). Разрешение коллизий добавляет работу: в худшем случае, если все ключи свалились в одну ячейку, поиск выродится в перебор O(n). Поэтому строго говорят: хеш- таблица даёт O(1) в среднем ПРИ хорошей (равномерной) хеш-функции и разумной заполненности, но НЕ гарантирует O(1) в худшем случае. Это принципиальное отличие от дерева поиска (следующий раздел), которое даёт O(log n) гарантированно. Понимать эту разницу - значит не обещать «словарь - это всегда константа» там, где важен худший случай.

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

Первая ошибка - недетерминированная хеш-функция (например, зависящая от времени или от адреса объекта в памяти, который меняется): положишь по одному номеру, искать будешь по другому - и не найдёшь. Второе - неравномерная функция (h(k) = 0 для всех, или mod степени двойки на «хвостатых» данных): все ключи в одной ячейке, поиск O(n), вся выгода испарилась. Третье - медленная хеш-функция (перебор всей длинной строки с тяжёлыми операциями на каждый поиск): константа подсчёта становится большой, и словарь проигрывает даже списку на малых данных. Четвёртое - забыть, что h даёт O(1) лишь В СРЕДНЕМ, и закладываться на константу там, где нужен худший случай.

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

Хеш-таблица - самая используемая структура данных после массива. Словарь в Python (dict), Map в JavaScript, HashMap в Java, unordered_map в C++ - всё это хеш-таблицы, и на них держится половина кода: подсчёт частот, кеши, индексы «по ключу», дедупликация, множества. Понимание хеш-функции объясняет, ПОЧЕМУ x in myset быстрее x in mylist (множество считает номер ячейки и смотрит одну, список перебирает все) - и это не мелочь: замена списка на множество превращает O(n²) в O(n) в реальном коде постоянно. А знание, что хеш - это O(1) в СРЕДНЕМ, а не всегда, уберегает от сюрпризов там, где важен худший случай или где данные подобраны злонамеренно (об этом в главе про универсальное хеширование). Хеш-функция - мост от «ключ» к «мгновенному доступу», и без неё словарей бы не было.

Теперь сам

Хеш-таблица из m = 10 ячеек, h(k) = k mod 10. Куда лягут ключи 23, 47, 33? Что не так с выбором m = 10 для ключей, которые все оканчиваются на 0 (10, 20, 30, …)?