Хеши полезны, когда необходимо проверять на равенство какие-то объекты за малое время либо непонятно, как вообще сравнивать объекты. Зачастую это не является самым лучшим решением, иногда существуют специальные алгоритмы для данной задачи, иногда проблемы хеширования сильно проявляются.
Определим для последовательности \(a\) длиной \(n\) значение хеша, как \(hash_i = a_0 + a_1*p^{1} + a_2*p^{2}... + a_i*p^i\), где \(p\) - некая константа. Таким образом, мы просто домножаем соответствующий элемент на степень числа \(p\). Для \(p\) необходимо брать простое число. Так как степень \(p\) быстро растёт из этого следует проблема. В языках с длинной арифметикой число будет очень быстро расти и тормозить вашу программу. Чтобы этого избежать можно хранить хеш по модулю \(m\). В языках с фиксированной размерностью числа будет происходить переполнение. В этом случае ничего не делать - также хорошая тактика, по факту модулем будет являться \(2^{32}\) или \(2^{64}\). Почему так лучше не делать:
Достаточно давно нашли тест против хешей по модулю степени двойки: для этого можно использовать строки Морса-Туэ, которые задаются рекуррентно, из-за чего часто происходят коллизии.
Пост об этом.
#define ll long long
int a[n]; // Данный массив
ll hash = 0;
ll M = 1e9+7; // модуль
ll P = 7; // небольшое простое число
ll powP[n];
powP[0]=1;
for(int i = 1; i < n; i++)
powP[i] = powP[i-1] * P % M;
for(int i = 0; i < n; i++)
hash = (hash + powP[i] * a[i]) % M;
Разумеется, все наши рассуждения можно обобщать на строки. Заметим лишь, что у строки лучше использовать не просто числовой код s[i], а s[i]-'a'+1. Вычитаем, чтобы уменьшить значение, а один прибавляем, чтобы 'a' не был равен нулю (в противном случае все последовательности вида "aaa...aaa" будут хешироваться нулем).
Итак, мы можем сравнивать две строки за \(O(1)\). Давайте научимся сравнивать две подстроки.
Нам нужно узнать хеш двух подстрок. Пускай нужно вычислить хеш подстроки \(s\) с промежутка \([l;r]\).
У нас уже предподсчитан \(hash = a_0 + p*a_1 + ... p^l * a_l ... p^r * a_r\)
Давайте вычтем \(hash[r]-hash[l-1]\) и получим \(hash_{substr} = p^l * a_l + p^{l+1} * a_{l+1} ... p^r * a_r\).
Теперь нам надо привести к виду \(a_l + p * a_{l+1} ... + p^{r-l} * a_r\). Для этого разделим полученную разность на \(p^{l}\). Так как все вычисления происходят по модулю, нам нужно найти \((p^l)^{-1}\), т.е. обратное по модулю число (его можно предподсчитать). Но так как нам нужно привести хеши не просто к стандартному виду, а к одинаковому, можно наоборот домножить их на \(p^{n-1-l}\). Таким образом за \(O(1)\) можно сравнивать две любые подстроки массива.
Этим способом можно решать огромное количество задач на строки. Поиск всех палиндромов в строке, поиск вхождения одной строки в другую за \(O(n+m)\), построение суффиксного массива и т.п.
Пусть надо сравнить две строки лексикографически и мы уже предподсчитали их хеши. Давайте обратимся к определению:
Строка \(a\) лексикографически меньше \(b\), если \(a\) является префиксом \(b\) или первая несовпадающая буква \(a\) меньше буквы \(b\).
То есть надо проверить является ли \(a\) префиксом \(b\) (легко) и если нет, найти наибольший общий префикс и сравнить следующую букву.
Чтобы найти наибольший общий префикс воспользуемся бинпоиском.
Допустим нужно найти длину максимального палиндрома, центр которого задан \(i\). Заметим, что максимальный палиндром содержит палиндромы поменьше. Применим бинпоиск.
Основной проблемой хешей, конечно, являются коллизии - совпадение хешей двух разных последовательностей. Есть много методов борьбы с ними. Можно использовать два хеша: с разными основаниями или с двумя разными модулями.
Один из оптимальных вариантов писать двойные хеши
#define MOD 998244353 // простой модуль
const int k1=29, k2 = 31; // простые основания
#define MAXN 200200 // длина строк, которые надо хешировать
// пишем доп.функции для удобной работы с арифметикой остатков
int add(int a,int b) { a+=b; if(a>=MOD) a-=MOD; return a;}
int sub(int a,int b) { a-=b; if(a<0) a+=MOD; return a;}
int mul(int a,int b) { return 1ll*a*b%MOD; }
int binpow(int a,int n) { int r=1; while(n) { if(n%2) r=mul(r,a); a=mul(a,a); n/=2; } return r;}
#define pp pair < int, int >
// хеш будем хранить парой int'ов
// перегружаем операции над парами
pp operator+(pp a,pp b) { return pp(add(a.first,b.first), add(a.second,b.second) ); }
pp operator+(pp a,pp b) { return pp(sub(a.first,b.first), sub(a.second,b.second) ); }
pp operator*(pp a,pp b) { return pp(mul(a.first,b.first), mul(a.second,b.second) ); }
// прекалькаем степени и обратные степени k1 и k2
/// pw[i] = {k1^i, k2^i}
/// revpw[i] = {k1^(-i), k2^(-i)}
pp pw[MAXN], revpw[MAXN];
void init() {
pp kof = {k1,k2};
pp rev_kof = { binpow(k1,MOD-2), binpow(k2,MOD-2) }; // находим k1^(-1) и k2^(-1)
pw[0] = revpw[0] = {1,1};
for(int i = 1; i < MAXN; i++) {
pw[i] = pw[i-1] * kof;
revpw[i] = revpw[i-1] * rev_kof;
}
}
signed main() {
// данные строка и ее длина
int n;
string s;
vector hash(n+1); // префиксные хеши
for(int i = 0; i < n; i++) {
pp sym = { s[i]-'a'+1, s[i]-'a'+1 }; // номер символа
hash[i+1] = hash[i] + sym * pw[i];
}
auto get_hash = [&](int l, int r) {
return (hash[r+1] - hash[l]) * revpw[l];
};
// чтобы вычислить хеш подстроки [l;r] вызываем get_hash();
}
Пускай даны массивы, представляющие собой мультимножества. Необходимо эффективно сравнивать их.
Сопоставим одинаковым элементам из множеств уникальное случайное число. Тогда просуммируем для каждого множества его числа. Теперь такую сумму назовем хешом мультимножества. Одинаковые мультимножества имеют одинаковые хеши. Вероятность совпадения хеша разных мультимножеств мала. Кроме того, теперь можно обрабатывать запросы на удаление/добавление элементов в множествах и даже слияние множеств.
Сложение можно заменить на xor - результат будет не хуже и исчезнет операция взятия по модулю.
Все это можно обобщить для массива, и соответственно насчитав префиксные суммы отвечать на запросы на отрезке (или даже на пути дерева).