Хеширование

Хеш - это какая-то функция, сопоставляющая объектам какого-то множества числовые значения из ограниченного промежутка. "Хорошая" хеш-функция: Быстро считается - за линейное от размера объекта время; Имеет не очень большие значения - влезающие в 64 бита; "Детерминировано-случайная" - если хеш может принимать $n$ различных значений, то вероятность того, что хеши от двух случайных объектов совпадут, равна примерно $\frac{1}{n}$.

ru.algorithmica.org

Минутка размышлений

Смысл познать общие принципы, а не зазубрить с точностью до индекса.

Человек не обязан знать все идеально

Еще раз определение

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

«Хорошая» хеш-функция:

• Быстро считается — за линейное от размера объекта время;
• Имеет не очень большие значения — влезающие в 64 бита;
• «Детерминировано-случайная» — если хеш может принимать $n$ различных значений, то вероятность того, что хеши от двух случайных объектов совпадут, равна примерно$\frac{1}{n}$

Обычно хеш-функция не является взаимно однозначной: одному хешу может соответствовать много объектов. Такие функции называют сюръективными.

Для некоторых задач удобнее работать с хешами, чем с самими объектами. Пусть даны $n$строк длины $m$, и нас просят $q$ раз проверять произвольные две на равенство. Вместо наивной проверки за O($q \cdot n \cdot m$), мы можем посчитать хеши всех строк, сохранить, и во время ответа на запрос сравнивать два числа, а не две строки.

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

В этом разделе мы в основном сфокусируемся на строках.

Полиномиальное хеширование

Будем считать, что строка — это последовательность чисел от 1 до $m$ (размер алфавита). В C/C++ тип charэто на самом деле тоже число (8-битное), поэтому можно вычитать из символов минимальный код и кастовать в число:

int x = (int) (c - 'a' + 1);

Определим прямой полиномиальный хеш строки как значение следующего многочлена:

$h_f​=(s_0​+s_1​k+s_2​k^2+…+s_n​k^n)\mod p$

Здесь $k$ — произвольное число больше размера алфавита, а $p$ — достаточно большой модуль (вообще говоря, не обязательно простой).

Его можно посчитать за линейное время, поддерживая переменную, равную $k$ в нужной степени:

const int k = 31, mod = 1e9+7;

string s = "abacabadaba";
long long h = 0, m = 1;

for (char c : s) {
    int x = (int) (c - 'a' + 1);
    h = (h + m * x) % mod;
    m = (m * k) % mod;
}

Можем ещё определить обратный полиномиальный хеш:

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

Его преимущество в том, что можно писать на одну строчку кода меньше:

long long h = 0;
for (char c : s) {
    int x = (int) (c - 'a' + 1);
    h = (h * k + x) % mod;
}

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

Зачем это нужно?

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

Например, если нужно посчитать хеш от конкатенации строк $a$ и $b$ (строку $b$ приписали в конец строки $a$), то можно просто хеш $b$ домножить на $k^{|a|}$ и сложить с хешом $a$:

$h(ab) = h(a) + k^{|a|} \cdot h(b)$

Удалить префикс строки можно так:

$h(b) = \frac{h(ab) - h(a)}{k^{|a|}}$

А суффикс — ещё проще:

$h(a) = h(ab) - k^{|a|} \cdot h(b)$

В задачах нам часто понадобится домножать $k$ в какой-то степени, поэтому имеет смысл предподсчитать все нужные степени и сохранить в массиве:

const int maxn = 1e5+5;

int p[maxn];
p[0] = 1;

for (int i = 1; i < maxn; i++)
    p[i] = (1ll * p[i-1] * k) % mod; // аккуратно с переполнением

Как это использовать в реальных задачах? Пусть нам надо отвечать на запросы проверки на равенство произвольных подстрок одной большой строки. Подсчитаем значение хеш-функции для каждого префикса:

int h[maxn];
h[0] = 0; // h[k] -- хеш префикса длины k
// будем считать, что s это уже последовательность int-ов
for (int i = 0; i < n; i++) 
    h[i+1] = (h[i] + p[i] * s[i]) % mod;

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

$h(s[l:r]) = \frac{h_r-h_l}{k^l}$

Деление по модулю возможно делать только при некоторых k и mod (а именно — при взаимно простых). В любом случае, писать его долго, и мы это делать не хотим.

Для нашей задачи не важно получать именно полиномиальный хеш — главное, чтобы наша функция возвращала одинаковый многочлен от одинаковых подстрок. Вместо приведения к нулевой степени приведём многочлен к какой-нибудь достаточно большой — например, к $n$-ной.

$\hat{h}(s[l:r]) = k^{n-l} (h_r-h_l)$

Так проще — теперь нужно домножать, а не делить:

int hash_substring(int l, int r) {
    return (h[r+1] - h[l]) * p[n-l] % mod;
}

Теперь мы можем просто вызывать эту функцию от двух отрезков и сравнивать числовое значение, отвечая на запрос за $O(1)$.

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

Лайфхак. Если взять обратный полиномиальный хеш короткой строки на небольшом алфавите с $k=10$, то числовое значение хеша строки будет наглядно соотноситься с самой строкой:

$h(abacaba)=1213121$

Этим удобно пользоваться при дебаге.

Примеры задач

Количество разных подстрок. Посчитаем хеши от всех подстрок за $O(n^2)$ и добавим их все в std::set. Чтобы получить ответ, просто вызовем set.size().

Поиск подстроки в строке. Можно посчитать хеши от шаблона (строки, которую ищем) и пройтись «окном» размера шаблона по тексту, поддерживая хеш текущей подстроки. Если хеш какой-то из этих подстрок совпал с хешом шаблона, то мы нашли нужную подстроку. Это называется алгоритмом Рабина-Карпа.

Сравнение подстрок на больше-меньше, а не только на равенство. У любых двух строк есть какой-то общий префикс (возможно, пустой). Сделаем бинпоиск по его длине, а дальше в обеих подстроках возьмём идущий за ним символ и сравним. Это будет работать за $O(\log n)$.

Палиндромность подстроки. Можно посчитать два массива — обратные хеши и прямые. Проверка на палиндром будет заключаться в сравнении значений hash_substring() на первом массиве и на втором.

Количество палиндромов. Можно перебрать центр палиндрома, а для каждого центра — бинпоиском его размер. Проверять подстроку на палиндромность мы уже умеем. Как и всегда в задачах на палиндромы, случаи четных и нечетных палиндромов нужно обрабатывать отдельно. Это будет работать за $O(n \log n)$, хотя это можно решить и линейно.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проверки на изоморфизм