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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 3 участников)
Строка 4: Строка 4:
 
}}
 
}}
  
==Постановка задачи==
+
== Основная идея ==
{{Задача
+
Идеальное хеширование используется в задачах со статическим множеством ключей (т.е. после того, как все ключи сохранены в таблице, их множество никогда не изменяется) для обеспечения хорошей асимптотики даже в худшем случае. При этом мы можем дополнительно хотеть, чтобы размер таблицы зависел от количества ключей линейно.
|definition=
+
 
Иногда возникают задачи не с динамическим, а со статическим множеством ключей, т.е. после того, как все ключи сохранены в таблице, их множество никогда не изменяется. При этом мы можем дополнительно хотеть, чтобы размер таблицы зависел от количества ключей линейно. Тогда мы можем использовать идеальное хеширование для обеспечения хорошей асимптотики даже в худшем случае.
+
В таком хешировании для доступа к данным потребуется лишь вычисление хеш-функций (одной или нескольких), что делает данный подход наибыстрейшим для доступа к статическим данным. Данная технология применяется в различных словарях и базах данных, в алгоритмах со статической (известной заранее) информацией.
}}
 
  
== Основная идея ==
 
 
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
 
Будем использовать двухуровневую схему хеширования с универсальным хешированием на каждом уровне.
 
=== Первый уровень ===
 
=== Первый уровень ===
Используется тот же принцип, что и в случае хеширования с цепочками: <tex>n</tex> ключей хешируются в <tex>m</tex> ячеек с использованием хеш-функции <tex>h(k) = ((a\cdot k+b) \bmod p) \bmod m</tex>, случайно выбранной из [[Универсальное_семейство_хеш-функций | семейства универсальных хеш-функций]] <tex>H_{p,m}</tex>, где <tex>p</tex> - простое число, превышающее <tex>m</tex>.
+
Используется тот же принцип, что и в случае хеширования с цепочками: <tex>n</tex> ключей хешируются в <tex>m</tex> ячеек с использованием хеш-функции <tex>h(k) = ((a\cdot k+b) \bmod p) \bmod m</tex>, случайно выбранной из [[Универсальное_семейство_хеш-функций | семейства универсальных хеш-функций]] <tex>H_{p,m}</tex>, где <tex>p</tex> простое число, превышающее <tex>m</tex>.
  
 
=== Второй уровень ===
 
=== Второй уровень ===
Строка 24: Строка 22:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если <tex>n</tex> ключей сохраняются в хеш-таблице размером <tex>m=n^2</tex> c использованием хеш-функции <tex>h</tex>, случайно выбранной из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], то вероятность возникновения коллизий не превышает <tex dpi="180">{1 \over 2}</tex>.
+
Если <tex>n</tex> ключей сохраняются в хеш-таблице размером <tex>m=n^2</tex> c использованием хеш-функции <tex>h</tex>, случайно выбранной из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], то [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий не превышает <tex dpi="180">{1 \over 2}</tex>.
 
|proof=
 
|proof=
 
Всего имеется <tex>\dbinom{n}{2}</tex> пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из [[Универсальное_семейство_хеш-функций | универсального семейства хеш-функций]] <tex>H</tex>, то для каждой пары вероятность возникновения коллизии равна <tex dpi="180">{1 \over m}</tex>. Пусть <tex>X</tex> — [[Дискретная_случайная_величина |случайная величина]], которая подсчитывает количество коллизий. Если <tex>m = n^2</tex>, то [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий равно
 
Всего имеется <tex>\dbinom{n}{2}</tex> пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из [[Универсальное_семейство_хеш-функций | универсального семейства хеш-функций]] <tex>H</tex>, то для каждой пары вероятность возникновения коллизии равна <tex dpi="180">{1 \over m}</tex>. Пусть <tex>X</tex> — [[Дискретная_случайная_величина |случайная величина]], которая подсчитывает количество коллизий. Если <tex>m = n^2</tex>, то [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий равно
Строка 33: Строка 31:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если мы сохраняем <tex>n</tex> ключей в хеш-таблице в хеш-таблице размеров <tex>m=n</tex> c использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из универсального множества хеш-функций, то <tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] < 2n</tex>, где <tex>n_j</tex> — количество ключей, хешированных в ячейку <tex>j</tex>.
+
Если мы сохраняем <tex>n</tex> ключей в хеш-таблице размеров <tex>m=n</tex> c использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из универсального множества хеш-функций, то <tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] < 2n</tex>, где <tex>n_j</tex> — количество ключей, хешированных в ячейку <tex>j</tex>.
 
|proof=
 
|proof=
 
<tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] =</tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} (n_j + 2 \dbinom{n_j}{2})\right] = </tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} n_j\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\right] = </tex> <tex> 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]</tex>
 
<tex>E\left[\displaystyle \sum_{j=0}^{m-1} n_j^2 \right] =</tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} (n_j + 2 \dbinom{n_j}{2})\right] = </tex> <tex> E\left[ \displaystyle \sum_{j=0}^{m-1} n_j\right] + 2E\left[\displaystyle \sum_{j=0}^{m-1} \dbinom{n_j}{2}\right] = </tex> <tex> 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]</tex>
Строка 58: Строка 56:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если мы сохраняем <tex>n</tex> ключей в хеш-таблице размером <tex>m=n</tex> с использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], и устанавливаем размер каждой вторичной хеш-таблицы равным <tex>m_j=n_j^2</tex> <tex>(j=0,1,...,m-1)</tex>, то вероятность того, что общее количество необходимой для вторичных хеш-таблиц памяти не менее <tex>4n</tex>, меньше чем <tex>1/2</tex>.
+
Если мы сохраняем <tex>n</tex> ключей в хеш-таблице размером <tex>m=n</tex> с использованием хеш-функции <tex>h</tex>, выбираемой случайным образом из [[Универсальное_семейство_хеш-функций | универсального множества хеш-функций]], и устанавливаем размер каждой вторичной хеш-таблицы равным <tex>m_j=n_j^2</tex> <tex>(j=0,1,...,m-1)</tex>, то вероятность того, что общее количество необходимой для вторичных хеш-таблиц памяти не менее <tex>4n</tex>, меньше чем <tex dpi="180">{1 \over 2}</tex>.
 
|proof=
 
|proof=
 
Применим [[Неравенство Маркова| неравенство Маркова]] <tex>P(X \geqslant t) \leqslant E[X]/t</tex>
 
Применим [[Неравенство Маркова| неравенство Маркова]] <tex>P(X \geqslant t) \leqslant E[X]/t</tex>
Строка 75: Строка 73:
 
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 11.5, стр. 308
 
* Т. Кормен. «Алгоритмы. Построение и анализ» второе издание, Глава 11.5, стр. 308
 
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563
 
* Д.Э. Кнут. «Искусство программирования: Сортировка и поиск" Том 3, Глава 6.4, стр. 563
* [http://en.wikipedia.org/wiki/Perfect_hash_function Perfect hash function — Wikipedia]
+
* [http://en.wikipedia.org/wiki/Perfect_hash_function Wikipedia — Perfect hash function]
 
* [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 Универсальное хэширование. Идеальное хэширование]

Текущая версия на 19:37, 4 сентября 2022

Определение:
Идеальная хеш-функция (англ. 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 \over 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]

См. также

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