Коллизии неизбежны: Дирихле и парадокс дней рождения

Если ты понимаешь, почему при n > m коллизия гарантирована (Дирихле) и почему уже при ≈√m ключах она вероятна (парадокс дней рождения), листай до «Теперь сам».

Как думаешь, можно ли подобрать хеш-функцию без коллизий

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

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

Комната, где собрались люди, и ты споришь, найдутся ли двое с одним днём рождения. Кажется, что для этого нужно человек 200 - ведь дней в году 365. Но нет: достаточно 23 человек, и шансы уже выше 50%. Почему так мало? Потому что важны не совпадения с ТОБОЙ, а совпадения МЕЖДУ ЛЮБОЙ парой - а пар в группе из 23 человек целых 253. Хеш-таблица - та же комната: «дни рождения» - это номера ячеек, «люди» - ключи. Совпадений между парами ключей набирается пугающе быстро, и первая коллизия случается куда раньше, чем таблица заполнится.

Механизм: два уровня неизбежности

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

Уровень 2 - парадокс дней рождения (вероятно уже при ≈ √m). Задолго до n = m коллизии становятся ВЕРОЯТНЫ. Прикинем вероятность, что при вбрасывании n ключей в m ячеек все попадут в РАЗНЫЕ. Пар ключей примерно n²/2, каждая пара сталкивается с вероятностью 1/m, поэтому ожидаемое число коллизий ≈ n²/(2m). Оно достигает единицы, когда n ≈ √(2m) - то есть коллизия становится ожидаемой уже при числе ключей порядка КОРНЯ из числа ячеек, а не самого числа ячеек.

Правило

Коллизии (h(k₁) = h(k₂) при k₁ ≠ k₂) НЕИЗБЕЖНЫ. При n > m коллизия гарантирована любой хеш-функцией - принцип Дирихле (предметов больше, чем ящиков). Но вероятной коллизия становится куда раньше: ожидаемое число коллизий ≈ n²/(2m) достигает единицы уже при n ≈ √(2m) (то есть порядка √m) - парадокс дней рождения. Поэтому хеш-таблица обязана иметь механизм РАЗРЕШЕНИЯ коллизий (следующая глава): они не аварийный случай, а норма работы.

Разбор: откуда берётся √m в парадоксе дней рождения

Разберём, почему именно КОРЕНЬ. Наивно кажется, что коллизия появится, когда ключей станет сравнимо с числом ячеек m. Но считать надо не ключи, а ПАРЫ ключей - ведь сталкиваются пары. Из n ключей пар примерно n·(n−1)/2 ≈ n²/2. Каждая конкретная пара при равномерной функции попадает в одну ячейку с вероятностью 1/m. Ожидаемое число столкнувшихся пар - это число пар на вероятность одной: (n²/2)·(1/m) = n²/(2m). Приравняем к 1 (в среднем одна коллизия): n² ≈ 2m, откуда n ≈ √(2m). Вот и корень: квадрат в числе пар «съедает» половину показателя. Для дней рождения m = 365, √(2·365) ≈ 27 - и правда, около двух- трёх десятков человек хватает. Смысл для хеша: даже полупустая таблица уже полна коллизий, и рассчитывать «пока ячеек больше ключей - столкновений нет» - грубая ошибка.

Разбор: почему это не вина хеш-функции

Легко подумать, что коллизии - признак ПЛОХОЙ хеш-функции, и хорошая их избежит. Это не так, и различать тут важно. Идеально РАВНОМЕРНАЯ функция даёт МИНИМУМ коллизий - но не ноль: парадокс дней рождения посчитан как раз для идеально случайного разбрасывания, и он всё равно даёт коллизии при ≈ √m ключах. То есть даже совершенная функция сталкивает ключи - просто реже, чем плохая. Плохая функция добавляет к неизбежным коллизиям ещё и лишние (перекос в пару ячеек), а хорошая держит их на теоретическом минимуме. Поэтому цель хорошей хеш-функции - не «убрать коллизии» (невозможно), а «не создавать ЛИШНИХ сверх неизбежных». А раз коллизии всё равно будут, таблице нужен способ с ними жить - и это отдельная инженерная задача, а не следствие кривой функции.

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

Первая ошибка - строить хеш-таблицу без разрешения коллизий, в надежде «подберу функцию без столкновений»: такой функции для n > m не существует (Дирихле), а на практике столкновения начинаются уже при √m ключах. Второе - брать таблицу «с запасом, ячеек вдвое больше ключей» и думать, что коллизий не будет: при n = m/2 ожидаемое число коллизий ≈ m/8 - их сотни в таблице на тысячу ячеек. Третье - при подсчёте вероятности коллизии считать совпадения с ОДНИМ ключом, а не между всеми парами: занизишь оценку в разы и удивишься, что столкновения так часты. Четвёртое - винить хеш-функцию за коллизии как таковые: минимум коллизий неустраним, вопрос лишь в лишних.

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

Понимание неизбежности коллизий - основа грамотной работы с хеш-таблицами. Оно объясняет, почему любая реальная реализация словаря ВСЕГДА содержит код разрешения коллизий (цепочки или пробирование - следующая глава): без него структура просто неверна. Парадокс дней рождения выходит далеко за хеш-таблицы: на нём стоят атаки на хеш-функции в криптографии (найти коллизию в n-битном хеше можно за ≈ 2^(n/2) попыток, а не 2^n - поэтому для защиты берут вдвое длиннее), оценки уникальности идентификаторов (сколько UUID можно выдать, пока не столкнутся два), дедупликация. А практический вывод для хеш-таблицы прост: держи заполненность (следующий урок про α) в узде и не жди, что «пустая таблица - без коллизий». Коллизия - не сбой, а фон, на котором работает весь механизм.

Теперь сам

В таблице m = 100 ячеек. Наивно кажется, что коллизии начнутся около n = 100 ключей. При каком числе ключей коллизия станет ОЖИДАЕМОЙ на самом деле, и почему это так рано?