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

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

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

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

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

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

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

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

Примітки


