Универсальное хеширование¶

Универсальное хеширование позволяет генерировать случайную хеш-функцию, обеспечивающую равномерное распределение значений хешей

Формальный критерий¶

$U$ - множество ключей
$\mathfrak{H}$ - множество хеш-функций, отображающих $U$ в $\{0..m-1\}$
при случайном выборе хеш-функции вероятность коллизии двух ключей не превышает вероятность коллизии двух случайно выбранных значений из множества $\{0..m-1\}$ , $1/m$

Для того, чтобы последнее было верно, количество функций $h \in \mathfrak{H}$ , для которых $h(k) = h(l)$ , не должно превышать $|\mathfrak{H}|/m$

Матожидание времени выполнения операций¶

Для универсального хеширования при использовании метода цепочек время выполнения операций $n$ любых операций равно $\Theta(n)$

Как реализовать подобный алгоритм¶

Хеш-функция принимает 1 аргумент. Поскольку для реализации неудобно хранить полный набор всех хеш-функций, нужны правила, по которым хеш-функция будет параметризоваться, либо при инстанцировании, либо другим способом.

Универсальная хеш-функция параметризуется двумя случайными параметрами $a, b$ , а также простым числом $p$ таким, что максимальный ключ $leq p-1$ :

h_{a b} (k) = ((a \cdot k + b) m o d p) m o d m)

$h_{ab}(k) = ((a \cdot k + b)\ mod\ p)\ mod\ m)$

Пример на псевдо-python

class UniversalHash:
    def __init__(self, max_key, m):  # конструктор
        self._m = m
        self._p = self.generate_prime_greater_than(max_key)
        self._a = random.randint(0, self.p)
        self._b = random.randint(1, self.p)

    def hash(self, key):  # self - указатель на сам объект
        return (((self._a * key + self._b)
                 % self._p)
                % self._m)

    def generate_prime_greater_than(self, max_key):
        ...
        return p

При инстанцировании hash_fn = UniversalHash(max_key, m) вычисляется параметр $p$ и случайным образом выбираются два параметра $a, b$ . При вызове метода hash_fn.hash(key) будут создаваться значения хешей, соответсующие требованию вероятности коллизий не более $1/m$ .

Фактически, класс UniversalHash описывает построение универсального класса (или множества) хеш-функций. Осталось только разобраться в генерации параметров $a, b$ и наложенных на них ограничениях, а так же разобраться в корректности работы алгоритма.

Алгоритм построения универсального класса хеш-функций¶

$p$ должно быть простым и максимально возможный ключ $\leq p-1$ , как было сказано выше
$a \in Z_p^*$ , где $Z_p^* = \{1..p-1\}$ , выбирается случайным образом из равномерного распределения
$b \in Z_p$ , где $Z_p = \{0..p-1\}$ , аналогично $a$

( $Z$ это множество целых чисел)

Например, если максимальный ключ - $32$ , $p = 37$ , мы выбираем случайным образом $a$ и $b$ из множеств $\{0..36\},\ \{1..36\}$ .

В этом случае хеш-функция равна, например,

h_{21, 13} (k) = ((21 \cdot k + 13) m o d 37) m o d m)

$h_{21,13}(k) = ((21 \cdot k + 13)\ mod\ 37)\ mod\ m)$

Если размер таблицы равен $16$ , мы получим такие значения:

$h_{21,13}(1) = 2$
$h_{21,13}(2) = 2$
$h_{21,13}(3) = 2$
$h_{21,13}(4) = 7$
$h_{21,13}(5) = 7$
$h_{21,13}(6) = 12$
...
$h_{21,13}(32) = 3$

Для некоторых значений количество коллизий для конкретной хеш-функции может быть больше, для некоторых - меньше, но в среднем будет $1/m$ , и сейчас мы докажем это.

Доказательство универсальности¶

$\mathfrak{H}_{pm} = \{h_{ab}: a \in Z_p^*, b \in Z_p\}$ - множество универсальных хеш-функций для всех ключей меньше $p$ и таблицы размера $m$

(на практике $p$ может быть равно, например, простому числу $> int32$ и т.д., а $m$ - любому размеру таблицы, так как данный метод не накладывает на размер таблиц дополнительных ограничений)

В этом множестве существует $p \cdot (p-1)$ возможных хеш-функций (т.к. есть $p-1$ вариантов выбора $a$ и $p$ вариантов выбора $b$ ).

Для двух ключей $k,l \in Z_p, k \neq l$ , и определенной $h_{ab}$ , "внутреннее" отображение $f: Z_p \rightarrow Z_p$ будет таким:

r = (a \cdot k + b) m o d p

$r = (a \cdot k + b)\ mod\ p$

s = (a \cdot l + b) m o d p

$s = (a \cdot l + b)\ mod\ p$

