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

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

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

Постановка задачи

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

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

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

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

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

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

На данном уровне вместо создания списка ключей будем использовать вторичную хеш-таблицу [math]S_j[/math], хранящую все ключи, хешированные функцией [math]h[/math] в ячейку [math]j[/math], со своей функцией [math]h_j(k)=((a_j\cdot k + b_j) \bmod p) \bmod m_j[/math], выбранной из множества [math]H_{p,m_j}[/math]. Путем точного выбора хеш-функции [math]h_j[/math] мы можем гарантировать отсутствие коллизий на этом уровне. Для этого требуется, чтобы размер [math]m_j[/math] хеш-таблицы [math]S_j[/math] был равен квадрату числа [math]n_j[/math] ключей, хешированных функцией [math]h[/math] в ячейку [math]j[/math].

Несмотря на квадратичную зависимость, ниже будет показано, что при корректном выборе хеш-функции первого уровня количество требуемой для хеш-таблицы памяти будет [math]O(n)[/math].

Теоретическое обоснование

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Теорема:

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

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

[math]\triangleright[/math]

Поскольку [math]m_j=n_j^2[/math] для [math]j=0,1,...,m-1[/math], согласно предыдущей теореме: [math]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[/math], ч.т.д.

[math]\triangleleft[/math]

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

См. также

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

Ссылки

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