Хэши

К разделу

1. Зачем вообще нужны хэш-функции

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

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

Хэш-функция — это функция, сопоставляющая объектам из некоторого множества числовые значения из ограниченного диапазона. Формально: $h:X\to [0,M)$.

Из этого определения сразу следует важное наблюдение: если $|X|>|M|$, то по принципу Дирихле обязательно найдутся два разных объекта с одинаковым хэшем — это называется коллизия. Коллизий избежать нельзя, но можно подобрать такую хэш-функцию, которая минимизирует их вероятность.

Где хэш-функции применяются в целом

• Криптография. Пароль пользователя не хранится на сервере в открытом виде — хранится его хэш. При входе сервер хэширует введённый пароль и сравнивает с сохранённым значением. Восстановить исходный пароль по хэшу должно быть вычислительно тяжело
• Кэширование. Хэш-таблицы (типа unordered_map и dict) используют хэш ключа, чтобы за O(1) находить нужную ячейку, вместо линейного перебора

Где хэши применяются в алгоритмических задачах

Здесь у хэшей задача попроще:

• подсчёт количества различных подстрок строки;
• поиск вхождения одной строки в другую;
• проверка подстроки на палиндромность.

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

---

2. Модульная арифметика

Прежде чем переходить к самому хэшированию, вспомним модульную арифметику — именно она не даёт значению хэша расти неограниченно и переполнять числа

Деление с остатком

Для любого целого a и натурального m деление с остатком всегда возможно, причём единственным образом:

$$a=q\cdot m+r,0⩽r<m$$

Число r называется остатком от деления a на m (обозначается $amodm$). В математике остаток всегда неотрицателен.

Пример: $7=1\cdot 5+2\Rightarrow 7mod5=2$; $-7=-2\cdot 5+3\Rightarrow -7mod5=3$.

Остаток в C++

Оператор % в C++ ведёт себя иначе: результат сохраняет знак делимого, а не всегда неотрицателен, как в математике:

int r = -7 % 10; // r == -7, а не 3, как в математике

выражение	математика	C++
7 % 5	2	2
-7 % 5	3	-2
7 % -5	2	2
-7 % -5	3	-2

Так как в задачах нам, как и в математике, нужен неотрицательный остаток, его приходится нормализовать вручную — прибавлением m, если результат оказался отрицательным:

long long norm(long long a, long long m) {
    return ((a % m) + m) % m;
}

Сравнимость чисел по модулю

Определение. Целые числа a и b называются сравнимыми по модулю m ($a\equiv b(\mathrm{mod}m)$), если у них одинаковый остаток от деления на m

Определение. Целые числа a и b называются сравнимыми по модулю m ($a\equiv b(\mathrm{mod}m)$), если разность $a-b$ делится на $m$ нацело

Эти определения равносильны

Арифметика по модулю

Хэш строки — это, по сути, огромное число, которое уже после нескольких десятков символов переполнило бы даже long long. Поэтому модуль берут не один раз в конце вычисления, а на каждом шаге:

• Сложение: $(a+b)modm=((amodm)+(bmodm))modm$
• Вычитание: $(a-b)modm=((amodm)-(bmodm))modm$
• Умножение: $(a\cdot b)modm=((amodm)\cdot (bmodm))modm$

Именно поэтому в коде массива степеней и префиксных хэшей (см. раздел 4) операция % p стоит внутри каждой итерации цикла, а не один раз после него — так промежуточные суммы и произведения никогда не выходят за пределы [0, p) и не переполняются.

Пример. Произведение n чисел по модулю m, с остатком на каждом шаге, а не в конце:

long long ans = 1;
for (int i = 0; i < n; i++) {
    ans = (ans * norm(a[i], m)) % m;
}

---

3. Полиномиальное хэширование строк

Пусть дана строка $S$ длины n+1 (индексы 0…n), символы которой заранее занумерованы числами от 1 до m

Идея полиномиального хэша — рассматривать строку как число, записанное в системе счисления с основанием k, где цифрами служат коды символов:

• выбирается основание (база) k, обычно k > m, чтобы разным коротким комбинациям символов не сопоставлялось одно и то же значение из-за переполнения разряда;
• выбирается модуль p — обычно большое простое число (например, p = 10^9 + 7), чтобы значения хэша не росли неограниченно и укладывались в машинное слово.

Два способа прочитать строку как число

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

$$h_f=(s_0+s_1\cdot k+s_2\cdot k^2+\cdots +s_n\cdot k^n)(\mathrm{mod}p)$$

2. Обратный полиномиальный хэш — наоборот, первый символ строки получает наибольшую степень, как в привычной десятичной записи числа (это же вычисление удобно делать по схеме Горнера: hash = hash * k + s[i]):

$$h_b=(s_0\cdot k^n+s_1\cdot k^{n-1}+\cdots +s_n)(\mathrm{mod}p)$$

Оба варианта — это один и тот же набор символов, просто прочитанный в разные стороны относительно степеней k.

Пример на маленьких числах

Возьмём k = 31, p = 101 (в реальных задачах модуль должен быть гораздо больше, порядка ${10}^9$, чтобы сократить число коллизий) и строку "abc", где a = 1, b = 2, c = 3

$$h_f(\text{"abc"})=1+2\cdot 31+3\cdot {31}^2=1+62+2883=2946\equiv 17(\mathrm{mod}101)$$$$h_b(\text{"abc"})=1\cdot {31}^2+2\cdot 31+3=961+62+3=1026\equiv 16(\mathrm{mod}101)$$

Значения различны — и это ожидаемо, ведь "abc" не палиндром. А теперь то же самое для "aba" (a = 1, b = 2):