фактически, любой ключ из $\{0..p-1\}$ изменяется и переходит в то же множество $\{0..p-1\}$

Вычтем $s$ из $r$ :

r - s \equiv a \cdot (k - l) (m o d p)

$r - s \equiv a \cdot (k-l) (mod\ p)$

Покажем, что для любой пары $k,l, k \neq l$ также верно $r \neq s$ . Это верно, поскольку $p$ - простое число, следовательно, $a$ и $(k - l)$ отличны от нуля по модулю $p$ , и их произведение также отлично от нуля по модулю $p$ .

мы можем вычитать $(k-l)$ , предполагая без потери общности, что $k-l>0$ всегда, поскольку можем выбирать имена переменных произвольно.

Итак, коллизии для произвольной (поскольку $a,b$ выбирались случайно и проивзольно) функции $h_ab$ из множества $\mathfrak{H}$ не могут случиться.

Далее, можно показать, что "внутреннее" отображение $f: Z_p \rightarrow Z_p$ биективно. Тогда из биективности отображения $f$ и пары случайного равновероятного выбора $a, b$ из $Z_p$ следует, что $s, r$ случайно и равномерно распределенные переменные.

Каждая из возможных $p \cdot (p-1)$ пар $a,b$ может быть найдена по значениям ключей $k,l$ и паре $s, r$ (и $p$ ) однозначно:

r = (a \cdot k + b) m o d p

$r = (a \cdot k + b)\ mod\ p$

b = (r - a \cdot k) m o d p

$b = (r - a \cdot k)\ mod\ p$

можно выразить $a$ без использования $b$ :

r - s = a \cdot (k - l) (m o d p)

$r - s = a \cdot (k-l) (mod\ p)$

a = ((r - s) (k - l)^{- 1} m o d p) m o d p

$a = ((r - s) (k - l)^{-1}\ mod\ p)\ mod\ p$

$(k - l)^{-1}$ - число, обратное $(k - l)$ по модулю; то есть $(k-l)\cdot (k-l)^{-1}\equiv 1 (mod\ m)$

из этого можно сделать вывод, что каждая пара $a, b$ дает различные пары $r,s$ .

Количество пар $a,b$ и $r,s$ одинаково и равно $p \cdot (p-1)$ ; отсюда и появляется биективность отображения из множества пар $a, b$ в множество пар $r,s$ .

Итак, пара $r,s$ с равной вероятностью может быть любой из пар с различающимися по модулю $p$ значениями, что следует из биективности отображения и характера выбора чисел $a$ и $b$ .

Осталось только показать, что вероятность коллизии значений после взятия модуля по $m$ не превышает $1/m$ .

Эта вероятность будет равна вероятности совпадения значений $r$ и $s$ по модулю $m$ : $r \equiv s\ (mod\ m)$ .
Если зафиксировать $r$ , останется $p-1$ возможных значений $s$ . Из них по $s$ , совпадающих по модулю с $r$ , будет не больше, чем $\lceil p/m \rceil - 1$ .

так происходит потому, что поскольку по модулю $m$ может совпадать не более, чем каждое $m$ -тое число, и надо посчитать количество возможных интеровалов размера $m$ , округлить значение вверх и вычесть единицу (1 интеравал будет неполным)

⌈ p / m ⌉ - 1 \leq ((p + m - 1) / m) - 1 = (p - 1) / m

$\lceil p/m \rceil - 1 \leq ((p+m-1)/m) - 1 = (p-1)/m$

Поделив это значение на количество возможных $s$ , получим вероятность коллизии:

((p - 1) / m) / (p - 1) = 1 / m

$((p-1)/m) / (p-1) = 1 / m$

Итак, было показано, что для любой пары $k,l$ и для любой случайно выбранной функции $h_{ab} \in \mathfrak{H_{pm}}$ вероятность коллизии равна $1/m$ , то есть множество функций $\mathfrak{H+{pm}}$ является универсальным.

Применение¶

Этот алгоритм будет применен далее как основа алгоритма создания идеальной хеш-функции для заранее известного набора данных

Некоторые правила работы с округлением вверх и вниз¶

Краткий список основных формул (без доказательств):

$x-1 < \lfloor x \rfloor \leq x \leq \lceil x \rceil < x + 1$ для действительных x
$\lfloor n/2 \rfloor + \lceil n/2 \rceil = n$ для любого целого n
для любого действительного и целых положительных :
- $\lfloor \lfloor x/a \rfloor /b \rfloor = \lfloor x/ab \rfloor$
- $\lceil \lceil x/a \rceil /b \rceil = \lceil x/ab \rceil$
- $\lfloor a/b \rfloor \geq (a - (b-1)) / b$
- $\lceil a/b \rceil \leq (a + (b-1)) / b$

</font>

в начало