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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метод №2)
Строка 23: Строка 23:
 
Если <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> пар ключей, которые могут вызвать коллизию. Если хеш-функция выбрана случайным образом из [[Универсальное_семейство_хеш-функций | универсального семейства хеш-функций]] H, то для каждой пары вероятность возникновения коллизии равна <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>, то [[Математическое_ожидание_случайной_величины | математическое ожидание]] числа коллизий равно
 
<tex>E[X] = </tex> <tex dpi="180"> \binom{n}{2} \cdot {1 \over n^2} = {n^2-n \over n} \cdot {1 \over n^2} < {1 \over 2}</tex>
 
<tex>E[X] = </tex> <tex dpi="180"> \binom{n}{2} \cdot {1 \over n^2} = {n^2-n \over n} \cdot {1 \over n^2} < {1 \over 2}</tex>
 
}}
 
}}
Это является очень хорошим результатом, если хотя бы вспомнить на примере [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0#.D0.92.D0.B2.D0.B5.D0.B4.D0.B5.D0.BD.D0.B8.D0.B5 парадокса дней рождения] о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.
+
Это является очень хорошим результатом, если хотя бы вспомнить на примере [[Хеш-таблица#Введение | парадокса дней рождения]] о том, что вероятность коллизий растет крайне быстро по сравнению с размером хеш-таблицы.
  
 
== Метод №2 ==
 
== Метод №2 ==
Строка 32: Строка 32:
 
{{Теорема
 
{{Теорема
 
|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>

Версия 20:55, 10 июня 2013

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


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

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

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

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

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

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

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

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

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

Метод №1

Будем использовать [math]O(n^2)[/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]

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

Метод №2

Будем использовать [math]O(n)[/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]

См. также

Ссылки