Коллизии и парадокс дней рождения

Вероятность того, что два конкретных различных объекта получат одинаковый хеш, — примерно $\frac{1}{m}$.

Отсюда легко сделать неверный вывод, что модуля $10^9$ хватит почти всегда. Это не так, и разница может стоить решения.

Парадокс дней рождения

Классический факт: в группе из 23 человек вероятность того, что у каких-то двоих совпадают дни рождения, уже больше $50\%$. При 365 возможных днях это кажется невероятным.

Объяснение в том, что сравниваются не человек с фиксированной датой, а все пары. При 23 людях пар $\binom{23}{2} = 253$, и каждая совпадает с вероятностью $\frac{1}{365}$.

Общее правило: среди $k$ случайных значений из $m$ возможных совпадение появляется, когда $k$ достигает примерно $\sqrt{m}$.

Что это значит для хешей

Задача: даётся $10^6$ строк, для каждой сказать, встречалась ли она раньше.

Естественное решение — складывать хеши в set. Но проверка «встречался ли хеш» — это неявное сравнение с каждой предыдущей строкой. Всего таких сравнений $\binom{10^6}{2} \approx 5 \cdot 10^{11}$.

При $m = 10^9$ ожидаемое число коллизий — около $5 \cdot 10^{11} / 10^9 = 500$. То есть коллизия не «маловероятна», а гарантирована, и решение выдаст неверный ответ.

По правилу корня: $\sqrt{10^9} \approx 31\,600$. Как только различных объектов становится сильно больше тридцати тысяч, модуля $10^9$ не хватает.

Как считать нужный модуль

Пусть $k$ — число объектов, которые попадают в общее хранилище (множество, словарь), и все они сравниваются друг с другом неявно.

$$\text{ожидаемое число коллизий} \approx \frac{k^2}{2m}$$

Хотим, чтобы это было сильно меньше единицы, значит $m$ должно быть заметно больше $k^2$.

сколько объектов	нужный модуль
$10^3$	$10^9$ с большим запасом
$10^5$	$10^{9}$ — на грани, лучше больше
$10^6$	$10^{18}$
$10^7$	$10^{18}$ на грани

Если же сравниваются только заданные пары — например, $q$ запросов «равны ли строки $i$ и $j$», — оценка другая: коллизий ожидается $\frac{q}{m}$, и при $q = 10^5$, $m = 10^9$ вероятность ошибки $10^{-4}$. Здесь модуля хватает.

Ключевой вопрос: сколько пар реально сравнивается. Ответ на него и определяет размер хеша.

Как получить большой модуль

Один хеш по модулю $10^{18}$. Требует __int128 для умножения. Работает, но медленнее.

Два хеша по модулям около $10^9$. Объекты считаются равными, только если совпали оба. Вероятность этого — произведение вероятностей, то есть примерно $10^{-18}$.

Второй вариант обычно предпочтительнее: все операции остаются в long long, а замедление — ровно вдвое.

struct DoubleHasher {
    Hasher h1, h2;   // разные p и разные mod
    pair<long long, long long> get(int l, int r) const {
        return {h1.get(l, r), h2.get(l, r)};
    }
};

Пара хешей кладётся в set<pair<long long, long long>> или упаковывается в одно 64-битное число как h1 * MOD2 + h2.

Осторожно с оптимизмом

Оценка $\frac{k^2}{2m}$ предполагает, что хеши распределены равномерно и независимо от входных данных. Если противник знает ваши $p$ и $m$, он может подобрать тест, где коллизия гарантирована при любом модуле, — и это делают.

Поэтому на площадках со взломами к оценке добавляют случайность: выбирают $p$ случайно во время выполнения.