Как называется совпадение хэш кодов двух различных строк

Хэширование в строковых задачах

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

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

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

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

Применения в реальной жизни

Чек-суммы. Простой и быстрый способ проверить целостность большого передаваемого файла — посчитать хэш-функцию на стороне отправителя и на стороне получателя и сравнить.
Хэш-таблица. Класс unordered_set из STL можно реализовать так: заведём $n$ изначально пустых односвязных списков. Возьмем какую-нибудь хэш-функцию $f$ с областью значений $[0, n)$ . При обработке .insert(x) мы будем добавлять элемент $x$ в $f(x)$ -тый список. При ответе на .find(x) мы будем проверять, лежит ли $x$ -тый элемент в $f(x)$ -том списке. Благодаря «равномерности» хэш-функции, после $k$ добавлений ожидаемое количество сравнений будет равно $\frac$ = $O(1)$ при правильном выборе $n$ .
Мемоизация. В динамическом программировании нам иногда надо работать с состояниями, которые непонятно как кодировать, чтобы «разгладить» в массив. Пример: шахматные позиции. В таком случае нужно писать динамику рекурсивно и хранить подсчитанные значения в хэш-таблице, а для идентификации состояния использовать его хэш.
Проверка на изоморфизм. Если нам нужно проверить, что какие-нибудь сложные структуры (например, деревья) совпадают, то мы можем придумать для них хэш-функцию и сравнивать их хэши аналогично примеру со строками.
Криптография. Правильнее и безопаснее хранить хэши паролей в базе данных вместо самих паролей — хэш-функцию нельзя однозначно восстановить.
Поиск в многомерных пространствах. Детерминированный поиск ближайшей точки среди $m$ точек в $n$ -мерном пространстве быстро не решается. Однако можно придумать хэш-функцию, присваивающую лежащим рядом элементам одинаковые хэши, и делать поиск только среди элементов с тем же хэшом, что у запроса.

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

Сегодня же мы остановимся на строках.

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

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

Будем считать, что строка — это последовательность чисел от $1$ до $m$ (размер алфавита). В C++ char это на самом деле тоже число, поэтому можно вычитать из символов минимальный код и кастовать в число: int x = (int) (c — ‘a’ + 1) .

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

\[ h_f = (s_0 + s_1 k + s_2 k^2 + \ldots + 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^ + \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$ :

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

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

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

 const int maxn = 1e5+5; int p[maxn]; p[0] = 1; for (int i = 1; i  maxn; i++) p[i] = (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;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хранение строк в декартовом дереве

Если для вас всё вышеперечисленное тривиально: можно делать много клёвых вещей, если «оборачивать» строки в декартово дерево. В вершине дерева можно хранить символ, а также хэш подстроки, соответствующей её поддереву. Чтобы поддерживать хэш, нужно просто добавить в upd() пересчёт хэша от конкатенации трёх строк — левого сына, своего собственного символа и правого сына.

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

Если нам не нужно обрабатывать запросы вставки и удаления символов, а, например, только изменения, то можно использовать и дерево отрезков вместо декартова.

Вероятность ошибки и почему это всё вообще работает

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первое доказательство (для любителей матана). Пусть $f(n, d)$ это вероятность того, что в группе из $n$ человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от $1$ до $d$ .

\[ f(n, d) = (1-\frac) \times (1-\frac) \times . \times (1-\frac) \]

Попытаемся оценить $f$ :

Из последнего выражения более-менее понятно, что вероятность $\frac$ достигается при $n \approx \sqrt$ и в этой точке изменяется очень быстро.

Второе доказательство (для любителей теорвера). Введем $\frac$ индикаторов — по одному для каждой пары людей $(i, j)$ — каждый будет равен единице, если дни рождения совпали. Ожидание и вероятность каждого индикатора равна $\frac$ .

Обозначим за $X$ число совпавших дней рождений. Его ожидание равно сумме ожиданий этих индикаторов, то есть $\frac \cdot \frac$ .

Отсюда понятно, что если $d = \Theta(n^2)$ , то ожидание равно константе, а если $d$ асимптотически больше или меньше, то $X$ стремится нулю или бесконечности соответственно.

Примечание: формально, из этого явно не следует, что вероятности тоже стремятся к 0 и 1.

Бонус: «мета-задача»

Дана произвольная строка, по которой известным только авторам задачи способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток отослать решение. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердиктов всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA.

Хеширование

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

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

Применения в реальной жизни

Чек-суммы. Простой и быстрый способ проверить целостность большого передаваемого файла — посчитать хэш-функцию на стороне отправителя и на стороне получателя и сравнить.
Хэш-таблица. Класс unordered_set из STL можно реализовать так: заведём $n$ изначально пустых односвязных списков. Возьмем какую-нибудь хэш-функцию $f$ с областью значений $[0, n)$. При обработке .insert(x) мы будем добавлять элемент $x$ в $f(x)$-тый список. При ответе на .find(x) мы будем проверять, лежит ли $x$-тый элемент в $f(x)$-том списке. Благодаря «равномерности» хэш-функции, после $k$ добавлений ожидаемое количество сравнений будет равно $\frac$ = $O(1)$ при правильном выборе $n$.
Мемоизация. В динамическом программировании нам иногда надо работать с состояниями, которые непонятно как кодировать, чтобы «разгладить» в массив. Пример: шахматные позиции. В таком случае нужно писать динамику рекурсивно и хранить подсчитанные значения в хэш-таблице, а для идентификации состояния использовать его хэш.
Проверка на изоморфизм. Если нам нужно проверить, что какие-нибудь сложные структуры (например, деревья) совпадают, то мы можем придумать для них хэш-функцию и сравнивать их хэши аналогично примеру со строками.
Криптография. Правильнее и безопаснее хранить хэши паролей в базе данных вместо самих паролей — хэш-функцию нельзя однозначно восстановить.
Поиск в многомерных пространствах. Детерминированный поиск ближайшей точки среди $m$ точек в $n$-мерном пространстве быстро не решается. Однако можно придумать хэш-функцию, присваивающую лежащим рядом элементам одинаковые хэши, и делать поиск только среди элементов с тем же хэшом, что у запроса.

Сегодня же мы остановимся на строках.

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

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

Будем считать, что строка — это последовательность чисел от $1$ до $m$ (размер алфавита). В C++ char это на самом деле тоже число, поэтому можно вычитать из символов минимальный код и кастовать в число: int x = (int) (c — ‘a’ + 1) .

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

$$ h_f = (s_0 + s_1 k + s_2 k^2 + \ldots + 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^ + \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$:

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

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

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

const int maxn = 1e5+5; int p[maxn]; p[0] = 1; for (int i = 1; i  maxn; i++) p[i] = (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;

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

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

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

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

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

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

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

Вероятность ошибки и почему это всё вообще работает

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

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

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

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

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

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

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

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

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

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

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

- Первое доказательство** (для любителей матана). Пусть $f(n, d)$ это вероятность того, что в группе из $n$ человек ни у кого не совпали дни рождения.
Будем считать, что дни рождения распределены независимо и равномерно в промежутке от $1$ до $d$.

$$ f(n, d) = \left(1-\frac\right) \times \left(1-\frac\right) \times\ . \ \times \left(1-\frac\right) $$

Попытаемся оценить $f$:

Из последнего выражения более-менее понятно, что вероятность $\frac$ достигается при $n \approx \sqrt$ и в этой точке изменяется очень быстро.
- - Второе доказательство** (для любителей теорвера). Введем $\frac$ индикаторов — по одному для каждой пары людей $(i, j)$ — каждый будет равен единице, если дни рождения совпали. Ожидание и вероятность каждого индикатора равна $\frac$.
  Обозначим за $X$ число совпавших дней рождений. Его ожидание равно сумме ожиданий этих индикаторов, то есть $\frac \cdot \frac$.
  
  Отсюда понятно, что если $d = \Theta(n^2)$, то ожидание равно константе, а если $d$ асимптотически больше или меньше, то $X$ стремится нулю или бесконечности соответственно.
  
  Примечание: формально, из этого явно не следует, что вероятности тоже стремятся к 0 и 1.
  
  Бонус: «мета-задача»
  Дана произвольная строка, по которой известным только авторам задачи способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток отослать решение. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердиктов всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA.
  
  Как называется совпадение хэш кодов двух различных строк
  
  PetarV → Codeforces Round #169 — Unofficial Editorial
  
  MikeMirzayanov → Codeforces Single Account Policy: zh0ukangyang is Removed from the Rating
  
  AC_AC → CSES DP SECTION — Book Shop
  
  Hexagons → [OFF TOPIC] Hollow Knight radiant tutorial for bossfight «Markoth»
  
  Gheal → Codeforces Round #833 (Div. 2) Editorial
  
  stefdasca → Easy and Quick Video Tutorials for the CSES Problem Set
  
  vrintle → Invitation to Gym Contest — Alpha IV (by AlgoRave)
  
  maomao90 → Editorial for Hello 2024
  
  maomao90 → I am top 1 contributor. AMA!
  
  YoyOyoYOy000y000 → Centroid Decomposition on a tree(Beginner)
  
  D_coder22 → Uncertainty in Python Time of Execution
  
  bycicle → Click here if you want a fast way to get rid of your alt
  
  SlavicG → Codeforces Round 918 (Div. 4)
  
  mohammed_orkhan → I wnat to be EXPERT!!
  
  thenymphsofdelphi → Codeforces Round #873 (Div. 1 & 2) Editorial
  
  VivaciousAubergine → Wow! You received a rating of -501 in the CodeTON round. Share it!
  
  diskoteka → Codeforces Round #878 (Div.3) Разбор
  
  CheaterExposer → [UPDATE] Codeforces Cheater IOI Medalist
  
  sarthak1357 → CSES shortest routes 1
  
  Pyqe → Codeforces Round #831 (Div. 1 + Div. 2, based on COMPFEST 14 Final) Editorial
  
  arham_doshi → cses graph session editorial(incomplete)
  
  SAD_IN_NIGHTMARE → 2024 OIs
  
  parth_1818 → Know Some Sorting Techniques
  
  I_am_Polish_Girl → Dijkstra Algorithgm
  
  atcoder_official → AtCoder Beginner Contest 335 (Sponsored by Mynavi) Announcement
  
  [Tutorial] Полиномиальное хэширование + разбор интересных задач
  
  Правка ru6, от dmkz, 2018-07-07 02:09:25
  
  Здравствуйте! Этот пост написан для всех тех, кто хочет освоить полиномиальные хэши и научиться применять их в решении различных задач. Я кратко приведу теоретический материал, рассмотрю особенности реализации и разберу некоторые задачи, среди них:
  1. Поиск всех вхождений одной строки длины n в другую длины m за O(n + m)
  2. Поиск наибольшей общей подстроки двух строк длин n и m (n ≥ m) за O(n + m·log(m) 2 )
  3. Нахождение лексикографически минимального циклического сдвига строки длины n за O(n·log(n))
  4. Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n) 2 )
  5. Нахождение количества подпалиндромов строки длины n за O(n·log(n))
  6. Количество подстрок строки длины n , являющихся циклическими сдвигами строки длины m за O((n + m)·log(n))
  7. Количество суффиксов строки длины n , бесконечное расширение которых совпадает с бесконечным расширением всей строки за O(n·log(n)) (расширение — дублирование строки бесконечное число раз).
  Примечание 1. Не исключено, что некоторые задачи могут быть решены быстрее другими методами, например, сортировка циклических сдвигов — это в точности то, что происходит при построении суффиксного массива, искать все вхождения одной строки в другую и работать с собственными суффиксами позволят префикс-функция и алгоритм Кнута-Морриса-Пратта, а с подпалиндромами отлично справляется алгоритм Манакера
  
  Примечание 2. В задачах выше приведена оценка, когда поиск хэша осуществляется при помощи сортировки и бинарного поиска. Если у Вас есть своя хэш-таблица с открытым перемешиванием или цепочками переполнения, то Вы — счастливчик, смело заменяйте бинарный поиск хэша на поиск в Вашей хэш-таблице, но не вздумайте использовать std::unordered_set , так как на практике поиск в std::unordered_set проигрывает сортировке и бинарному поиску в связи с тем, что эта штука подчиняется стандарту C++ и обязана много чего гарантировать пользователю, что полезно при промышленной разработке и, зачастую, бесполезно в олимпиадном программировании, поэтому сортировка и бинарный поиск для несложных структур одерживают абсолютное первенство в C++ по скорости работы, если не тянуть что-то свое.
  
  Примечание 3. В тех случаях, когда сравнение элементов затратно (например, сравнение по хэшам за O(log(n)) ), то в худшем случае std::random_shuffle + std::sort всегда проигрывает std::stable_sort , так как std::stable_sort гарантирует минимальное число сравнений среди всех сортировок (основанных на сравнениях) для худшего случая.
  
  Решение перечисленных задач будет приведено ниже, исходники тоже.
  
  В качестве плюса полиномиального хэширования могу отметить, что зачастую не нужно думать, можно сразу брать и писать наивный алгоритм решения задачи и ускорять его полиномиальным хэшированием. Лично мне решения с полиномиальным хэшем приходят в голову в первую очередь, может поэтому я синий.
  
  Среди минусов полиномиального хэширования: а) Слишком много операций остатка от деления, порой на грани TLE на больших задачах и б) на codeforces в программах на C++ зачастую маленькие гарантии от взлома из-за MinGW: std::random_device генерирует каждый раз одно и то же число, std::chrono::high_resolution_clock тикает в микросекундах вместо наносекунд. (Компилятор cygwin на windows лишен всех недостатков MinGW, в том числе и медленного ввода/вывода).
  
  `UPD`: Одолели пункт а)
  
  Для того, чтобы не использовать медленную операцию взятия остатка от деления, можно взять два модуля m₁ = 2 31 — 1 и m₂ = 2 64 .
  
  Тогда для взятия остатка от деления по модулю m₂ необходимо проводить вычисления в беззнаковом 64-битном типе, например, в типе unsigned long long в C++, т.к. во многих языках программирования гарантируется, что вычисления в этом типе данных будут проводиться по модулю 2 64 .
  
  Для взятия остатка от деления по модулю 2 31 — 1 = 2147483647 для неотрицательных чисел x до 2 62 (результат умножения двух остатков) можно брать смещенный остаток следующим образом:
```
x = x + 2147483647; x = (x >> 31) + (x & 2147483647); x = (x >> 31) + (x & 2147483647); return x; 
```
  В случае сложения и вычитания по модулю m₁ двух остатков можно обойтись обычным тернарным оператором.
  
  `UPD`: Одолели пункт б)
  
  Достаточно делать побитовое ИЛИ для значений текущего времени и адреса в памяти, полученного от менеджера кучи:
  - (uint64_t)(std::chrono::high_resolution_clock::now().time_since_epoch().count())
  - (uint64_t)(std::make_unique().get())
  Что такое полиномиальный хэш?
  
  Хэш-функция должна сопоставлять некоторому объекту некоторое число (его хэш) и обладать следующими свойствами:
  1. Если два объекта совпадают, то их хэши равны.
  2. Если два хэша равны, то объекты совпадают с большой вероятностью.
  Коллизией называется очень неприятная ситуация равенства двух хэшей у несовпадающих объектов. В идеале, при выборе хэш-функции необходимо обеспечить как можно меньшую вероятность коллизии. На практике — такую вероятность, чтобы успешно пройти набор тестов к задаче.
  
  Рассмотрим последовательность a₀, a₁, . a_{n — 1}> . Под полиномиальным хэшем для этой последовательности будем иметь в виду результат вычисления следующего выражения:
  
  Здесь p и m — точка (или основание) и модуль хэширования соответственно.
  
  Условия, которые мы наложим: , .
  
  Примечание. Если подумать об интерпретации выражения, то мы сопоставляем последовательности a₀, a₁, . a_{n — 1}> число длины n в системе счисления p и берем остаток от его деления на число m , или значение многочлена (n — 1) -й степени с коэффициентами a_i в точке p по модулю m . О выборе p и m поговорим позже.
  
  Примечание. Если значение , не взятое по модулю, помещается в целочисленный тип данных (например, 64-битный тип), то можно каждой последовательности сопоставить это число. Тогда сравнение на больше / меньше / равно можно выполнять за O(1) .
  
  Сравнение на равенство за O(1)
  
  Теперь ответим на вопрос, как сравнивать произвольные подпоследовательности за O(1) ? Покажем, что для сравнения подпоследовательностей исходной последовательности a₀, a₁, . a_{n — 1}> достаточно посчитать полиномиальный хэш на каждом префиксе исходной последовательности.
  
  Определим полиномиальный хэш на префиксе как:
  
  Кратко обозначим как и будем иметь в виду, что итоговое значение берется по модулю m . Тогда:
  
  Полиномиальный хэш на каждом префиксе можно находить за O(n) , используя рекуррентные соотношения:
  
  Допустим, нам нужно сравнить две подстроки, начинающиеся в позициях i и j и имеющие длину len , на равенство:
  
  Рассмотрим разности и . Не трудно видеть, что:
  
  Домножим 1-е уравнение на p j , а 2-е на p i . Получим:
  
  Видим, что в правой части выражений в скобках были получены полиномиальные хэши от подпоследовательностей:
  
  Таким образом, чтобы определить, совпали ли искомые подпоследовательности, необходимо проверить выполнение следующего равенства:
  
  Одно такое сравнение можно выполнять за O(1) , предподсчитав степени p по модулю. С учетом модуля m , имеем:
  
  Минусы: сравнение одной строки зависит от параметров другой строки (от j ).
  
  Если нам известны максимальные длины сравниваемых строк, то можно применить другой подход. Обозначим максимальную длину сравниваемых строк как . Домножим 1-е уравнение на p в степени mxPow — i — len + 1 , а 2-е на p в степени mxPow — j — len + 1 . Тогда:
  
  Можем заметить, что в правых частях был получен полиномиальный хэш от искомых подпоследовательностей. Тогда, равенство проверяется следующим образом:
  
  Этот подход позволяет сравнивать одну подстроку длины len со всеми подстроками длины len на равенство, в том числе, и подстроками другой строки, так как выражение для подстроки длины len , начинающейся в позиции i , зависит только от параметров подстроки i , len и константы mxPow , а не от параметров другой подстроки.
  
  Сравнение на больше / меньше за O(log(n))
  
  Рассмотрим две подстроки возможно разных строк длин len1 и len2 , (len1 ≤ len2) , начинающиеся в позициях i и j соответственно. Заметим, что отношение больше / меньше определяется первым несовпадающим символом в этих подстроках, а до позиции этого символа строки совпадают. Таким образом, необходимо найти позицию первого несовпадающего символа методом бинарного поиска, а затем сравнить найденные символы. Благодаря сравнению подстрок на равенство за O(1) , можно решить задачу сравнения подстрок на больше / меньше за O(log(len1)) :
  
  Псевдокод
