Хеширование


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

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

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

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

pn * S0 + pn-1 * S1 + ... + p * Sn-1 + Sn

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

[Обратите внимание, что на других ресурсах в интернете вы можете увидеть другой многочлен, а именно S0 + p * S1 + ... + pn-1 * Sn-1 + pn * Sn . Это также правильный способ, но я рекомендую использовать формулу выше, так как это поможет избежать трудностей с хэшированием подстрок, о котором поговорим позже].

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

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

Параметры p и mod выбираются заранее. Рекомендуется выбирать mod, равный простому числу. Учитывая то, что было сказано выше, хорошим выбором будет взять простое число в районе 109, чтобы операции промежуточного перемножения помещались в long long. 
Основание же особо не ограничивается в выборе, но я бы рекомендовал брать не маленькое число.
[Во всех задачах на хэширование я выбирал для основания простое число в районе 106 и простое число в районе 109 для модуля, такое никогда не подводило, в том числе на реальных олимпиадах. Однако есть несколько блогов на 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;
}
Здесь представлен вариант вычисления хэша от строки. Для массивов чисел все выполняется аналогично.

Также есть способ снизить вероятность коллизии. Для этого просто нужно хэшировать последовательность еще по одной паре параметров. То есть для одной последовательности нужно будет посчитать хэш для параметров (p1, mod1) и для параметров (p2, mod2). В результате вы получите пару хэшей (h1, h2).
В этом случае будет удобно все хранить в парах: основание (p1, p2), модуль (mod1, mod2) и результатом хэше будет (h1, h2). Рекомендуется заранее переопределить необходимые операторы у пар и тогда можно будет писать код без копипасты на first и second, как будто оперируя числами.

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

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

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

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

Задача для тренировки:

Хэш двойной строки

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

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

Если мы хотим посчитать хэш подотрезка [l;r], то нужно взять хэш на префиксе r и вычесть хэш на префиксе l-1, домноженный на p в степени r-l+1. Почему это так, становится понятным, если расписать значения на префиксах и посмотреть, что происходит. Надеюсь у вас получится, глядя на эту картинку.



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

Тут есть два момента, которые стоит уточнить:
1) Чтобы быстро домножать на p в степени r-l+1, необходимо заранее предпосчитать все возможные степени p по модулю mod.
2) Необходимо помнить, что все вычисления мы производим по модулю mod, а поэтому может получиться так, что после вычитания префиксных хэшей мы получим отрицательное число. Чтобы этого избежать можно всегда прибавлять mod перед вычитанием. Также не забываем после домножений и всех сложений также брать значение по модулю.

В коде это выглядит так:
  
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1000003;

// основание и модуль хэширования
ll p, mod;

// префиксный хэш и степени p
ll h[MAXN], pows[MAXN];

// подсчет хэша подотрезка [l;r]
ll get_segment_hash(int l, int r) {
	return (h[r] + mod - h[l - 1] * pows[r - l + 1] % mod) % mod;
}

int main()
{
	// каким то способом получаем p и mod
	
	// предпосчитываем степени p
	pows[0] = 1;
	for (int i = 0; i < MAXN; i++)
	    pows[i] = (pows[i - 1] * p) % mod;
	    
	// 
	// основное решение задачи
	//

	return 0;
}

Задача для тренировки:

Подстроки в строке

Если у нас есть хэш строки A равный hA и хэш строки В равный hB, то мы можем быстро посчитать хэш строки АВ:
hAB = hA * p|B| + hB   <- считая все по модулю mod
где |B| - длина строки В.

Задача для тренировки:

Гекльберри Финн и две строки

Помимо последовательностей можно также хэшировать множества. То есть наборы объектов без порядка на них. Считается он по следующей формуле:
hash(A) = \(\sum_{a \in A} p^{ord(a)}\)   <- считая все по модулю mod
где ord - функция, которая сопоставляет объекту множества его абсолютный порядковый номер среди всех возможных объектов (например, если объекты - натуральные числа, то ord(x) = x, а если строчные латинские буквы, то ord('a') = 1, ord('b') = 2 и т.д.)

То есть каждому объекту мы сопоставляем величину равную основанию в степени номера этого объекта и суммируем все эти величины для того, чтобы получить хэш всего множества. Как понятно из формулы, хэш легко пересчитывается, если в множество добавляется элемент или удаляется из него (просто добавляем или вычитаем необходимую величину). Такая же логика,  если добавляются или удаляются не одиночные элементы, а другие множества (просто добавляем/вычитаем их хэш).

Как вы уже могли понять, одиночные элементы рассматриваются как множества размера 1, для которых мы умеем считать хэш. А более крупные множества просто являются объединением таким единичных множеств, где объединяя множества, мы складываем их хэши.

На самом деле это все тот же полиномиальный хэш, но раньше коэффициентом при pm у нас было значение элемента последовательности под номером n - m - 1 (где n - длина последовательности), а теперь это количество элементов в множестве, у которых абсолютный порядковый номер равен m.

В таком хэшировании необходимо брать достаточно большое основание (большее, чем максимальный размер множества), либо использовать двойное хэширование, чтобы избежать ситуаций, когда множество из p объектов с абсолютным порядковым номером m имеюют тот же хэш, что и множество с одним объектом с абсолютным порядковым номером m+1.
 

Задача для тренировки:

Культурный контакт

Существует также несколько способов эффективно хэшировать корневые деревья. 
Один из таких способов устроен следующим образом:
Обрабатываем вершины рекурсивно, в порядке обхода в глубину. Будем считать, что хэш единичной вершины равен p. Для вершин с детьми, мы сперва запускаем алгоритм для них, затем через детей будем считать хэш текущего поддерева. Для этого рассмотрим хэши поддеревьев детей как последовательность чисел и посчитаем хэш от этой последовательности. Это и будет хэшом текущего поддерева.
Если нам не важен порядок на детях, то до подсчета хэша, отсортируем последовательность хэшей от поддеревьев детей и затем посчитаем хэш от отсортированной последовательности.

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

Для некорневых деревьев все происходит аналогичным образом, но в качестве корня необходимо взять центроид. Или рассматривать пару хэшей, если центроида два.

Задача для тренировки:

Бункеры