Кольцевой хэш

Кольцевой хэш (англ. rolling hash) — хэш-функция, обрабатывающая вход в рамках некоторого окна. Получение значения хэш-функции для сдвинутого окна (window ) в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь предыдущее значение хэша; значение входных данных, которые остались за пределами окна; и значение данных, которые попали в окно. Процесс сходен с вычислением Скользящей среднего.

Применяется в алгоритме поиска подстроки Рабина — Карпа, а также в программе rsync для сравнения двоичных файлов (используется кольцевая версия adler-32).

Кольцевой хэш Рабина-Карпа

В алгоритме Рабина — Карпа часто используется простой кольцевой хэш, построенный на операциях умножения и сложения^[1]

$H = c_1 a^{k-1} + c_2 a^{k-2} + c_3 a^{k-3} + ... + c_k a^{0}$ где $a$ константа, а $c_1, ..., c_k$ — входные символы.

Чтобы избежать использования целочисленной арифметики произвольной точности, используется арифметика в кольце вычетов по модулю $n$. Выбор констант $a$ и $n$ очень важен для получения качественного хэша (см. Линейный конгруэнтный метод).

Удаление старых входных символов и добавление новых производится путем прибавления или вычитания первого или последнего члена формулы. Сдвиг окна производится путем домножения всего многочлена $H$ на $a$, либо делением на $a$ (в кольце вычетов возможно вместо деления производить умножение на обратную величину).

Buzhash

Возможно также построение кольцевой хэш-функции без умножения (на операции сдвига)^[2]. Подобные функции иногда называют Buzhash

Ссылки

• ngramhashing is a Free software C++ implementation of several rolling hash functions
• rollinghashjava is an Apache licensed Java implementation of rolling hash functions

Примечания

1. ↑ Методы и алгоритмы вычислений на строках, 7.3
2. ↑ Jonathan D. Cohen, Recursive hashing functions for n-grams, ACM Trans. Inf. Syst. 15 (3), 1997