Полиномиальное хеширование строк: различия между версиями
(Новая страница: «== Зачем нужны хеши? == Сравнивать строки $S_1, S_2$ мы умеем за $O(|S|)$. Если бы мы могли для каждо...») |
|||
Строка 21: | Строка 21: | ||
*[[Хеш-таблицы (открытый ключ)]] | *[[Хеш-таблицы (открытый ключ)]] | ||
*[[Хеш-таблицы (цепочки)]]. | *[[Хеш-таблицы (цепочки)]]. | ||
+ | |||
+ | == [http://acm.math.spbu.ru/~sk1/algo/hash/HashStrComparator_simple.cpp.html Готовый код для вашего шаблона] == |
Версия 22:29, 23 января 2020
Содержание
Зачем нужны хеши?
Сравнивать строки $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$.
Из парадокса дней рождений следует, что если объектов хотя бы корень от числа возможных значений хеш-функции, то коллизия будет с достаточно большой вероятностью. В этом случае, можно воспользоваться хеш-таблицами: