Идеальное хеширование

Определение:

Идеальная хеш-функция — хеш-функция, которая без коллизий отображает различные элементы из множества объектов на множество ключей за $O(1)$ времени в худшем случае.

Практический смысл

Задача идеального хеширования возникает тогда, когда возникает необходимость проверять наличие элемента (скажем, слова из словаря) за гарантировано константное время. При этом подразумевается, что набор данных в таблице статичен либо изменяется очень редко.

Основная идея

Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.

Первый уровень

Используется тот же принцип, что и в случае хеширования с цепочками: $n$ ключей хешируются в $m$ ячеек с использованием хеш-функции $h$, выбранной из семейства универсальных хеш-функций. Сама хеш-функция будет иметь вид $h(k) = ((a\cdot k+b) \bmod p)$.

Второй уровень

На данном уровне будет использовать вторичную хеш-таблицу $S_j$ со своей функций $h_j$. $S_j$ будет хранить все ключи, хешированные в ячейку $j$. Соответственно, хеш-функция будет вида $h_j((a_j\cdot k + b_j) \bmod p) \bmod m_j$.

Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе. Но для того, чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер $m_j$ хеш-таблицы $S_j$ был равен квадрату числа $n_j$ ключей, хешированных в ячейку $j$.

Метод №1

Будем использовать $O(n^2)$ памяти.

Теорема:

Если $n$ ключей сохраняются в хеш-таблице размером $m=n^2$ c использованием хеш-функции $h$, случайно выбранный из универсального множества хеш-функций, то вероятность возникновения коллизий не превышает ${1 \over 2}$.

Доказательство:

$\triangleright$

Всего имеется $\dbinom{n}{2}$ пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из универсального семейства хеш-функций $H$, то для каждой пары вероятность возникновения коллизии равна ${1 \over m}$. Пусть $X$ — случайная величина, которая подсчитывает количество коллизий. Если $m = n^2$, то математическое ожидание числа коллизий равно $E[X] =$ $\binom{n}{2} \cdot {1 \over n^2} = {n^2-n \over n} \cdot {1 \over n^2} \lt {1 \over 2}$

$\triangleleft$

Это является очень хорошим результатом, если хотя бы вспомнить на примере парадокса дней рождения о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.

Метод №2

Будем использовать $O(n)$ памяти.

Теорема:

Если мы сохраняем $n$ ключей в хеш-таблице в хеш-таблице размеров $m=n$ c использованием хеш-функции $h$, выбираемой случайным образом из универсального множества хеш-функций, то $E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] \lt 2n$, где $n_j$ — количество ключей, хешированных в ячейку $j$.

Доказательство:

$\triangleright$

$E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] =$ $E\left[ \displaystyle \sum_{j=0}^{m-1} (n_j + 2 \dbinom{n_j}{2})\right] =$ $E\left[ \displaystyle \sum_{j=0}^{m-1} n_j\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\right] =$ $E\left[n\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\right] = n + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2} \right]$ Первый переход в равенстве мы совершили благодаря формуле $a^2 = a + 2\cdot\dbinom{a}{2}$. Далее мы воспользовались свойствами математического ожидания, в частности - линейности. Очевидно, что $\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}$ - просто общее количество коллизий, поэтому по свойству универсального хеширования математическое ожидание значения этой суммы не превышает $\binom{n}{2}{1 \over m} = {n(n-1) \over 2m} = {n-1 \over 2}$ А так как $m = n$, то $E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] \leqslant$ $n + 2 \cdot {n-1 \over 2} = 2n - 1 \lt 2n$, ч.т.д.

$\triangleleft$

Теперь выведем 2 следствия из этой теоремы.

Теорема:

Если мы сохраняем $n$ ключей в хеш-таблице размером $m=n$ с использованием хеш-функции $h$, выбираемой случайным образом из универсального множества хеш-функций, и устанавливаем размер каждой вторичной хеш-таблицы равным $m_j=n_j^2$ $(j=0,1,...,m-1)$, то математическое ожидание количества необходимой для вторичных хеш-таблиц в схеме идеального хеширования памяти не превышает $2n$.

Доказательство:

$\triangleright$

Поскольку $m_j=n_j^2$ для $j=0,1,...,m-1$, согласно предыдущей теореме: $E\left[\displaystyle \sum_{j=0}^{m-1} m_j \right] = E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] \lt 2n$, ч.т.д.

$\triangleleft$

Теорема:

Если мы сохраняем $n$ ключей в хеш-таблице размером $m=n$ с использованием хеш-функции $h$, выбираемой случайным образом из универсального множества хеш-функций, и устанавливаем размер каждой вторичной хеш-таблицы равным $m_j=n_j^2$ $(j=0,1,...,m-1)$, то вероятность того, что общее количество необходимой для вторичных хеш-таблиц памяти не менее $4n$, меньше чем $1/2$.

Доказательство:

$\triangleright$

Применим неравенство Маркова $P(X \geqslant t) \leqslant E[X]/t$ Пусть $X=\displaystyle \sum_{j=0}^{m-1} m_j$ и $t=4n$. Тогда $P \left \{\displaystyle \sum_{j=0}^{m-1} m_j \geqslant 4n \right \} \leqslant E\left[\displaystyle\sum_{j=0}^{m-1} mj\right]$ ${1 \over 4n} \lt$ ${2n \over 4n} = {1 \over 2}$, ч.т.д.

$\triangleleft$

См. также

• Хеширование
• Хеширование кукушки
• Разрешение коллизий

Ссылки

• Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 11.5, стр. 308
• Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563
• Perfect hash function — Wikipedia
• Universal and Perfect Hashing
• Универсальное хэширование. Идеальное хэширование