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

Возможность быстрого «сдвига» хеша накладывает некоторые ограничения на теоретические гарантии. В частности, показано, что семейства кольцевых хешей не могут быть ; максимум — универсальными или . Впрочем, для большинства приложений достаточно универсальности (даже приблизительной).

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

Полиномиальный хеш В алгоритме Рабина — Карпа часто используется простой полиномиальный кольцевой хеш, построенный на операциях умножения и сложения: . Чтобы избежать использования целочисленной арифметики произвольной точности, используется арифметика в кольце вычетов по модулю , умещающемуся в одно машинное слово. Выбор констант и очень важен для получения качественного хеша. В исходном варианте хеша предполагалось, что должно быть случайно выбранным простым числом, а . Но ввиду того, что алгоритм выбора случайного простого числа не такой простой, предпочитают использовать вариант хеша, в котором является фиксированным простым числом, а выбирается случайно из диапазона . Дитзфелбингер и др. показали, что такой вариант хеша имеет те же теоретические характеристики, что и исходный. В частности, вероятность совпадения значений хешей двух различных строк и не превосходит , если и представляют собой целые числа из диапазона , и выбирается действительно случайно.

Удаление старых входных символов и добавление новых производится путём прибавления или вычитания первого или последнего члена формулы (по модулю ). Для удаления члена хранят заранее посчитанное значение . Сдвиг окна производится путём домножения всего многочлена на либо делением на (если простое, то в кольце вычетов возможно вместо деления производить умножение на обратную величину). На практике удобнее всего полагать или для, соответственно, 32- и 64-битовых машинных слов (это так называемые простые числа Мерсенна). В таком случае операция взятия модуля может быть выполнена на многих компьютерах с помощью быстрых операций побитового сдвига и сложенияS. E. Anderson. Bit twiddling hacks. . Другой возможный выбор — значения или , для которых тоже существуют быстрые алгоритмы взятия остатка от деления на (при этом диапазон допустимых значений немного сужают). Частое заблуждение — полагать . Существуют семейства строк, на которых хеш с будет всегда давать множество коллизий, независимо от выбора . Эти и другие дальнейшие детали реализации и теоретического анализ полиномиального хеша можно найти в статье об алгоритме Рабина — Карпа.

Полиномиальный хеш над полем GF(2L) Данный хеш похож на обычный полиномиальный хеш, но все вычисления в нём производятся в конечном поле . Обычно выбирается равным 64. Элементы поля — это числа . Сложение в поле реализуется с помощью операции побитового исключающего «или» , а умножение выполняется с помощью операции , которая сначала на , а потом берёт остаток от «беспереносного» деления результата на некоторый выбранный фиксированный элемент (беспереносным делением здесь названа операция, обратная беспереносному умножению). Элемент должен быть выбран так, что и — это неприводимый многочлен над полем (на поле часто смотрят как на множество многочленов над полем по модулю произвольного неприводимого многочлена степени ). Например, можно положить . Тогда хеш вычисляется следующим образом: , где — это случайно выбранное на этапе инициализации хеша число из диапазона , а — это короткая запись для , где повторён раз. С помощью основной теоремы алгебры можно показать, что вероятность коллизии хешей двух различных строк длины не превосходит . Показано, что на современных процессорах Intel и AMD вся необходимая для хеша арифметика над полем может быть эффективно вычислена с помощью инструкций из расширения .

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

где  — это операция побитового исключающего «или», а  — это операция циклического сдвига -битового числа на битов влево. Несложно показать, что данный хеш кольцевой:

Главное преимущество этого хеша в том, что он использует только быстрые побитовые операции доступные на многих современных компьютерах. Качество хеша напрямую зависит от выбора функции . Лемире и Касер доказали, что если функция выбирается случайно из семейства , то вероятность совпадения хешей двух различных строк длины не превосходит . Это накладывает определённые ограничения на диапазон задач, в которых данный хеш может использоваться. Во-первых, длина хешируемых строк должна быть меньше . Для алгоритмов хеширования общего назначения это условие может быть проблемой, но, например, для хеширования -грамм, где обычно не превосходит 16, такое ограничение является естественным (в случае -грамм роль символов играют отдельные лексемы текста). Во-вторых, выбор семейства независимых функций в некоторых случаях тоже может быть проблемой. Для байтового алфавита свойством независимости обладает семейство функций , закодированных таблицей из 256-и различных случайных -битовых чисел (выбор функции — это заполнение таблицы). Для хеширования -грамм можно присваивать различные случайные -битовые числа различным лексемам (обычно число разных лексем в таких задачах относительно невелико) и такое семейство хеш-функций тоже имеет свойство независимости.

Хеш Рабина Данный хеш применим только в специальном случае, когда символы хешируемой строки суть числа 0 и 1. Идея хеша в том, чтобы смотреть на входную строку как на многочлен над полем , а сам хеш представляет собой взятие остатка от деления на случайно выбранный на этапе инициализации хеша неприводимый многочлен степени над полем . По существу это та же процедура, что используется в CRC. Рассмотрим её более подробно.

Результат хеширования строки — это последовательность битов . Число выбирается простым и достаточно большим, но так чтобы последовательность умещалась в одно машинное слово (обычно берут или ). Пусть представляет собой некоторый неприводимый многочлен степени над полем . Обозначим через соответствующее число с битовым представлением . Хеш-функция определяется как число с битовым представлением таким что многочлен является остатком от деления многочлена на многочлен , то есть .

Несмотря на весьма запутанное определение, хеш Рабина довольно просто реализуем (если неприводимый многочлен уже найден). Вычисления опираются на такое несложное наблюдение: если число с битовым представлением кодирует многочлен , то число кодирует многочлен , где обозначает операцию побитового сдвига числа на один бит влево с замещением младшего бита нулём (не путать с циклическим сдвигом , определённым выше!). Пусть , и  — это битовое представление . Тогда вычисляется следующим образом: если если

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

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

Отметим, что данный хеш часто путают с полиномиальным хешем из-за схожей области применения, рассмотрения многочленов и общего автора.

Ссылки ngramhashing — свободная C++-реализация нескольких кольцевых хеш-функций rollinghashjava  — Java-реализация кольцевых хеш-функций под лицензией Apache

Примечания

Литература

Категория:Хеш-функции