Модуль: Хеширование

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

В идеальном случае от хэш-функции мы хотим, чтобы выполнялись следующие свойства:
1) одинаковые объекты имели одинаковый хэш
2) если хэш объектов одинаковый, то сами объекты одинаковы

Первое обеспечить несложно, достаточно задать общий детерминированный алгоритм.
Но со вторым возникают проблемы. Как говорилось выше, хэш-функция сжимает объекты. Поэтому здесь работает принцип Дирихле - будут такие случаи, когда два разных объекта будут иметь одинаковый хэш. Такая ситуация называется коллизией.
Хэш-функции бывают "хорошие" и "плохие". "Хорошие" обеспечивают маленькую вероятность коллизии, но зачастую это нелегко доказать. Здесь эти доказательства также будут опускаться.

Полиномиальное хэширование:
Рассмотрим алгоритм, который хэширует последовательность (пронумерованный набор) чисел. Строки также попадают под это определение, достаточно просто рассматривать символ как его ASCII-код (в программном коде ничего не меняется, т.к. символы итак хранятся как числа).
Для того, чтобы посчитать хэш последовательности S длины n рассмотрим следующую конструкцию:

p^{n *} S₀ + p^n-1 * S₁ + ... + p * S_n-1 + S_n

где p - формальная переменная.
То есть мы сопоставили последовательности S некоторый полином (многочлен).

[Обратите внимание, что на других ресурсах в интернете вы можете увидеть другой многочлен, а именно S₀ + p * S₁ + ... + p^n-1 * S_n-1 + pⁿ * S_n . Это также правильный способ, но я рекомендую использовать формулу выше, так как это поможет избежать трудностей с хэшированием подстрок, о котором поговорим позже].

Теперь чтобы получить хэш от последовательности S, подставим в этот полином некоторое число p, которое называют основанием. При этом все вычисления будем производить по модулю числа mod (то есть от каждой арифметической операции будем брать остаток от деления на число mod), которое называют модулем.

Параметр mod как раз задает то, на сколько наша хэш-функция сжимает последовательность. Чем больше mod - тем больше возможных значений хэшей. А чем больше возможных хэшей, тем меньше вероятность коллизии.
Предположим, что нам нужно работать с тысячью строк, от каждой из которых мы считаем хэш. Если возьмем модуль, меньший чем 1000, то по принципу Дирихле будет существовать пара строк, у которых будет одинаковый хэш. Таким образом, мы всегда хотим выбирать как можно больший модуль. Но при этом не забываем, что мы работаем с числами, т.к. это быстрее и удобнее.

Параметры p и mod выбираются заранее. Рекомендуется выбирать mod, равный простому числу. Учитывая то, что было сказано выше, хорошим выбором будет взять простое число в районе 10⁹, чтобы операции промежуточного перемножения помещались в long long. 
Основание же особо не ограничивается в выборе, но я бы рекомендовал брать не маленькое число.
[Во всех задачах на хэширование я выбирал для основания простое число в районе 10⁶ и простое число в районе 10⁹ для модуля, такое никогда не подводило, в том числе на реальных олимпиадах. Однако есть несколько блогов на codeforces, которые посвящены тому, как подбирать параметры для хэширования и как взламывать задачи, зная чужие параметры. При желании можете ознакомиться с ними]

Как это выглядит в реальном коде
Для подсчета хэша воспользуемся схемой Горнера.
[Если вы не знаете что это, то можете прочитать общую теорию, но она может быть трудноватой. Я рекомендую ознакомиться с двумя видео:
1) Пример подсчета на бумаге
2) Раскрытие формулы и псевдокод
]

long long calc_hash(const string& s, long long p, long long mod) {
	long long h = 0;
	for (int i = 0; i < s.size(); i++) {
		h = (h * p + (long long)s[i]) % mod;
	}
	return h;
}

Здесь представлен вариант вычисления хэша от строки. Для массивов чисел все выполняется аналогично.

Также есть способ снизить вероятность коллизии. Для этого просто нужно хэшировать последовательность еще по одной паре параметров. То есть для одной последовательности нужно будет посчитать хэш для параметров (p₁, mod₁) и для параметров (p₂, mod₂). В результате вы получите пару хэшей (h₁, h₂).
В этом случае будет удобно все хранить в парах: основание (p₁, p₂), модуль (mod₁, mod₂) и результатом хэше будет (h₁, h₂). Рекомендуется заранее переопределить необходимые операторы у пар и тогда можно будет писать код без копипасты на first и second, как будто оперируя числами.

Однако учитывайте накладные расходы на использование пар и то, что теперь вы делаете в два раза больше операций.

Что с этим делать?
Основное назначение хэшей в олимпиадном программировании - быстрая проверка на равенство больших объектов.
Наивное сравнение массивов и строк происходит за время, пропорциональное их размеру.

Рассмотрим следующую задачу: у вас есть набор из m строк, каждая из которых длины n. Вам дано q запросов, в каждом из которых вас просят сказать равны ли две какие то строки из набора.
Предположим, что m = 1000, n = 1000, q = 1000000.
Тогда наивное решение будет работать за О(q*n) ~= 10⁹.  Можно предпосчитать ответ для каждой пары строк и тогда можно будет моментально отвечать на запрос, но это работает за O(m²*n + q) ~= 10⁹, что тоже долго.
Воспользуемся хэшированием - захэшируем каждую строку и для каждого запроса будем сравнивать хэши вместо самих строк. Это работает за O(m*n + q) ~= 10⁶, что уже вполне быстро.

Здесь мы рассчитываем на второе свойство, которое рассматривалось в самом начале. С большой вероятностью при одинаковых хэшах мы будем иметь дело с одинаковыми объектами, поэтому здесь мы выбираем стратегию "веры" (в самом коде всегда будем рассчитывать на то, что второе свойство выполняется). Однако все же стоит понимать, что вам может не повезти [с двойным хэшированием у меня никогда такого не было, с обычным, кажется, тоже, но это не точно].