Информатика · объяснение и практика
Скользящий хеш: быстро сравнить кандидатов и проверить совпадение
Скользящий полиномиальный хеш: два обновления окна, согласование степеней, нормализация отрицательного остатка и проверка прямым подсчётом.

В теме Методы алгоритмов: углубление · Учебная карта
В маршруте Сортировки и сравнение строк · 10 тем
Главная мысль
Полиномиальный хеш заменяет строку числом по выбранному основанию и модулю. При сдвиге окна вклад первого символа можно убрать, остальные степени сдвинуть и добавить новый символ. Равные строки дают равные хеши, но равные хеши не доказывают равенство строк.
Фиксируем соглашение до вычислений
Пусть символам назначены целые коды, основание равно b, модуль равен m. Будем читать строку слева направо и обновлять число по правилу H=(H·b+c)mod m, начиная с нуля. Тогда первый символ получает наибольшую степень основания. В других описаниях степени могут идти в обратную сторону; смешивать формулы двух соглашений нельзя.
Для окна длины L вклад первого символа равен c₀·b^(L−1). Чтобы продолжить окно вправо, вычитают этот вклад, умножают остаток на b и добавляют код нового символа. После вычисления берут остаток по модулю. В языках с отрицательным остатком результат дополнительно приводят к выбранному диапазону.
Обновляем окно два раза
Для собственного примера возьмём коды a=1, b=2, c=3, d=4, e=5, основание 7, модуль 101 и окно длины три. Хеш «abc» равен 1·49+2·7+3=66. При сдвиге к «bcd» удаляем вклад a, затем умножаем остаток на основание и добавляем d: (66−49)·7+4=123. Остаток по модулю 101 равен 22. Прямой подсчёт 2·49+3·7+4 также даёт 123 и остаток 22.
Для следующего окна «cde» получаем (22−2·49)·7+5=−527. Приводим к диапазону от нуля до ста: остаток равен 79. Прямой полином 3·49+4·7+5=180 подтверждает 79. Отрицательная промежуточная величина допустима; важно согласованно нормализовать остаток. Само обновление хеша не устраняет возможных коллизий при сравнении строк.
Пример
Почему после удаления первого символа нужно ещё умножить оставшуюся часть на 7?
Коды оставшихся символов должны перейти к степеням нового окна: бывшая средняя позиция становится старшей. Если только вычесть вклад a и прибавить d, получится 21 вместо правильного остатка 22.
Что нужно для надёжного применения
При сравнении фрагментов учитывают их длину, одно и то же кодирование и согласованные степени основания. Использование двух независимых хешей уменьшает риск случайного столкновения при подходящих предположениях, но не превращает конечный набор чисел в доказательство уникальности любой строки.
Обычный полиномиальный хеш также не является криптографической подписью и не защищает от намеренной подмены. Для точного поиска можно сравнивать символы после совпадения хешей либо выбрать другой детерминированный алгоритм. Вычислительная экономия и требуемая гарантия ответа должны обсуждаться отдельно, особенно когда входные данные может выбирать заинтересованный противник.
От чтения к действию
А теперь — вы
Частые вопросы
Разные хеши доказывают различие строк?
При одинаковой функции и кодировании — да: равные строки обязательно дали бы равный хеш.
Одинаковые хеши достаточно объявить одной строкой?
Нет. Возможны коллизии; для точного ответа нужна проверка исходных данных или другой гарантированный метод.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Префикс-функция: как искать границу совпавшего фрагмента
Префикс-функция строки: собственная граница, суффикс обработанного префикса и переход к более короткому совпадению.
Открыть темуZ-функция строки: длины совпадения с её началом
Z-функция без путаницы с префикс-функцией: совпадение от текущей позиции, правая граница известного блока и длина результата.
Открыть тему