Полиномиальное хеширование строк
Содержание
Зачем нужны хеши?
Сравнивать строки $S_1, S_2$ мы умеем за $O(|S|)$. Если бы мы могли для каждой из строк за $O(1)$ вычислить какую-нибудь функцию, которая для разных аргументов принимает разные значения (такие функции называются инъекциями), то мы могли бы сравнивать строки уже за $O(1)$.
'Хеш-функцией' назовём любую функцию, которая отображает строки (на самом деле не только их) в ${0, 1, \dots, M}$ для некоторого постоянного $M$. Хэшем строки будем называть значение хеш-функции на ней.
По принципу Дирихле, если количество различных строк, которые наша функция может принимать, превышает $M$, то найдутся две строки с одинаковыми хешами $\implies$ наша хеш-функция $~-$ не инъекция $\implies$ значение $M$ стоит выбирать как можно больше.
Полиномиальный хеш
Положим $h(s_0s_2...s_n) = (p^{n+1}s_0 + p^{n}s_1 + \dots + p^1s_{n-1} + s_n) % M$, где $p, M ~-$ некоторые фиксированные константы, требования к которым мы предъявим чуть позже.
Какие $p$ и $M$ выбрать?
Первое требование (б/д) $~-$ на $p$: $p > max \{s_i\}$. Если это так, то хеш от строки без взятия по модулю (по сути, значение многочлена в некоторой точке) $~-$ инъекция. А вот если брать $p$ меньше, чем $max \{s_i\}$, то коллизии могут появиться ещё на этапе подсчёта.
Далее, мы хотим выбрать такие $p$ и $M$, чтобы минимизировать вероятность коллизии. В частности, мы хотим минимизировать количество таких остатков, которые не могут быть хешом никакой строки. Давайте тогда возьмём взаимнопростые $p$ и $M$.
Из парадокса дней рождений следует, что если объектов хотя бы корень от числа возможных значений хеш-функции, то коллизия будет с достаточно большой вероятностью. В этом случае, можно воспользоваться хеш-таблицами: