Идеальное хеширование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 6: Строка 6:
 
== Основная идея ==
 
== Основная идея ==
 
Идеальное хеширование используется в задачах со статическим множеством ключей (т.е. после того, как все ключи сохранены в таблице, их множество никогда не изменяется) для обеспечения хорошей асимптотики даже в худшем случае. При этом мы можем дополнительно хотеть, чтобы размер таблицы зависел от количества ключей линейно.
 
Идеальное хеширование используется в задачах со статическим множеством ключей (т.е. после того, как все ключи сохранены в таблице, их множество никогда не изменяется) для обеспечения хорошей асимптотики даже в худшем случае. При этом мы можем дополнительно хотеть, чтобы размер таблицы зависел от количества ключей линейно.
 +
 +
В таком хешировании для доступа к данным потребуется лишь вычисление хеш-функций (одной или нескольких), что делает данный подход наибыстрейшим для доступа к статическим данным. Данная технология применяется в различных словарях и базах данных, в алгоритмах со статической (известной заранее) информацией.
  
 
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
 
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
Строка 62: Строка 64:
 
Тогда <tex>P \left \{\displaystyle \sum_{j=0}^{m-1} m_j \geqslant 4n \right \} \leqslant E\left[\displaystyle\sum_{j=0}^{m-1} mj\right]</tex> <tex dpi="150"> {1 \over 4n} < </tex> <tex dpi="150">{2n \over 4n} = {1 \over 2}</tex>, ч.т.д.
 
Тогда <tex>P \left \{\displaystyle \sum_{j=0}^{m-1} m_j \geqslant 4n \right \} \leqslant E\left[\displaystyle\sum_{j=0}^{m-1} mj\right]</tex> <tex dpi="150"> {1 \over 4n} < </tex> <tex dpi="150">{2n \over 4n} = {1 \over 2}</tex>, ч.т.д.
 
}}
 
}}
==Применение идеального хеширования==
 
Идеальное хеширование применяется в тех случаях, когда мы хотим присвоить уникальный идентификатор ключу, без сохранения какой-либо информации о ключе. Одним из наиболее очевидных примеров использования идеального хеширования является ситуация, когда мы располагаем небольшой быстрой памятью, где размещаем значения хешей, связанных с данными хранящимися в большой, но медленной памяти. Причем размер хеш-таблицы можно выбрать таким, что необходимые нам данные, хранящиеся в медленной памяти, будут получены за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах. Также идеальное хеширование используется для ускорения работы алгоритмов на графах, в тех случаях, когда представление графа не умещается в основной памяти.
 
 
==См. также==
 
==См. также==
 
* [[Хеширование]]
 
* [[Хеширование]]
Строка 73: Строка 73:
 
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563
 
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563
 
* [http://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia — Perfect hash function]
 
* [http://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia — Perfect hash function]
*[http://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5#.D0.98.D0.B4.D0.B5.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D0.B5_.D1.85.D0.B5.D1.88.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5 Википедия — Идеальное хеширование]
 
 
* [http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0215.pdf Universal and Perfect Hashing]
 
* [http://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0215.pdf Universal and Perfect Hashing]
 
* [http://nord.org.ua/static/course/algo_2009/lecture8.pdf Универсальное хэширование. Идеальное хэширование]
 
* [http://nord.org.ua/static/course/algo_2009/lecture8.pdf Универсальное хэширование. Идеальное хэширование]

Версия 22:28, 5 июня 2015

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


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

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

В таком хешировании для доступа к данным потребуется лишь вычисление хеш-функций (одной или нескольких), что делает данный подход наибыстрейшим для доступа к статическим данным. Данная технология применяется в различных словарях и базах данных, в алгоритмах со статической (известной заранее) информацией.

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

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

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

См. также

Источники информации