Что такое хеш-функция

Хеш-функция сопоставляет объекту — строке, множеству, дереву — одно целое неотрицательное число.

Смысл прост: сравнивать числа быстро, а объекты — долго. Если равным объектам всегда соответствуют равные числа, то сравнение чисел заменяет сравнение объектов.

Обратное, к сожалению, неверно: разным объектам иногда достаётся одно и то же число. Это называется коллизией, и вся практика хеширования — про то, как сделать коллизии достаточно редкими.

Зачем

Мотивирующая задача. Дан массив из $n$ строк суммарной длины $10^6$ и $q$ запросов вида «равны ли строки $i$ и $j$».

Прямое сравнение стоит длину строки, и при $q = 10^5$ решение не проходит. С хешами: один раз считаем хеш каждой строки за линию, дальше каждый запрос — сравнение двух чисел.

Тот же приём работает для подстрок, множеств, поддеревьев — везде, где сравнение дорого, а объектов много.

Четыре требования

1. Значения распределены равномерно. Если половина строк получает хеш $0$, то две случайные строки совпадут по хешу с вероятностью около $25\%$. Это негодно.

2. Диапазон ограничен. Можно сопоставить каждой строке уникальное число, перечислив все строки по порядку, — но для строки длины $1000$ такое число само окажется размером со строку. Хеш должен помещаться в 32 или 64 бита, иначе сравнивать его будет не быстрее, чем сами объекты.

3. Считается быстро. Хеш строки должен вычисляться за линию от её длины, иначе предподсчёт съест выигрыш.

4. Неустойчива к малым изменениям. Похожие объекты должны получать непохожие хеши. Если строки из ста тысяч букв a с одной буквой b на разных местах дают близкие хеши, задача с таким тестом провалится.

Четвёртое требование — то, чем хеш-функция отличается от «какой-нибудь функции». Длина строки удовлетворяет первым трём и совершенно бесполезна как хеш.

Плохие примеры

Длина строки. Все строки одной длины сталкиваются. Контрпример строится мгновенно.

Сумма кодов символов. Любая перестановка символов даёт тот же хеш. Строки abc и cba неразличимы.

Первые несколько символов. Строки с общим префиксом сталкиваются.

Общий признак негодности: контрпример строится руками, без перебора. Если для вашей хеш-функции можно за минуту придумать две разные строки с одинаковым хешем, она не годится.

Хорошая хеш-функция — та, для которой контрпример приходится искать перебором, и перебор этот долгий.

Вероятность коллизии

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

При $m \approx 10^9$ это одна миллиардная — на $10^5$ сравнений вероятность хоть одной ошибки около $10^{-4}$. Приемлемо.

Но эта оценка обманчива: она верна для фиксированной пары. Когда сравнений много и они между всеми парами, картина меняется резко — об этом отдельная статья.

Хеш — не доказательство

Важная оговорка. Совпадение хешей не доказывает равенства объектов. Решение на хешах верно лишь с некоторой вероятностью.

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

Если задача решается точным алгоритмом за ту же асимптотику, обычно лучше взять его.