Коллизии хешей - Алгоритмика
Коллизии хешей

Коллизии хешей

автор Сергей Слотин
опубликовано 2019

У алгоритмов, использующих хеширование, есть один неприятный недостаток: недетерминированность. Если мы сгенерируем бесконечное количество примеров, то когда-нибудь нам не повезет, и программа отработает неправильно. На CodeForces даже иногда случаются взломы решений, использующих хеширование — можно в оффлайне сгенерировать тест против конкретного решения. Есть даже гайды про то, как это делать.

Событие, когда два хеша совпали, а не должны, называется коллизией. Пусть мы решаем задачу определения количества различных подстрок — мы добавляем в set O(n2)O(n^2) различных случайных значений в промежутке [0,m)[0, m). Понятно, что если произойдет коллизия, то мы какую-то строку не учтем и получим WA. Насколько большим следует делать mm, чтобы не бояться такого?

#Выбор констант

Практическое правило: если вам нужно хранить nn различных хешей, то безопасный модуль — это число порядка 10n210 \cdot n^2. Обоснование — см. парадокс дней рождений.

Не всегда такой модуль можно выбрать один — если он будет слишком большой, то при умножении будут происходить переполнения. Вместо этого можно брать два или даже три модуля и считать много хешей параллельно.

Можно также брать «модуль» 2642^{64}. У него есть несколько преимуществ:

  • Он большой — второй модуль точно не понадобится.
  • С ним ни о каких переполнениях заботиться не нужно — если все хранить в unsigned long long, процессор сам автоматически сделает эти взятия остатков при переполнении.
  • С ним хеширование будет значительно быстрее — раз переполнение происходит на уровне процессора, можно не выполнять долгую операцию %.

Всё с этим модулем было прекрасно, пока не придумали тест против него. Однако его добавляют далеко не на все контесты — имейте это в виду.

В выборе же kk ограничения не такие серьезные:

  • Она должна быть чуть больше размера словаря — иначе можно изменить две соседние буквы и получить коллизию.
  • Она должна быть взаимно проста с модулем — иначе в какой-то момент всё может занулиться.

Главное — чтобы значения kk и модуля не знал человек, который генерирует тесты.

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

В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения хотя бы у двух людей превышает 50%.

Более общее утверждение: в мультимножество нужно добавить Θ(n)\Theta(\sqrt{n}) случайных чисел от 1 до n, чтобы какие-то два совпали.

Первое доказательство (для любителей матана). Пусть f(n,d)f(n, d) это вероятность того, что в группе из nn человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от 11 до dd.

f(n,d)=(11d)×(12d)×...×(1n1d) f(n, d) = (1-\frac{1}{d}) \times (1-\frac{2}{d}) \times ... \times (1-\frac{n-1}{d}) Попытаемся оценить ff: ex=1+x+x22!+(ряд Тейлора для экспоненты)1+x(аппроксимация для x1)end1nd(подставим nd1)f(n,d)e1d×e2d××en1d=en(n1)2den22d \begin{aligned} e^x & = 1 + x + \frac{x^2}{2!} + \ldots & \text{(ряд Тейлора для экспоненты)} \\ & \simeq 1 + x & \text{(аппроксимация для $|x| \ll 1$)} \\ e^{-\frac{n}{d}} & \simeq 1 - \frac{n}{d} & \text{(подставим $\frac{n}{d} \ll 1$)} \\ f(n, d) & \simeq e^{-\frac{1}{d}} \times e^{-\frac{2}{d}} \times \ldots \times e^{-\frac{n-1}{d}} & \\ & = e^{-\frac{n(n-1)}{2d}} & \\ & \simeq e^{-\frac{n^2}{2d}} & \\ \end{aligned}

Из последнего выражения более-менее понятно, что вероятность 12\frac{1}{2} достигается при ndn \approx \sqrt{d} и в этой точке изменяется очень быстро.

Второе доказательство (для любителей теорвера). Введем n(n1)2\frac{n(n-1)}{2} индикаторов — по одному для каждой пары людей (i,j)(i, j) — каждый будет равен единице, если дни рождения совпали. Ожидание и вероятность каждого индикатора равна 1d\frac{1}{d}.

Обозначим за XX число совпавших дней рождений. Его ожидание равно сумме ожиданий этих индикаторов, то есть n(n1)21d\frac{n (n-1)}{2} \cdot \frac{1}{d}.

Отсюда понятно, что если d=Θ(n2)d = \Theta(n^2), то ожидание равно константе, а если dd асимптотически больше или меньше, то XX стремится нулю или бесконечности соответственно.

Примечание: формально, из этого явно не следует, что вероятности тоже стремятся к 0 и 1.

#Бонус: «мета-задача»

Дана произвольная строка, по которой известным только авторам задачи способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток отослать решение. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердиктов всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA.

«Решите» задачу.