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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 4: Строка 4:
 
}}
 
}}
  
== Практический смысл ==
+
== Постановка задачи ==
Задача идеального хеширования возникает тогда, когда возникает необходимость проверять наличие элемента (скажем, слова из словаря) за гарантировано константное время. При этом подразумевается, что набор данных в таблице статичен либо изменяется очень редко.
+
Необходимо проверять наличие элемента (скажем, слова из словаря) за гарантировано константное время. При этом подразумевается, что набор данных в таблице статичен либо изменяется очень редко.
  
 
== Основная идея ==
 
== Основная идея ==
Строка 14: Строка 14:
  
 
=== Второй уровень ===
 
=== Второй уровень ===
На данном уровне будет использовать вторичную хеш-таблицу <tex>S_j</tex> со своей функций <tex>h_j</tex>. <tex>S_j</tex> будет хранить все ключи, хешированные в ячейку <tex>j</tex>. Соответственно, хеш-функция будет вида <tex>h_j((a_j\cdot k + b_j) \bmod p) \bmod m_j</tex>.<br>
+
На данном уровне будемльзовать вторичную хеш-таблицу <tex>S_j</tex> со своей функций <tex>h_j</tex>. <tex>S_j</tex> будет хранить все ключи, хешированные в ячейку <tex>j</tex>. Соответственно, хеш-функция будет вида <tex>h_j(k)=((a_j\cdot k + b_j) \bmod p) \bmod m_j</tex>.<br>
  
Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе. Но для того, чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер <tex>m_j</tex> хеш-таблицы <tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных в ячейку <tex>j</tex>.
+
Для того, чтобы гарантировать отсутствие коллизий на втором уровне, требуется, чтобы размер <tex>m_j</tex> хеш-таблицы <tex>S_j</tex> был равен квадрату числа <tex>n_j</tex> ключей, хешированных в ячейку <tex>j</tex>. Благодаря такому подходу, так как ни в одной из вторичных таблиц нет ни одной коллизии, время поиска в худшем случае будет равно константе.
  
Хеш-функция первого уровня выбирается из множества <tex>H_{p,m}</tex>, где <tex>p</tex> - простое число, превышающее значение любого из ключей. Ключи, хешированные в ячейку <tex>j</tex>, затем повторно хешируются во вторичную хеш-таблицу <tex>S_j</tex> размером <tex>m_j</tex> с использованием хеш-функции <tex>h_j</tex> , выбранной из множества <tex>H_{p,m_j}</tex>.
+
Хеш-функция первого уровня выбирается из множества <tex>H_{p,m}</tex>, где <tex>p</tex> - простое число, превышающее значение любого из ключей. Ключи, хешированные функцией <tex>h</tex> в ячейку <tex>j</tex>, затем повторно хешируются во вторичную хеш-таблицу <tex>S_j</tex> размером <tex>m_j</tex> с использованием хеш-функции <tex>h_j</tex> , выбранной из множества <tex>H_{p,m_j}</tex>.
 +
 
 +
== Теоретическое обоснование ==
  
== Метод №1 ==
 
Будем использовать <tex>O(n^2)</tex> памяти.
 
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Строка 31: Строка 31:
 
Это является очень хорошим результатом, если хотя бы вспомнить на примере [[Хеш-таблица#Введение | парадокса дней рождения]] о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.
 
Это является очень хорошим результатом, если хотя бы вспомнить на примере [[Хеш-таблица#Введение | парадокса дней рождения]] о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.
  
== Метод №2 ==
 
Будем использовать <tex>O(n)</tex> памяти.
 
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=

Версия 11:22, 13 июня 2013

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


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

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

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

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

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

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

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

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

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

Хеш-функция первого уровня выбирается из множества [math]H_{p,m}[/math], где [math]p[/math] - простое число, превышающее значение любого из ключей. Ключи, хешированные функцией [math]h[/math] в ячейку [math]j[/math], затем повторно хешируются во вторичную хеш-таблицу [math]S_j[/math] размером [math]m_j[/math] с использованием хеш-функции [math]h_j[/math] , выбранной из множества [math]H_{p,m_j}[/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]

См. также

Ссылки