```
low = 0; high = len1+1; while (high-low > 1) < mid = (low + high) / 2; if (hash(i,mid) == hash(j,mid)) < low = mid; >else < high = mid; >> low - позиция первого различия 
```
  Минимизация вероятности коллизии
  
  Пусть за все время работы программы нам нужно выполнить сравнений символов. Грубая оценка:
  
  . Тогда вероятность того, что коллизии не произойдет:
  
  Отсюда очевидно, что m нужно брать значительно больше, чем . Тогда, аппроксимируя экспоненту рядом Тейлора, получаем вероятность коллизии на одном тесте:
  
  Если мы рассмотрим задачу о поиске вхождений всех циклических сдвигов одной строки в другую строку длин до 10 5 , то мы можем получить 10 15 сравнений символов (может показаться, что 10 20 , но чем больше длина — тем меньше позиций, в которых реально нужно искать совпадения с текущим циклическим сдвигом, поэтому 10 15 ).
  
  Тогда, если мы возьмем простой модуль порядка 10 9 , то мы не пройдем ни один из максимальных тестов.
  
  Если мы возьмем модуль порядка 10 18 , то вероятность коллизии на одном тесте ≈ 0.001 . Если максимальных тестов 100 , то вероятность коллизии в одном из тестов ≈ 0.1 , то есть 10% .
  
  Если мы возьмем модуль порядка 10 27 , то на 100 максимальных тестах вероятность коллизии равна ≈ 10 — 10 .
  
  Вывод: чем больше модуль — тем больше вероятность пройти тест. Эта вероятность не учитывает взломы.
  
  Двойной полиномиальный хэш
  
  Разумеется, в реальных программах мы не можем брать модули порядка 10 27 . Как быть? На помощь приходит китайская теорема об остатках. Если мы возьмем два взаимно простых модуля m₁ и m₂ , то кольцо остатков по модулю m = m₁·m₂ эквивалентно произведению колец по модулям m₁ и m₂ , т.е. между ними существует взаимно однозначное соответствие, основанное на идемпотентах кольца вычетов по модулю m . Иными словами, если вычислять по модулю m₁ и по модулю m₂ , а затем сравнивать две подпоследовательности по и одновременно, то это эквивалентно сравнению полиномиальным хэшем по модулю m . Аналогично, можно брать три взаимно простых модуля m₁ , m₂ , m₃ .
  
  Особенности реализации
  
  Итак, мы подошли к реализации описанного выше. Цель — минимум взятий остатка от деления, т.е. получить два умножения в 64-битном типе и одно взятие остатка от деления в 64-битном типе на одно вычисление двойного полиномиального хэша, при этом получить хэш по модулю порядка 10^27 и защитить код от взлома на codeforces.
  
  Выбор модулей. Выгодно использовать двойной полиномиальный хэш по модулям m1 = 1000000123 и m2 = 2^64 . Если Вам не нравится такой выбор m1 , можете выбрать 1000000321 , главное выбрать такое простое число, чтобы разность двух остатков лежала в пределах знакового 32-битного типа (int). Простое число брать удобнее, так как автоматически обеспечиваются условия gcd(m1, m2) = 1 и gcd(m1, p) = 1 . Выбор в качестве m2 = 2^64 не случаен. Стандарт C++ гарантирует, что все вычисления в unsigned long long выполняются по модулю 2^64 автоматически. Отдельно модуль 2^64 брать нельзя, так как существует анти-хэш тест, который не зависит от выбора точки хэширования p . Модуль m1 необходимо задать как константу для ускорения взятия модуля (компилятор (не MinGW) оптимизирует, заменяя умножением и побитовым сдвигом).
  
  Кодирование последовательности. Если дана последовательность символов, состоящая, например, из маленьких латинских букв, то можно ничего не кодировать, так как каждому символу уже соответствует его код. Если дана последовательность целых чисел разумной для представления в памяти длины, то можно собрать в один массив все встречающиеся числа, отсортировать, удалить повторы и сопоставить каждому числу в последовательности его порядковый номер в полученном упорядоченном множестве. Начинать нумерацию с нуля запрещено: все последовательности вида 0,0,0. 0 разной длины будут иметь один и тот же полиномиальный хэш.
  
  Выбор основания. В качестве основания p достаточно взять любое нечетное число, удовлетворяющее условию max(a[i]) < p < m1 . (нечетное, потому что тогда gcd(p, 2^64) = 1 ). Если Вас могут взломать, то необходимо генерировать p случайным образом с каждым новым запуском программы, причем генерация при помощи std::srand(std::time(0)) и std::rand() не подходит, так как std::time(0) тикает очень медленно, а std::rand() не обеспечивает достаточной равномерности. Если компилятор НЕ MinGW (к сожалению, на codeforces установлен MinGW), то можно использовать std::random_device , std::mt19937 , std::uniform_int_distribution (в cygwin на windows и gnu gcc на linux данный набор обеспечивает почти абсолютную случайность). Если не повезло и Вас посадили на MinGW, то ничего не остается, как std::random_device заменить на std::chrono::high_resolution_clock и надеяться на лучшее (или есть способ достать какой-нибудь счетчик из процессора?). На MinGW этот таймер тикает в микросекундах, на cygwin и gnu gcc в наносекундах.
  
  Гарантии от взлома. Нечетных чисел до модуля порядка 10^9 тоже порядка 10^9 . Взломщику необходимо будет сгенерировать для каждого нечетного числа анти-хэш тест так, чтобы была коллизия в пространстве до 10^27 , скомпоновать все тесты в один большой тест и сломать Вас. Это если использовать не MinGW на Windows. На MinGW таймер тикает, как уже говорилось, в микросекундах. Зная время запуска решения на сервере с точностью до секунд, можно для каждой из 10^6 микросекунд вычислить, какое случайное p сгенерировалось, и тогда вариантов в 1000 раз меньше. Если 10^9 это какая-то космическая величина, то 10^6 уже кажется не такой безопасной. При использовании std::time(0) всего 10^3 вариантов (миллисекунды) — можно ломать. В комментариях я видел, что гроссмейстеры умеют ломать полиномиальный хэш до 10^36 .
  
  Удобство в использовании. Удобно написать универсальный объект для полиномиального хэша и копировать его в ту задачу, где он может понадобиться. Лучше писать самостоятельно для своих нужд и целей в том стиле, в котором пишете Вы, чтобы разбираться в исходном коде при необходимости. Все задачи в этом посте решены при помощи копирования одного и того же объекта. Не исключено, что существуют специфические задачи, в которых это не сработает.
  
  Задача 1. Поиск всех вхождений одной строки длины n в другую длины m за O(n + m)
  
  Дано: Две строки S и T длин до 50000 . Вывести все позиции вхождения строки T в строку S . Индексация с нуля.
  
  Пример: Ввод S = «ababbababa» , T = «aba» , вывод: 0 5 7 .
  
  Решение и код
  
  Посчитаем полиномиальный хэш на префиксах строк S и T . Будем идти вдоль строки S , сравнивая полиномиальный хэш текущей подстроки со всей строкой T . При совпадении хэшей выводим текущую позицию. Асимптотика: O(n) по времени и памяти. Исходный код.
  
  Задача 2. Поиск наибольшей общей подстроки двух строк длин n и m (n ≥ m) за O(n + m·log(m) 2 )
  
  Дано: Длина строк N и две строки A и B длины до 100000 . Вывести длину наибольшей общей подстроки.
  
  Пример: Ввод: N = 28 , A = «VOTEFORTHEGREATALBANIAFORYOU» , B = «CHOOSETHEGREATALBANIANFUTURE» , вывод: THEGREATALBANIA
  
  Решение и код
  
  Первым делом посчитаем полиномиальный хэш на префиксах строк A и B . Пусть мы нашли наибольшую общую подстроку длины len , начинающуюся в позиции pos любой из строк. Тогда общей подстрокой будет также и любая подстрока длин len-1, len-2, . 1 , начинающаяся в позиции pos , а len+1 уже не будет являться общей подстрокой. Видно, что выполняются условия бинарного поиска. Инициализация бинарного поиска: low = 0 , high = N+1 . На каждой итерации поиска будем складывать все хэши подстрок длины mid строки A в вектор, сортировать его, а дальше проходить по хэшам подстрок длины mid строки B и искать их среди отсортированных хэшей строки A . Асимптотика решения по времени O(n log(n)^2) , по памяти O(n) . Исходный код.
  
  Задача 3. Нахождение лексикографически минимального циклического сдвига строки длины n за O(n·log(n))
  
  Дано: Строка S длины до 10^5 . Вывести минимальный лексикографически сдвиг строки A .
  
  Пример: Ввод: «program» , Вывод: «amprogr»
  
  Решение и код
  
  В этой задаче необходимо написать сравнение двух подстрок методом бинарного поиска, описанным выше. Продублируем строку S и посчитаем полиномиальный хэш на префиксе. Каждый циклический сдвиг будем представлять в виде числа (начальной позиции). Сложим в вектор все позиции, а дальше применим линейный алгоритм нахождения минимума в массиве, используя оператор сравнения подстрок. Асимптотика: O(n log(n)) по времени и O(n) по памяти. Исходный код.
  
  Задача 4. Сортировка всех циклических сдвигов строки длины n в лексикографическом порядке за O(n·log(n) 2 )
  
  Дано: Строка S длины до 10^5 . Вывести номер позиции исходного слова в отсортированном списке циклических сдвигов. Если таких позиций несколько, то следует вывести позицию с наименьшим номером. Во второй строке вывести последний столбец таблицы циклических сдвигов.
  
  Пример: Ввод: «abraka» , Вывод: «2 karaab»
  
  Замечания
  
  Не забудьте, что быстрая сортировка в процесса своей работы может переставлять элементы, но по условию задачи, равные циклические сдвиги не переставляются. Изначально теста против этого не было, теперь он есть. Более того, одиночный полиномиальный хэш по модулю 2^64 валится на этой задаче. Изначально анти-хэш теста не было, теперь он есть.
  
  Решение и код
  
  Не хотите строить суффиксный массив? Я тоже. Но когда-то все-таки нужно будет его построить, а пока продублируем строку S и посчитаем полиномиальный хэш на префиксе. Каждый циклический сдвиг будем представлять в виде числа (начальной позиции). Сложим в вектор все позиции, а дальше применим устойчивую сортировку слиянием, используя оператор сравнения подстрок. Асимптотика: O(n log(n)^2) по времени и O(n) по памяти.
  
  Победила сортировка слиянием. Если кто-нибудь сдаст построением суффиксного массива, сообщите Ваш результат.
  
  Задача 5. Нахождение количества подпалиндромов строки длины n за O(n·log(n))
  
  Дано: Строка S длины до 10^5 . Вывести количество подпалиндромов строки.
  
  Пример: Ввод: «ABACABADABACABA» , Вывод: 32
  
  Решение и код
  
  Скопируем исходную строку и обратим порядок элементов. Построим полиномиальный хэш на префиксах исходной строки и развернутой. Будем перебирать центры палиндромов и применять бинарный поиск по длине максимального палиндрома, имеющего центр в текущем символе.
  
  Пусть строка S — исходная, а строка T — развернутая. Тогда необходимо сравнивать хэши:
  
  S[i. i+len-1] и T[j. j+len-1] , где j = n — i + 1 .
  
  Затем будем строить палиндромы четной длины. В этом случае нужно сравнивать хэши:
  
  S[i+1. i+len] и T[j. j+len-1] , где j = n — i + 1 .
  
  Исходный код. Асимптотика решения: O(nlog(n)) по времени и O(n) по памяти. На версии задачи с ограничениями 10^6 код получает Memory Limit (38 МБ). Задача для 10^6 не проходит с хэшем по модулю 2^64 — коллизия на тесте 7.
  
  Задача 6. Количество подстрок строки длины n , являющихся циклическими сдвигами строки длины m за O((n + m)·log(n))
  
  Дано: Заданы две строки S и T длины до 10^5 . Необходимо определить, сколько подстрок строки S являются циклическими сдвигами строки T .
  
  Пример: Ввод: S = «aAaa8aaAa» , T=»aAa» , Вывод: 4
  
  Решение и код
  
  Запомним исходную длину строки T и продублируем строку 2 раза. Пусть n — исходная длина. Построим полиномиальный хэш на префиксах строк S и T . Выпишем хэши всех подстрок длины n строки T и отсортируем. Теперь задача свелась к тому, чтобы поискать каждую подстроку длины n строки S среди выписанных хэшей строки T . Это можно сделать за O(n log(n)) по времени и O(n) по памяти. Исходный код.
  
  Задача 7. Количество суффиксов строки длины n , бесконечное расширение которых совпадает с бесконечным расширением всей строки за O(n·log(n))
  
  Дано: Строка S длины до 10^5 . Бесконечным расширением строки назовем строку, полученную выписыванием исходной строки бесконечное число раз. Например, бесконечное расширение строки «abс» равно «abcabcabcabcabc. «. Необходимо ответить на вопрос, сколько суффиксов исходной строки имеют такое же бесконечное расширение, какое и строка S .
  
  Пример: На входе: S = «qqqq» , на выходе 4 .
  
  Решение и код
  
  Первым делом развернем строку S и будем решать для префиксов. Построим полиномиальный хэш на префиксе строки S . Далее необходимо сравнить расширение каждого префикса с расширением исходной строки.
  
  Пусть есть префикс S[0. m) длины m и префикс S[0. n) длины n , где n >= m . Рассмотрим расширение длины n*m . Это будет означать, что мы префикс S[0..m) запишем n раз подряд, а префикс S[0..n) — m раз подряд:
  
  S[0. m)* = (1+p^m+p^(2m)+p^(3m)+p^((n-1)m))(S[0] + S[1] * p + S[2] * p^2 + . + S[m-1] * p^(m-1)))
  
  S[0. n)* = (1+p^n+p^(2n)+p^(3n)+p^((m-1)n))(S[0] + S[1] * p + S[2] * p^2 + . + S[n-1] * p^(n-1)))
  
  Хэш на префиксе вычислять мы уже умеем, осталось решить подзадачу вычисления следующей суммы:
  
  Ответ sum(a, k) = (a^k-1) / (a — 1) = (a^k — 1) * inverse(a-1, mod) — неверный, так как у четных чисел нет обратных в кольце по модулю 2^64 .
  
  Пусть k — четное, например, k = 8 . Тогда:
  
  sum(a,8) = 1+a+a^2+a^3+a^4+a^5+a^6+a^7 = (1+a)*(1+a^2+a^4+a^6) = (1+a) * sum(a^2, 4)
  
  пусть k — нечетное, например, k = 7 . Тогда:
  
  sum(a,7) = 1+a+a^2+a^3+a^4+a^5+a^6 = 1 + a * (1+a+a^2+a^3+a^4+a^5) = 1 + a * sum(a, 6)
  
  Получили рекуррентные формулы, позволяющие вычислять значения sum(a, k) для любых a и k за O(log(k)) :
  
  sum(a, 2*k) = (1+a) * sum(a^2, k) и sum(a, 2*k+1) = 1 + a * sum(a, 2*k) .
  
  В случае простого же модуля предложенный способ вычисления суммы геометрической прогрессии быстрее в два раза, чем sum(a, k) = (a^k — 1) * inverse(a-1, mod) , так как второй способ вызывает функцию быстрого возведения в степень два раза. В случаях с хэшами ускорение в два раза может быть критично.
  
  Осталось только сравнить sum(p^m, n) * pref(m) с sum(p^n, m) * pref(n) . Асимптотика решения O(n log(n)) по времени и O(n) по памяти. Исходный код.
  
  На этом все. Надеюсь, этот пост поможет Вам активно применять хэширование и решать более сложные задачи. Буду рад любым комментариям, исправлениям и предложениям. В ближайших планах перевести этот пост на английский язык, поэтому нужны ссылки, где эти задачи можно сдать на английском языке. Возможно, к тому времени Вы внесете существенные корректировки и дополнения в этот пост. Ребята из Индии говорят, что пытались сидеть с гугл-переводчиком и переводить с русского языка посты про полиномиальный хэш и у них это плохо вышло. Делитесь другими задачами и, возможно, их решениями, а также решениями указанных задач не через хэши. Спасибо за внимание!
  
  Полезные ссылки:
  
  хэши, хэширование, tutorial, бинарный поиск, сортировка
  
  Почему одинаковый хэш-код может быть у разных объектов?
  
  Иначе наши методы будут лишены смысла. Проверка по hashCode(), как мы и сказали, должна идти первой для повышения быстродействия. Если хэш-коды будут разными, проверка вернет false, хотя объекты на самом деле равны (согласно нашему определению в методе equals()).
  
  Если метод hashCode() вызывается несколько раз на одном и том же объекте, каждый раз он должен возвращать одно и то же число.
  
  Правило 1 не работает в обратную сторону. Одинаковый хэш-код может быть у двух разных объектов.
  
  Я запутался помогите разобраться:
  Почему в 3 правило написано мол правило 1 не работает в обратную сторону?
  Получается 1 правило 2 объекта равны и у них хэш-код одинаковый.
  А 3 правило так же одинаковый хэш-код у 2 объектов или я не очень понимаю? Почему в 1 правило написано если 2 объекта равны, а в 3 правило написано одинаковый хэш-код может быть у двух РАЗНЫХ объектов, как понять разных?
  
  Отслеживать
  66.5k 6 6 золотых знаков 53 53 серебряных знака 112 112 бронзовых знаков
  задан 11 мая 2019 в 9:38
  Петровченко Иван Петровченко Иван
  1,913 1 1 золотой знак 13 13 серебряных знаков 36 36 бронзовых знаков
  
  Вся суть в том, что множество объектов ограничено только Вашей фантазией, а множество хэш-кодов ограничено диапазоном типа Integer . Исходя из этого, кол-во различных объектов может быть больше, чем кол-во различных хэш-кодов, откуда следует, что у разных объектов может быть одинаковый хэш-код (т.н. коллизия). Сначала проверяется хэш-код, а затем equals . Если хэш-коды разные, то и объекты гарантированно разные и проверять на equals смысла нет. Если же хэш-коды одинаковые, то необходимо еще проверить на equals .
  
  11 мая 2019 в 9:52
  @post_zeew а если использовать BigInteger ?)
  11 мая 2019 в 9:56
  
  1 ответ 1
  
  Сортировка: Сброс на вариант по умолчанию
  
  Примечание: предполагается, что в классе переопределен метод hashCode() .
  
  По хорошему, у разных объектов хешкод должен быть разный. Но на практике иногда происходит по другому. Очень часто это происходит из-за несовершенства формулы для вычисления хешкода.
  
  Пример: хеш строки считается по длине строки: length*3 . Тогда у строк foo и bar одинаковые хеши.
  
  Вообще, хешкод используется для того, чтобы можно было точно сказать, что объекты разные. Но не для того, чтобы сказать, что они одинаковые. Одинаковый хешкод — не гарантия одинаковых объектов.
  
  Обычно он используется для сравнения объектов:
  Допустим, у вас есть объект, в котором есть много-много полей. В большинстве случаев объекты для сравнения будут неравны. Чтобы не сравнивать кучу переменных(если объекты не равны), можно сначала сравнивать хешкод(т.к., если хеш различается, то объекты точно различны). Если хеши отличаются — можно дальше не сравнивать переменные. Если одинаковы — дальше нужно сравнить переменные(т.к., если хеши одинаковы, то это не значит, что объекты одинаковы).
  
  Ну и последнее — почти всегда возвращаемый тип метода hashCode() — int . У int есть определенный предел(от -21. до +21. если я не ошибаюсь). Если разных объектов будет больше, чем этот предел, то физически нельзя сгенерировать разные хеши для всех объектов. Т.е., при использовании хешей можно увеличить производительность программы.
  
  Попробую объяснить правила:
  - У одинаковых объектов всегда одинаковые хеши
  - У одного и того же объекта всегда должен быть неизменяемый хешкод(если значения внутри объекта не изменились)
  - У разных объектов иногда могут быть одинаковые хеши
  Похожие публикации: