Концепция универсального хеширования была предложена в [1]. Целью является генерация случайной хеш-функции $ h $, отображающей пространство ключей¹⁾ $ \mathbb U $ во множество $[m]:=\{0,1,\dots, m-1\}$. Мы считаем $ h $ случайной переменной из некоторого распределения всевозможных функций из $ \mathbb U $ в $[m]$. Желательно, чтобы функция была универсальной в том смысле, что для любых различных $ x $ и $ y $ из $ \mathbb U $ при случайном выборе $ h $ выполнялась следующая оценка для вероятности коллизии $$ \Pr (h(x)=h(y)) \le \frac{1}{m} \, . $$

Примером классической универсальной хеш-функции является функция из $[u]:=\{0,1,\dots,u-1\} $ в $ [m] $. Предполагается, что $u>m>1 $. Фиксируется простое число $ p \ge m $ и случайным образом выбираются числа $ a \ne 0 $ и $ b $ из $[p]$. Универсальная хеш-функция определяется как $$ h_{a,b}(x):= ((ax+b) \pmod{p}) \pmod{m} \, . $$

Теорема.

$$ \Pr_{\{a,b\}\in [p]} (h_{a,b}(x)=h_{a,b}(y)) < \frac{1}{m} \, . $$

Пример. $ p=31, a=7,b=15 $

$$ \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} x & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & \dots \\ \hline 7x+15 \pmod{31} & 22 & 29 & 5 & 12 & 19 & 26 & 2 & 9 & 16 & 23 & 30 & 6 & 13 & \dots \end{array} $$

Вычислительная проблема заключается в реализации операции модулярного умножения $ ax \pmod{p} $ при больших $ p $. Что предлагается? — В качестве $ p $ брать числа из специального класса. Так, для простых чисел Мерсенна, т.е. чисел вида $ p=2^q-1 $, имеет место $$ z \pmod{p} = \{z \pmod{2^q} + \lfloor z/2^q \rfloor \} \pmod p \, . $$ В $ \{ \cdot \} $ стоят сумма остатка и частного от деления $ z $ на $ 2^q $.

Пример. Для $p=31=2^5-1 $ и $ z= 328 $

Имеем $q=5 $ и $$ \lfloor z/2^q \rfloor =10, \quad \Rightarrow \quad z \pmod{2^q} = z- 320=8 \, . $$ $$328 \equiv 18 \pmod{31}\, .$$ А если $ z $ перегнать в двоичную систему, то вообще всё упростится: $$ \underline{328}_{_{10}} = \underline{101001000}_{_2} \quad \Rightarrow \quad \{z \pmod{2^5} + \lfloor z/2^5 \rfloor \} = \underline{1010}_{_2}+\underline{01000}_{_2}=\underline{10010}_{_2}= \underline{18}_{_{10}} \, . $$ ♦

Еще одним примером универсальной хеш-функции, отображающей $ w $-битное число в $ \ell $-битное является $$ h_a(x):=\lfloor (ax \pmod{2^w})/2^{w-\ell} \rfloor $$ при выборе случайного $w$-битного нечетного числа $ a $.

Если строка состоит из $ k $ чисел $ x_1,\dots,x_k $ из $[u]$ и мы хотим построить $k$-независимый случайный хеш $H$ такой, чтобы все величины $ H(x_1),\dots,H(x_k)$ были независимыми случайными переменными, то подходящим кандидатом является полиномиальное отображение $$ H(x)= \sum_{j=0}^{k-1} a_j x^j \pmod{p} \, . $$ Здесь коэффициенты $a_0,\dots,a_{k-1} $ из $[p]$ выбираются случайным образом.

[1]. Carter L., Wegman M. N. Universal Classes of Hash Functions. Journal of Computer and System Sciences. 1979. Vol. 18, no. 2. P. 143—154

[2]. Thorup M. High Speed Hashing for Integers and Strings. ArXiv 09.05.2020