Коткий геш

Коткий геш (англ. rolling hash) (також відомий як рекурсивне гешування або котка контрольна сума) — це геш-функція, яка гешує дані у вікні, що рухається уздовж входових даних.

Декілька геш-функцій дозволяють швидке обчислення коткого гешу маючи лише попередній геш і видалене з і до додане до вікна значення. Це подібно до функції рухомого середнього, яку можна обчислити швидше ніж інші низькочастотні фільтри.

Одне з найпомініших застосувань це алгоритм Рабіна — Карпа пошуку підрядка, який використовує геш описаний нижче. Інше поширене застосування це застосунок rsync, який в якості коткого гешу використовує контрольну суму породжену з adler-32. Вузькосмугова мережева файлова система (LBFS) використовує «відбиткі пальців» Рабіна як коткий геш.

Щонайбільше, значення коткого гешу попарно незалежні або сильно універсальні. Наприклад, вони не можуть бути потрійково незалежні.

Поліномний коткий геш

Алгоритм Рабіна — Карпа часто пояснюють за допомогою функції коткого гешу, яка використовує лише множення і додавання:

$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}$ це входові символи (але ця функція не є «відбитками пальців» Рабіна).

Щоб не довелось працювати з величезними значеннями $H$, всю математику роблять за модулем $n$. Вибір $a$ і $n$ критичний для отримання хорошого гешування; дивись лінійний конгруентний метод.

Видаляння і додавання символів потребує просто додавання або віднімання першого або останнього доданку. Зсування всіх символів на одну позицію ліворуч вимагає домноження усієї суми $H$ на $a$. Зауважте, що в модульній арифметиці $a$ можна обрати так, щоб вона мала множильне обернене $a^{-1}$, на яке можна домножити $H$, щоб отримати ділення не роблячи його насправді.