Перегляд вихідного коду сторінки Універсальне гешування

У [[Математика|математиці]] та [[Комп'ютинг|обчислювальній техніці]] '''універсальне гешування''' (у [[Увипадковлений алгоритм|рандомізованому алгоритмі]] чи структурі даних) означає випадковий вибір [[Хеш-функція|геш-функції]] з сімейства геш-функцій із певною математичною властивістю (див. визначення нижче). Це гарантує низьку кількість [[Колізія геш-функції|колізій]] в [[Математичне сподівання|очікуванні]], навіть якщо дані вибирає зловмисник. Відомо багато універсальних сімейств (для гешування цілих чисел, векторів, рядків), і їх оцінка часто дуже ефективна. Універсальне гешування має численні застосування в інформатиці, наприклад у реалізації [[Геш-таблиця|геш-таблиць]], [[Увипадковлений алгоритм|рандомізованих алгоритмів]] і [[Криптографія|криптографії]].

== Вступ ==
Припустимо, ми хочемо відобразити ключі з якогось [[Універсум (математика)|універсуму]] <math>U</math> в <math>m</math> кошиків (позначених <math>[m] = \{0, \dots, m-1\}</math>). Алгоритм повинен буде обробляти певний набір даних <math>S \subseteq U</math> з <math>|S|=n</math> ключів, про які заздалегідь не відомо. Зазвичай метою гешування є отримання невеликої кількості колізій (ключів з <math>S</math> які потрапляють в один кошик). Детермінована геш-функція не може запропонувати жодних гарантій у ситуації змагання, якщо <math>|U| > m \cdot n</math>, оскільки противник може вибрати <math>S</math>, яке є саме [[Образ відображення|прообразом]] кошика. Це означає, що всі ключі даних потрапляють в один кошик, що робить гешування марним. Крім того, детермінована геш-функція не допускає ''повторного гешування'': іноді вхідні дані виявляються поганими для геш-функції (наприклад, забагато колізій), тому можна змінити геш-функцію.

Рішення цих проблем полягає у випадковому виборі геш-функції з сімейства геш-функцій. Сімейство геш-функцій <math>H = \{ h : U \to [m] \}</math> називається '''універсальним''', якщо

<math>\forall x, y \in U, ~ x\ne y: ~~ |\{h\in H: h(x) = h(y)\}|\le \frac{|H|}{m}</math>

Іншими словами, будь-які два різні ключі універсуму утворюють колізію з максимальною ймовірністю <math>1/m</math> коли геш-функція <math>h</math> обирається рівноімовірно випадковим чином із <math>H</math>. Це саме та ймовірність колізії, яку ми очікували б, якби геш-функція призначала справді випадкові геш-коди кожному ключу.

Іноді визначення пом'якшується постійним множником, коли вимагається лише ймовірність колізії <math>O(1/m)</math> а не <math>\leq 1/m</math> . Ця концепція була введена Картером і Вегманом<ref name="CW77">
{{Cite journal|last=Carter|first=Larry|last2=Wegman|first2=Mark N.|author-link2=Mark N. Wegman|year=1979|title=Universal Classes of Hash Functions|journal=Journal of Computer and System Sciences|volume=18|issue=2|pages=143–154|doi=10.1016/0022-0000(79)90044-8|id=Conference version in STOC'77|doi-access=free}}</ref> у 1977 році та знайшла численні застосування в інформатиці (див., {{Nobr|приклад<ref name=Miltersen>{{cite web
 |last = Miltersen
 |first = Peter Bro
 |title = Universal Hashing
 |url = http://www.daimi.au.dk/~bromille/Notes/un.pdf
 |archive-url = https://web.archive.org/web/20110524163440/http://www.daimi.au.dk/~bromille/Notes/un.pdf
 |archive-date = 24 травня 2011
 |access-date = 24 червня 2009
 |url-status = dead
 |df = dmy-all
 }} {{Webarchive|url=https://web.archive.org/web/20170309144737/http://www.daimi.au.dk/~bromille/Notes/un.pdf |date= 9 березня 2017 }}</ref>)}} .

Якщо верхня межа ймовірності колізії <math>\epsilon<1</math>, говорять про <math>\epsilon</math>-майже універсальність. Так, наприклад, універсальне сімейство є <math>1/m</math>-майже універсальним.

Багато, але не всі універсальні родини мають наступну сильнішу '''властивість рівномірної різниці''':

: <math>\forall x,y\in U, ~ x\ne y</math>, коли <math>h</math> вибирається випадковим чином із сімейства <math>H</math>, різниця <math>h(x)-h(y) ~\bmod~ m</math> рівномірно розподілена в <math>[m]</math>.

Слід зауважити, що визначення універсальності стосується лише випадку <math>h(x)-h(y)=0</math>, по якому підраховуються колізії. Властивість рівномірної різниці сильніша.

Аналогічно універсальне сімейство може бути XOR-універсальним, якщо для <math>\forall x,y\in U, ~ x\ne y</math> значення <math>h(x) \oplus h(y) ~\bmod~ m</math> рівномірно розподілене в <math>[m]</math>, де <math>\oplus</math>&nbsp;— операція побітового виключного АБО. Це можливо тільки якщо <math>m</math> є степенем двійки.

Ще сильнішою умовою є {{Iw|попарна незалежність|3=en|4=Pairwise independence}}: коли <math>\forall x,y\in U, ~ x\ne y</math>, то ймовірність, що гешування відобразить <math>x,y</math> у будь-яку пару геш-значень <math>z_1, z_2</math> ніби вони абсолютно випадкові: <math>P(h(x)=z_1 \land h(y)=z_2)= 1/m^2</math>. Попарну незалежність іноді називають сильною універсальністю.

Ще одна властивість&nbsp;— однорідність. Кажуть, що сімейство однорідне, якщо всі геш-значення однаково імовірні: <math>P(h(x)=z)=1/m</math> для будь-якого геш-значення <math>z</math>. Універсальність не означає однорідності. Однак сильна універсальність передбачає однорідність.

Маючи сімейство з властивістю рівномірної відстані, можна створити попарно незалежне або сильно універсальне геш-сімейство шляхом додавання рівномірно розподіленої випадкової константи зі значеннями з <math>[m]</math> до геш-функцій. (Так само, якщо <math>m</math> є степенем двійки, ми можемо досягти попарної незалежності від XOR-універсального геш-сімейства за допомогою операції XOR з рівномірно розподіленою випадковою константою.) Оскільки зсув на константу іноді нерелевантний у програмах (наприклад, геш-таблиці), ретельне розрізнення між властивістю рівномірної відстані та попарною незалежністю іноді не робиться.<ref>
{{Cite book
|title=Randomized Algorithms |last=Motwani
|first=Rajeev
|last2=Raghavan
|first2=Prabhakar
|year=1995
|publisher=Cambridge University Press
|page=221
|isbn=0-521-47465-5
}}
</ref>

Для деяких застосувань (таких як геш-таблиці) важливо, щоб молодші біти геш-значень також були універсальними. Коли сімейство сильно універсальне, це гарантовано: якщо <math>H</math> є сильно універсальним сімейством з <math>m=2^L</math>, то сімейство, що складається з функцій <math>h \bmod{2^{L'}}</math> для усіх <math>h \in H</math>, також є універсальним для <math>L'\leq L</math> . На жаль, це не стосується (просто) універсальних сімейств. Наприклад, сімейство з функції ідентичності <math>h(x)=x</math> є однозначно універсальним, але сімейство, яке складається з функції <math>h(x)=x \bmod{2^{L'}}</math>, не може бути універсальним.

{{Iw|UMAC|3=en}} і {{Iw|Poly1305|Poly1305-AES|en}}, а також кілька інших алгоритмів [[Код аутентифікації повідомлення|кодів автентифікації повідомлень]] базуються на універсальному гешуванні.<ref>
David Wagner, ed.
[https://books.google.com/books?id=11BsCQAAQBAJ «Advances in Cryptology&nbsp;— CRYPTO 2008»].
p. 145.
</ref><ref>
Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen.
[https://books.google.com/books?id=nhPmBQAAQBAJ «The Hash Function BLAKE»].
2014.
p. 10.
</ref> У таких застосуваннях програмне забезпечення вибирає нову геш-функцію для кожного повідомлення на основі унікального [[Криптографічний нонс|довільного числа]] для цього повідомлення.

Кілька реалізацій геш-таблиць засновані на універсальному гешуванні. У таких застосуваннях зазвичай програмне забезпечення вибирає нову геш-функцію лише після того, як помічає, що «забагато» ключів утворюють колізії; до того часу та сама геш-функція продовжує використовуватися знову і знову. (Деякі схеми вирішення колізій, такі як {{Iw|динамічне ідеальне гешування|3=en|4=Dynamic perfect hashing}}, вибирають нову геш-функцію кожного разу, коли виникає колізія. Інші схеми вирішення колізій, такі як [[Зозулине хешування|зозулине гешування]] та {{Iw|гешування з двома варіантами|3=en|4=2-choice hashing}}, допускають кілька колізій перед вибором нової геш-функції). Огляд найшвидших відомих універсальних і сильно універсальних геш-функцій для цілих чисел, векторів і рядків можна знайти в джерелі<ref>
{{Cite arXiv|last=Thorup|first=Mikkel|author-link=Mikkel Thorup|title=High Speed Hashing for Integers and Strings|eprint=1504.06804|year=2015|class=cs.DS}}</ref>.

== Математичні гарантії ==
Для будь-якого фіксованого набору <math>S</math> з <math>n</math> ключів, використання універсального сімейства гарантує такі властивості.

# Для будь-якого фіксованого <math>x</math> у <math>S</math> очікуване число ключів у кошику <math>h(x)</math> дорівнює <math>n/m</math>. При реалізації геш-таблиць методом ланцюжків це число пропорційне очікуваному часу роботи по ключу <math>x</math> (наприклад запиту, вставляння чи видалення).
# Очікуване число пар ключів <math>x,y</math> у <math>S</math> з <math>x\ne y</math>, які утворюють колізію (<math>h(x) = h(y)</math>) обмежене зверху <math>n(n-1)/2m</math>, що є порядком <math>O(n^2/m)</math>. Коли число кошиків <math>m</math> обране лінійно в <math>n</math> (тобто визначене функцією у <math>\Omega(n)</math>), очікуване число колізій становить <math>O(n)</math>. При гешуванні у <math>n^2</math> кошиків з імовірністю не менше 0.5 не існує колізій взагалі.
# Очікуване число ключів <math>x \in S</math>, які утворюють щонайменше <math>t</math> колізій, обмежене зверху як <math>2n/(t-2(n/m)+1)</math>.<ref name="BDP">
{{Cite journal|last=Baran|first=Ilya|last2=Demaine|first2=Erik D.|last3=Pătraşcu|first3=Mihai|author-link3=Mihai Pătrașcu (computer scientist)|year=2008|title=Subquadratic Algorithms for 3SUM|url=http://people.csail.mit.edu/mip/papers/3sum/3sum.pdf|journal=Algorithmica|volume=50|issue=4|pages=584–596|doi=10.1007/s00453-007-9036-3}}</ref> Таким чином, якщо ємність кожного кошика обмежена потрійним середнім розміром (<math>t = 3n/m</math>), загальна кількість ключів у переповнених кошиках не більше <math>O(m)</math>. Це справедливо лише для геш-сімейства, ймовірність колізії якого обмежена згори <math>1/m</math>. Якщо використовується слабше визначення з обмеженням імовірності колізій <math>O(1/m)</math>, результат перестає бути істинним.<ref name="BDP" />

Оскільки наведені вище гарантії справедливі для будь-якого фіксованого набору <math>S</math>, вони зберігаються, якщо набір даних вибрано противником. Однак противник повинен зробити цей вибір до (або незалежно від) випадкового вибору алгоритму геш-функції. Якщо зловмисник може спостерігати за випадковим вибором алгоритму, випадковість не має сенсу, і ситуація така ж, як і з детермінованим гешуванням.

Друга і третя гарантія зазвичай використовуються в поєднанні з {{Iw|Подвійне гешування|перегешуванням|en|Double hashing}}. Наприклад, може бути підготовлений рандомізований алгоритм для обробки деякої кількості <math>O(n)</math> колізій. Якщо він спостерігає занадто багато колізій, він вибирає іншу випадкову <math>h</math> з родини і повторює гешування. Універсальність гарантує, що кількість повторень є [[Геометричний розподіл|геометричною випадковою величиною]].

== Конструкції ==
Оскільки будь-які комп'ютерні дані можуть бути представлені як одне або більше машинних слів, зазвичай потрібні геш-функції для трьох типів [[Область визначення|доменів]]: машинні слова («<nowiki/>[[Ціле число (тип даних)|цілі числа]]<nowiki/>»); вектори [[Машинне слово|машинних слів]] фіксованої довжини; і вектори змінної довжини («[[Рядок (програмування)|рядки]]»).

=== Гешування цілих чисел ===
У цьому розділі розглядається випадок гешування цілих чисел, які вписуються в машинні слова; таким чином, такі операції, як множення, додавання, ділення тощо, є дешевими машинними інструкціями. Нехай універсум, що гешується <math>\{0, \dots, |U| - 1\}</math>.

Початкова пропозиція Картера і Вегмана<ref name="CW77"/> полягала у виборі простого числа <math>p \ge |U|</math> і визначенні

: <math> h_{a,b}(x) = ((ax + b)~\bmod ~ p)~\bmod ~ m</math>

де <math>a,b</math> випадково вибрані цілі числа за модулем <math>p</math> з <math>a \neq 0</math> . (Це одна ітерація [[Лінійний конгруентний метод|лінійного конгруентного генератора]].)

Щоб побачити, що <math>H = \{ h_{a,b} \}</math> є універсальним сімейством, слід зауважити, що <math>h(x) = h(y)</math> виконується лише коли

: <math>ax+b \equiv ay + b + i\cdot m \pmod{p}</math>

для деякого цілого числа <math>i</math> між <math>0</math> і <math>(p-1)/m</math> . Оскільки <math>p \ge |U|</math>, якщо <math>x \neq y</math> їх різниця <math>x-y</math> не дорівнює нулю і має [[Обернене за модулем число|оберенене за модулем]] <math>p</math> число. Розв'язання для <math>a</math>

: <math>a \equiv i\cdot m \cdot (x-y)^{-1} \pmod{p}</math> .

Існує <math>p-1</math> можливих варіантів для <math>a</math> (оскільки <math>a=0</math> виключається) і, варіюючи <math>i</math> в допустимому діапазоні, можливо отримати <math>\lfloor (p - 1)/m \rfloor</math> ненульових значень для правої частини. Таким чином, ймовірність колізії дорівнює

: <math>\lfloor (p - 1)/m \rfloor / (p-1) \le ((p-1)/m)/(p-1) = 1/m</math> .

Інший спосіб побачити, що <math>H</math> є універсальним сімейством використовує поняття {{Iw|статистична відстань|статистичної відстані|en|Statistical distance}}. Різницю <math>h(x) - h(y)</math> можна переписати як

: <math>h(x)-h(y) \equiv (a(x-y)~ \bmod~ p) \pmod{m}</math> .

Оскільки <math>x - y</math> не дорівнює нулю і <math>a</math> рівномірно розподіляється в <math>\{1,\dots,p-1\}</math>, з цього випливає, що <math>a(x-y)</math> по модулю <math>p</math> також рівномірно розподіляється в <math>\{1,\dots,p-1\}</math>. Розподіл <math>(h(x)-h(y)) ~\bmod~ m</math> таким чином є майже рівномірним, аж до різниці в ймовірності <math>\pm 1/p</math> між зразками. У результаті статистична відстань до однорідної родини становить <math>O(m/p)</math>, яка стає незначною, коли <math>p \gg m</math>.

Сімейство простіших геш-функцій

: <math>h_a(x) = (ax~\bmod~p)~\bmod~m</math>

є лише ''приблизно'' універсальним: <math>\Pr\{h_a(x) = h_a(y)\} \le 2/m</math> для усіх <math>x\neq y</math>.<ref name="CW77"/> Крім того, цей аналіз є майже строгим; Картер і Вегман<ref name="CW77" /> показують що <math>\Pr\{h_a(1) = h_a(m+1)\} \ge 2/(m-1)</math> будь-коли <math>(p-1)~\bmod~ m = 1</math> .

==== Уникнення модульної арифметики ====
Найсучаснішим для гешування цілих чисел є схема '''множення-зсуву,''' описана Діцфельбінгером та ін. у 1997&nbsp;р.<ref name="DHKP97">
{{Cite journal|last=Dietzfelbinger|first=Martin|last2=Hagerup|first2=Torben|last3=Katajainen|first3=Jyrki|last4=Penttonen|first4=Martti|year=1997|title=A Reliable Randomized Algorithm for the Closest-Pair Problem|url=http://www.diku.dk/~jyrki/Paper/CP-11.4.1997.ps|format=Postscript|journal=Journal of Algorithms|volume=25|issue=1|pages=19–51|doi=10.1006/jagm.1997.0873|access-date=10 лютого 2011}}</ref> Завдяки уникненню [[Модульна арифметика|модульної арифметики]] цей метод набагато легше реалізувати, а також він працює значно швидше на практиці (зазвичай щонайменше в чотири рази<ref>
{{Cite web|url=http://mybiasedcoin.blogspot.com/2009/12/text-book-algorithms-at-soda-guest-post.html|title=Text-book algorithms at SODA|last=Thorup|first=Mikkel|authorlink1=Mikkel Thorup|date=18 грудня 2009}}</ref>). Схема припускає, що кількість кошиків є ступенем двійки, <math>m=2^M</math>. Нехай <math>w</math> буде кількістю бітів у машинному слові. Потім геш-функції параметризуються над непарними додатними цілими числами <math>a < 2^w</math> (що вписується в одне <math>w</math>-бітове слово). Щоб оцінити <math>h_{a}(x)</math>, слід помножити <math>x</math> на <math>a</math> по модулю <math>2^w</math> а потім зберегти старші <math>M</math> бітів як геш-код. У математичній нотації це

: <math>h_a(x) = (a\cdot x\,\, \bmod\, 2^w)\,\, \mathrm{div}\,\, 2^{w-M} .</math>

Ця схема ''не'' задовольняє властивості рівномірної різниці і є єдиною ''<math>2/m</math> -майже універсальною''; для будь-якого <math>x\neq y</math>, <math>\Pr\{h_a(x) = h_a(y)\} \le 2/m</math>.

Щоб зрозуміти поведінку геш-функції, зауважимо, що якщо <math>ax \bmod 2^w</math> і <math>ay\bmod 2^w</math> мають однакові старші ''M'' бітів, тоді <math>a(x-y) \bmod 2^w</math> має всі одиниці або всі нулі у старших ''M'' бітах (залежно від того, що більше: <math>ax \bmod 2^w</math> чи <math>ay \bmod 2^w</math>). Припустимо, що набір молодших бітів <math>x-y</math> з'являється на позиції <math>w-c</math>. Через те, що <math>a</math> є випадковим непарним цілим числом, а непарні цілі числа мають обернені значення у [[Кільце (алгебра)|кільці]] <math>Z_{2^w}</math>, слідує, що <math>a(x-y)\bmod 2^w</math> буде рівномірно розподілено серед <math>w</math>-бітових цілих чисел з молодшим установленим бітом на позиції <math>w-c</math>. Таким чином, імовірність того, що всі ці біти складаються з 0 або 1, не перевищує <math>2/2^M=2/m</math>.

З іншого боку, якщо <math>c < M</math>, тоді старші M бітів <math>a(x-y) \bmod 2^w</math> містять і 0, і 1, тому <math>h(x) \ne h(y)</math>. Насамкінець, якщо <math>c=M</math> то біт <math>w-M</math> значення <math>a(x-y) \bmod 2^w</math> є 1, і <math>h_a(x)=h_a(y)</math> тоді і тільки тоді, коли біти <math>w-1,\ldots,w-M+1</math> також є 1, що відбувається з імовірністю <math>1/2^{M-1}=2/m</math>.

Цей аналіз є строгим, як можна показати на прикладі <math>x=2^{w-M-2}</math> і <math>y=3x</math>. Щоб отримати дійсно «універсальну» геш-функцію, можна використати схему множення-додавання-зсуву, яка вибирає старші біти

: <math>h_{a,b}(x) = ((ax + b) \bmod 2^{w+M})\, \mathrm{div}\, 2^w ,</math>

де <math>a</math> є випадковим натуральним числом з <math>a < 2^{2w}</math> і <math>b</math> є випадковим невід'ємним цілим числом з <math>b < 2^{2w}</math>. Для цього потрібно виконувати арифметику <math>2w</math> -розрядних беззнакових цілих чисел. Ця версія множинного зсуву належить Діцфельбінгеру, а пізніше була більш точно проаналізована Вельфелем.<ref name="w992">{{cite conference|last1=Woelfel|first1=Philipp|title=Efficient Strongly Universal and Optimally Universal Hashing|conference=Mathematical Foundations of Computer Science 1999|series=LNCS|volume=1672|pages=262–272|doi=10.1007/3-540-48340-3_24|year=1999}}</ref>

=== Гешування векторів ===
Цей розділ стосується гешування вектора машинних слів фіксованої довжини. Вхідні дані інтерпретуються як вектор <math>\bar{x} = (x_0, \dots, x_{k-1})</math> з <math>k</math> машинних слів (цілі числа по <math>w</math> бітів кожне). Якщо <math>H</math> є універсальним сімейством з властивістю рівномірної різниці, наступне сімейство (походить від Картера і Вегмана<ref name="CW77"/>) також має властивість рівномірної різниці (і, отже, є універсальним):

: <math>h_{\bar{a}}(\bar{x}) = \left(\big( \sum_{i=0}^{k-1} x_i \cdot a_i \big) ~\bmod ~ 2^{2w} \right) \,\, \mathrm{div}\,\, 2^{2w-M}</math> .

Якщо <math>m</math> є степенем двійки, підсумовування можна замінити виключним або.<ref name="thorup09">
{{Cite conference|authorlink=Mikkel Thorup|isbn=978-0-89871-680-1}}, section 5.3
</ref>

На практиці, якщо доступна арифметика подвійної точності, вона створюється за допомогою сімейства геш-функцій із множним зсувом.<ref name="DGMP2">{{cite conference|last1=Dietzfelbinger|first1=Martin|last2=Gil|first2=Joseph|last3=Matias|first3=Yossi|last4=Pippenger|first4=Nicholas|title=Polynomial Hash Functions Are Reliable (Extended Abstract)|work=Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP)|pages=235–246|year=1992}}</ref> Якщо ніціалізувати геш-функцію вектором <math>\bar{a} = (a_0, \dots, a_{k-1})</math> випадкових '''непарних''' цілих чисел по <math>2w</math> бітів кожне, тоді, якщо кількість кошиків дорівнює <math>m=2^M</math> для <math>M\le w</math> :

: <math>h_{\bar{a}}(\bar{x}) = \left(\Big( \sum_{i=0}^{\lceil k/2 \rceil} (x_{2i} + a_{2i}) \cdot (x_{2i+1} + a_{2i+1}) \Big) \bmod ~ 2^{2w} \right) \,\, \mathrm{div}\,\, 2^{2w-M}</math> .

Можна вдвічі зменшити кількість множень, що на практиці приблизно означає подвійне прискорення.<ref name="thorup09"/> Якщо ніціалізувати геш-функцію вектором <math>\bar{a} = (a_0, \dots, a_{k-1})</math> випадкових '''непарних''' цілих чисел на <math>2w</math> біти кожне, то наступне сімейство геш-функцій є універсальним:<ref name="black2">{{cite conference|last1=Black|first1=J.|last2=Halevi|first2=S.|last3=Krawczyk|first3=H.|last4=Krovetz|first4=T.|title=UMAC: Fast and Secure Message Authentication|work=Advances in Cryptology (CRYPTO '99)|year=1999|url=http://www.cs.ucdavis.edu/~rogaway/papers/umac-full.pdf}}, Equation 1</ref>

: <math>h_{\bar{a}}(\bar{x})^{\mathrm{strong}} = (a_0 + \sum_{i=0}^{k-1} a_{i+1} x_{i}  \bmod ~ 2^{2w} ) \,\, \mathrm{div}\,\, 2^w </math> .

Якщо операції подвійної точності недоступні, можна інтерпретувати вхідні дані як вектор півслів (<math>w/2</math> -розрядні цілі числа). Далі буде використовуватися алгоритм <math>\lceil k/2 \rceil</math> множення, де <math>k</math>&nbsp;— кількість півслів у векторі. Таким чином, алгоритм працює зі швидкістю одного множення на вхідне слово.

Цю ж схему також можна використовувати для гешування цілих чисел, інтерпретуючи їхні біти як вектори байтів. У цьому варіанті векторна техніка відома як {{Iw|табуляційне гешування|3=en|4=Tabulation hashing}} та забезпечує практичну альтернативу універсальним схемам гешування на основі множення.<ref>{{Cite conference|isbn=9781450306911}}</ref>

Також можлива сильна універсальність на високій швидкості.<ref name="kaser2013">{{Cite journal|last=Kaser|first=Owen|last2=Lemire|first2=Daniel|year=2013|title=Strongly universal string hashing is fast|journal=Computer Journal|publisher=Oxford University Press|volume=57|issue=11|pages=1624–1638|arxiv=1202.4961|doi=10.1093/comjnl/bxt070}}</ref> Потрібно ініціалізувати геш-функцію вектором <math>\bar{a} = (a_0, \dots, a_{k})</math> випадкових цілих чисел на <math>2w</math> бітів. Обчислити

: <math>h_{\bar{a}}(\bar{x})^{\mathrm{strong}} = (a_0 + \sum_{i=0}^{k-1} a_{i+1} x_{i}  \bmod ~ 2^{2w} ) \,\, \mathrm{div}\,\, 2^w </math> .

Результат сильно універсальний на <math>w</math> бітах. Експериментально було встановлено, що він працює на швидкості на 0,2 цикла процесора на байт на останніх процесорах Intel для <math>w = 32</math>.

=== Гешування рядків ===
Це стосується гешування вектора машинних слів ''змінного розміру''. Якщо довжину рядка можна обмежити невеликим числом, найкраще використовувати векторне рішення зверху (концептуально доповнюючи вектор нулями до верхньої межі). Потрібний простір&nbsp;— це максимальна довжина рядка, але час для оцінки <math>h(s)</math> це просто довжина <math>s</math>. Поки нулі заборонені в рядку, доповнення нулями можна ігнорувати під час оцінювання геш-функції без впливу на універсальність.<ref name="thorup09"/> Слід зауважити, що якщо в рядку дозволені нулі, тоді, можливо, найкраще буде додати фіктивний ненульовий символ (наприклад, 1) до всіх рядків перед доповненням: це гарантує, що це не вплине на універсальність.<ref name="kaser2013"/>

Тепер припустимо, що ми хочемо гешувати <math>\bar{x} = (x_0,\dots, x_\ell)</math>, де гарна межа <math>\ell</math> апріорі невідома. Універсальне сімейство, запропоноване<ref name="DGMP3">{{cite conference|last1=Dietzfelbinger|first1=Martin|last2=Gil|first2=Joseph|last3=Matias|first3=Yossi|last4=Pippenger|first4=Nicholas|title=Polynomial Hash Functions Are Reliable (Extended Abstract)|work=Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP)|pages=235–246|year=1992}}</ref>, розглядає рядок <math>x</math> як коефіцієнти полінома за модулем великого простого числа. Якщо <math>x_i \in [u]</math>, прийняти просте число <math>p \ge \max \{ u, m \}</math> і визначити:

: <math>h_a(\bar{x}) = h_\mathrm{int} \left( \big(\sum_{i=0}^\ell x_i\cdot a^{\ell-i} \big) \bmod ~p \right)</math>, де <math>a \in [p]</math> є рівномірно випадковим і <math>h_\mathrm{int}</math> вибирається випадковим чином із універсального сімейства, що відображає: цілі числа <math>[p] \mapsto [m]</math> .

Використовуючи властивості модульної арифметики, наведене вище можна обчислити без отримання великих чисел для великих рядків, як показано нижче:<ref>{{Cite web|url=http://www.cs.huji.ac.il/course/2002/dast/slides/tirgul9.pdf|title=Hebrew University Course Slides}}</ref><syntaxhighlight lang="C">
uint hash(String x, int a, int p)
	uint h = INITIAL_VALUE
	for (uint i=0 ; i < x.length ; ++i)
		h = ((h*a) + x[i]) mod p
	return h
</syntaxhighlight>

Цей [[Коткий геш|коткий геш Рабіна-Карпа]] базується на [[Лінійний конгруентний метод|лінійному конгруентному генераторі]].<ref>
Robert Uzgalis.
[http://www.serve.net/buz/hash.adt/java.002.html «Library Hash Functions»].
1996.
</ref> Наведений вище алгоритм також відомий як ''мультиплікативна геш-функція''.<ref>{{Cite web|url=http://www.strchr.com/hash_functions|title=Hash functions: An empirical comparison|last=Kankowsk|first=Peter}}</ref> На практиці оператора ''mod'' і параметра ''p'' можна взагалі уникнути, просто дозволивши цілочисельне переповнення, оскільки це еквівалентно ''mod'' (''Max-Int-Value'' + 1) у багатьох мовах програмування. У таблиці нижче показано значення, вибрані для ініціалізації ''h'' і a для деяких популярних реалізацій.
{| class="wikitable"
!Реалізація
! Початкове значення
! a
|-
| геш-функція [[Даніель Джуліус Бернштайн|Бернштайна]] ''djb2''<ref>{{Cite web|url=http://www.cse.yorku.ca/~oz/hash.html|title=String hash functions|last=Yigit|first=Ozan}}</ref>
| 5381
| 33
|-
| STLPort 4.6.2
| 0
| 5
|-
| геш-функція [[Браян Керніган|Кернігана]] та [[Денніс Рітчі|Річі]]<ref>{{Cite book
|title=The C Programming Language |last=Kernighan; Ritchie
|year=1988
|publisher=Prentice Hall
|edition=2nd
|pages=[https://archive.org/details/cprogramminglang00bria/page/118 118]
|chapter=6
|isbn=0-13-110362-8
}}</ref>
| 0
| 31
|-
| java.lang.String.hashCode() <ref>{{Cite web|url=http://docs.oracle.com/javase/6/docs/api/java/lang/String.html#hashCode()|title=String (Java Platform SE 6)|website=docs.oracle.com|access-date=2015-06-10}}</ref>
| 0
| 31
|}
Розглянемо два рядки <math>\bar{x}, \bar{y}</math> і нехай <math>\ell</math> бути довжиною довшого; для аналізу коротший рядок концептуально доповнюється нулями до довжини <math>\ell</math> . Колізія при застосуванні <math>h_\mathrm{int}</math> означає, що <math>a</math> є коренем многочлена з коефіцієнтами <math>\bar{x} - \bar{y}</math>. Цей многочлен має не більше <math>\ell</math> коренів по модулю <math>p</math>, тому ймовірність колізії не більше <math>\ell/p</math>. Імовірність колізії через випадковість <math>h_\mathrm{int}</math> доводить загальну ймовірність колізії до <math>\frac{1}{m} + \frac{\ell}{p}</math>. Таким чином, якщо просте <math>p</math> є достатньо великим порівняно з довжиною гешованих рядків, сімейство дуже близько до універсального (за статистичною відстанню).

Інші універсальні сімейства геш-функцій, які використовуються для гешування рядків невідомої довжини до геш-значень фіксованої довжини, включають [[Відбитки пальців Рабіна|відбиток Рабіна]] та [[Коткий геш|Бужаш]].

==== Уникнення модульної арифметики ====
Щоб пом'якшити обчислювальні витрати від модульної арифметики, на практиці використовуються три прийоми:<ref name="thorup09"/>

# Обирається просте <math>p</math>, близьке до степеня двійки, наприклад {{Iw|просте число Мерсенна|просте число Мерсенна|en|Mersenne prime}}. Це дозволяє арифметику по модулю <math>p</math> реалізувати без ділення (з використанням швидших операцій, таких як додавання та зсув). Наприклад, на сучасних архітектурах можна працювати з <math>p = 2^{61}-1</math>, поки <math>x_i</math> є 32-розрядними значеннями.
# До блоків можна застосувати векторне гешування. Наприклад, можна застосувати гешування векторів до кожного блоку з 16 слів рядка, а також застосувати гешування рядка до <math>\lceil k/16 \rceil</math> результатів. Оскільки повільніше гешування рядків застосовується до значно меншого вектора, загальна швидкість, по суті, буде така ж, як і швидкість гешування векторів.
# Дільником вибирається ступінь двійки, що дозволяє виконувати арифметичні дії за модулем <math>2^w</math> без ділення (з використанням швидших операцій [[Маскування (програмування)|маскування бітів]]). {{Iw|UMAC|Сімейство геш-функцій NH|en}} використовує цей підхід.

== Див. також ==

* {{Iw|K-independent hashing|3=en}}
* [[Коткий геш]]
* {{Iw|Tabulation hashing|3=en}}
* {{Iw|Min-wise independence|3=en}}
* {{Iw|Universal one-way hash function|3=en}}
* [[Послідовність із низькою розбіжністю]]
* {{Iw|Perfect hashing|3=en}}

== Примітки ==
{{примітки}}

== Подальше читання ==

* {{Cite book
|title=The Art of Computer Programming, Vol. III: Sorting and Searching
|last=Knuth
|first=Donald Ervin
|authorlink1=Donald Knuth
|year=1998
|publisher=Addison-Wesley
|edition=3rd
|location=Reading, Mass; London
|isbn=0-201-89685-0
}}

== Посилання ==

* [http://opendatastructures.org/versions/edition-0.1e/ods-java/5_1_ChainedHashTable_Hashin.html#SECTION00811000000000000000 Відкриті структури даних&nbsp;— Розділ 5.1.1&nbsp;— Мультиплікативне гешування], {{Iw|Пет Морін|3=en|4=Pat Morin}}

[[Категорія:Теорія складності обчислень]]
[[Категорія:Алгоритми пошуку]]
[[Категорія:Хешування]]
[[Категорія:Криптографічні геш-функції]]
[[Категорія:Сторінки з неперевіреними перекладами]]