$$h_f(\text{"aba"})=1+2\cdot 31+1\cdot {31}^2=1024\equiv 14(\mathrm{mod}101)$$$$h_b(\text{"aba"})=1\cdot {31}^2+2\cdot 31+1=1024\equiv 14(\mathrm{mod}101)$$

Для палиндрома оба хэша совпали, ибо последовательность символов что слева-направо, что справо-налево - одинакова

---

4. Сравнение подстрок за O(1)

Пересчитывать хэш подстроки с нуля при каждом запросе — это O(n) на запрос, и общая сложность становится O(nq) для q запросов, что для больших строк слишком медленно. Нам надо научиться отвечать на запрос за O(1) после линейной предобработки.

Шаг 1. Массив степеней основания

Заранее считаем и сохраняем в массиве все нужные степени $k^0,k^1,k^2,\dots ,k^n(\mathrm{mod}p)$. Это делается один раз за O(n):

vector<long long> pw(n + 1);
pw[0] = 1;
for (int i = 1; i <= n; i++) {
    pw[i] = pw[i - 1] * k % p;
}

Шаг 2. Массив префиксных хэшей

Строим массив pref, где pref[i] — обратный (по схеме Горнера) полиномиальный хэш префикса строки от начала до символа s[i] включительно:

vector<long long> pref(n + 1);
pref[0] = s[0];
for (int i = 1; i <= n; i++) {
    pref[i] = (pref[i - 1] * k + s[i]) % p;
}

Шаг 3. Хэш произвольной подстроки [l, r] за O(1)

Кажется, что можно получить хэш только куска [l, r], вычитая из pref[r] вклад префикса [0, l-1]. Но напрямую вычитать нельзя: символы на позициях [l, r] в pref[r] стоят на своих изначальных степенях k, а символы [0, l-1] в pref[l-1] — на гораздо меньших степенях.

Чтобы их совместить, префикс [0, l-1] нужно сначала домножить на $k^{r-l+1}$ — это как дописать в конец числа ровно столько нулевых разрядов, сколько занимает кусок [l, r]:

$$\text{hash}(l,r)=({\text{pref}}_r-{\text{pref}}_{l-1}\cdot k^{r-l+1})(\mathrm{mod}p)$$

Проверим на примере. Строка "abcab" ($a=1,b=2,c=3,k=31,p=101$, индексы 0..4):

$$\text{pref}=[1,33,16,93,57]$$

Хотим хэш подстроки s[1..2] = "bc". По формуле:

$$\text{hash}(1,2)={\text{pref}}_2-{\text{pref}}_0\cdot k^2=16-1\cdot 961\equiv 16-52\equiv -36\equiv 65(\mathrm{mod}101)$$

Проверяем напрямую: $h_b(\text{"bc"})=2·31+3=65$. Совпало, значит формула действительно вычисляет хэш подстроки, как если бы мы посчитали его с нуля, но за O(1).

Важно

Хэш подтверждает вероятное равенство строк, а не гарантированное — теоретически возможен подбор строки, которая при заданном основании и модуле даст коллизию. Риск можно снизить так:

• возьмем модуль p порядка ${10}^9$ или больше — вероятность коллизии быстро падает с ростом модуля;
• используем два независимых хэша (разные пары (k, p)) и сравним строки только тогда, когда совпали обе пары — вероятность коллизии по обеим сразу перемножается и становится еще меньше

---

5. Решение типовых задач с помощью хэшей

5.1. Поиск подстроки в строке

Задача: найти вхождение образца P длины m в текст T длины n.

Подход: посчитать хэш образца P один раз, а затем скользящим окном длины m пройтись по тексту T, на каждом шаге за O(1) вычисляя хэш очередного окна по формуле из раздела 4 и сравнивая его с хэшем образца.

Сложность: O(n + m) — линейная предобработка плюс O(1) на каждое из O(n) положений окна

5.2. Количество различных подстрок

Задача: посчитать, сколько существует различных подстрок у строки (одинаковые по содержанию подстроки считаются один раз, даже если встречаются в разных местах).

Подход: для каждой длины подстроки (или сразу для всех $O(n^2)$ подстрок) вычислить хэш за O(1) и сложить все хэши в set. Так как одинаковые подстроки дают одинаковый хэш, а разные — почти всегда разный, размер множества после добавления всех хэшей и есть ответ.

Ответ: set.size().

Сложность: $O(n^2\log n)$ — $O(n^2)$ подстрок, на каждую O(1) на вычисление хэша и O(log n) на вставку в set.

5.3. Проверка подстроки на палиндромность

Идея: вспомним пример из раздела 3 — для палиндрома значения h_f и h_b совпадали. Разберёмся, почему:

Хэш h_f(l, r) читает подстроку слева направо, приписывая первому символу наименьшую степень k. Хэш h_b(l, r) читает ту же подстроку тоже слева направо, но приписывает первому символу наибольшую степень — а это в точности то же самое, что прочитать подстроку справа налево и приписать уже последнему символу наименьшую степень. Другими словами:

$$h_b(l,r)=h_f(\text{подстрока, записанная в обратном порядке})$$

Значит, равенство h_f(l, r) = h_b(l, r) означает (с точностью до вероятности коллизии), что подстрока совпадает сама с собой, прочитанная в обратном порядке — то есть является палиндромом.

Подход: сравнить прямой хэш подстроки [l, r] с обратным хэшем той же подстроки. Если они равны, подстрока с высокой вероятностью палиндром (для надёжности лучше использовать двойное хэширование, как описано выше).

Сложность: O(1) на проверку после O(n) предобработки обоих видов префиксных хэшей.

---

Итог

Хэширование строк превращает дорогие посимвольные сравнения подстрок в сравнение чисел за O(1), если заранее (за O(n)) построить массив степеней основания и один или два массива префиксных хэшей. Ключевые вещи, которые стоит помнить:

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