Конспект: хеш-функция и коллизии

Понятия

Хеш-таблица - массив из m ячеек плюс хеш-функция; даёт доступ по ПРОИЗВОЛЬНОМУ ключу за O(1) в среднем. На ней стоят словарь (map) и множество (set).

Хеш-функция h(ключ) → [0, m) - переводит ключ в номер ячейки. Три свойства: ДЕТЕРМИНИРОВАННОСТЬ (ключ → всегда тот же номер), РАВНОМЕРНОСТЬ (ключи ложатся ровно), БЫСТРОТА (O(1) на подсчёт).

Деление по модулю h(k) = k mod m - простейшая функция для целых. m берут ПРОСТЫМ: степень двойки смотрит лишь на младшие биты ключа и рушит равномерность на закономерных данных.

Коллизия - h(k₁) = h(k₂) при k₁ ≠ k₂ (два ключа в одну ячейку). НЕИЗБЕЖНА.

Принцип Дирихле - при n > m коллизия ГАРАНТИРОВАНА любой функцией (предметов больше, чем ящиков).

Парадокс дней рождения - коллизия ВЕРОЯТНА уже при n ≈ √m ключах: ожидаемое число коллизий ≈ n²/(2m) (сталкиваются ПАРЫ, их ≈ n²/2). 23 человека → совпадение дня рождения с шансом >50%.

Коэффициент заполнения α = n/m - теснота таблицы. Среднее число проверок на поиск ≈ 1 + α. Держат небольшим (0.5–0.75).

Рехеширование - при α выше порога массив УДВАИВАЮТ и перекладывают ключи (пересчитав h под новое m). Разово O(n), амортизированно O(1) (как у растущего массива).

Прямая адресация - массив из U ячеек, ключ k лежит в ячейке k: O(1) в худшем случае, память Θ(U). Битовая шкала - то же для множества, U/8 байт.

Ленивая инициализация - два массива без обнуления и счётчик: ключ есть, если T[k] < top и S[T[k]] == k.

Что унести

Хеш-таблица - доступ по ключу за O(1) в СРЕДНЕМ, и в этой оговорке вся суть.

Практический вывод: x in myset быстрее x in mylist, потому что множество считает номер ячейки и смотрит одну, а список перебирает все. Замена списка на множество/словарь для проверки наличия превращает O(n²) в O(n) - самый частый способ ускорить код. И держи α в узде: если знаешь число ключей заранее, задай размер таблицы - рехешировок не будет.

Главное отличие от дерева поиска (следующий раздел): хеш - O(1) в СРЕДНЕМ, но не в худшем; дерево - O(log n) ГАРАНТИРОВАННО. Где важен худший случай или предсказуемая задержка - берут дерево.

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

m = степень двойки на закономерных данных. mod 2^b = младшие биты; ключи с одинаковым хвостом свалятся в одни ячейки. Бери m простым.

Недетерминированная хеш-функция (зависит от времени, адреса объекта). Положишь по одному номеру, искать будешь по другому.

«Возьму таблицу с запасом - коллизий не будет». При α = 0.5 их сотни (парадокс дней рождения). Коллизии - фон, а не край.

Считать вероятность коллизии по совпадениям с ОДНИМ ключом. Надо по всем ПАРАМ - их квадратично много, оттого столкновения так часты.

Расширять таблицу на +const, а не удвоением. Рехешировки учащаются, вставка в среднем становится O(n).

Обещать O(1) на КАЖДУЮ операцию. Из-за рехеширования отдельная вставка бывает O(n).

Завёл массив под «маленький» диапазон, который не маленький. Номер телефона, время в миллисекундах, 32-битный адрес - [None] * 2**32 это 32 ГБ ссылок.

Проверь себя

Зачем нужна хеш-функция и какие у неё три свойства?

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

Почему коллизии неизбежны и при каком числе ключей становятся вероятными?

Что такое α и как оно влияет на время поиска?

Что делают при переполнении и почему это амортизированно O(1)?

Почему битовая шкала на миллион номеров меньше set из десяти тысяч и где проходит граница?