Редактирование: Универсальное семейство хеш-функций

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
==Определение==
 
==Определение==
  
Качественная хеш-функция (англ. ''hash function'') удовлетворяет (приближенно) условию простого равномерного [[Хеширование|хеширования]]: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из <tex> m </tex> ячеек. Но это условие обычно невозможно проверить, так как распределение вероятностей, с которыми поступают входные данные, как правило, неизвестно. К тому же, вставляемые ключи могут и не быть независимыми. Если наш противник будет умышленно выбирать ключи для хеширования при помощи конкретной хеш-функции, то при некоторых реализациях хеш-таблиц может получиться так, что все ключи будут записаны в одну и ту же ячейку таблицы, что приведет к среднему времени выборки <tex> \Theta(n) </tex>. Таким образом,  любая фиксированная хеш-функция становится уязвимой. И единственный эффективный выход из данной ситуации {{---}} случайный выбор хеш-функции. Такой подход называется универсальным хешированием. Он гарантирует хорошую производительность в среднем, вне зависимости от данных, выбранных нашим противником.
+
Качественная хеш-функция удовлетворяет (приближенно) условию простого равномерного [[Хеширование|хеширования]]: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из <tex> m </tex> ячеек. Но это условие обычно невозможно проверить, так как распределение вероятностей, с которыми поступают входные данные, как правило, неизвестно. К тому же, вставляемые ключи могут и не быть независимыми. Если наш противник будет умышленно выбирать ключи для хеширования при помощи конкретной хеш-функции, то при некоторых реализациях хеш-таблиц может получиться так, что все ключи будут записаны в одну и ту же ячейку таблицы, что приведет к среднему времени выборки <tex> \Theta(n) </tex>. Таким образом,  любая фиксированная хеш-функция становится уязвимой. И единственный эффективный выход из данной ситуации {{---}} случайный выбор хеш-функции. Такой подход называется универсальным хешированием. Он гарантирует хорошую производительность в среднем, вне зависимости от данных, выбранных нашим противником.
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
 
Пусть <tex> H </tex> {{---}} конечное множество хеш-функций, которые отображают пространство ключей <tex>\ U </tex> в диапазон <tex> \{0, 1, 2, .. , m - 1\} </tex>.
 
Пусть <tex> H </tex> {{---}} конечное множество хеш-функций, которые отображают пространство ключей <tex>\ U </tex> в диапазон <tex> \{0, 1, 2, .. , m - 1\} </tex>.
Такое множество называется '''универсальным''' (англ.  ''universal''), если для каждой пары ключей <tex> k, l \in U, (k\ne l)</tex> количество хеш-функций <tex> h \in H </tex>, для которых <tex> h(k) = h(l) </tex> не превышает <tex dpi = "180"> \frac{|H|}{m} </tex>.
+
Такое множество называется '''универсальным''', если для каждой пары ключей <tex> k, l \in U, (k\ne l)</tex> количество хеш-функций <tex> h \in H </tex>, для которых <tex> h(k) = h(l) </tex> не превышает <tex dpi = "180"> \frac{|H|}{m} </tex>.
 
}}
 
}}
  
Строка 14: Строка 14:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Множество хеш функций <tex>H_{p,m}=\{h_{a,b}:a\in Z_p^*,b\in Z_p\}</tex>, где <tex>h_{a,b}(k)=((ak+b)\bmod p)\bmod m</tex>, <tex>Z_p^*=\{1,2,\dots,p-1\}</tex>, <tex>Z_p=\{0,1,\dots,p-1\}</tex>, <tex>p</tex> {{---}} простое число, является универсальным.
+
Множество хеш функций <tex>H_{p,m}=\{h_{a,b}:a\in Z_p^*,b\in Z_p\}</tex>, где <tex>h_{a,b}(k)=((ak+b)\mod p)\mod m</tex>, <tex>Z_p^*=\{1,2,...,p-1\}</tex>, <tex>Z_p=\{0,1,...,p-1\}</tex>, <tex>p</tex> {{---}} простое число, является универсальным.
 
|proof=
 
|proof=
 
Рассмотрим <tex>k,l\in Z_p:k\ne l</tex>. Пусть для данной хеш-функции <tex>h_{a,b}</tex>  
 
Рассмотрим <tex>k,l\in Z_p:k\ne l</tex>. Пусть для данной хеш-функции <tex>h_{a,b}</tex>  
  
<tex>r=(ak+b)\bmod p</tex>,
+
<tex>r=(ak+b)\mod p</tex>,
  
<tex>s=(al+b)\bmod p</tex>.
+
<tex>s=(al+b)\mod p</tex>.
  
 
<tex>r\ne s</tex>, так как <tex>r-s\equiv a(k-l)\pmod p</tex>, а <tex>p</tex> {{---}} простое число, <tex>a</tex> и <tex>(k-l)</tex> не равны нулю по модулю <tex>p</tex>. Значит, произведение <tex>r</tex> и <tex>s</tex> также отлично от нуля по модулю <tex>p</tex>. Таким, образом, коллизии "по модулю <tex>p</tex>" отсутствуют. Более того, каждая из <tex>p(p-1)</tex> возможных пар <tex>(a,b)</tex>, приводят к различным парам <tex>(r,s):r\ne s</tex>. Чтобы доказать это, достаточно рассмотреть возможность однозначного определения <tex>a</tex> и <tex>b</tex> по заданным <tex>r</tex> и <tex>s</tex>:
 
<tex>r\ne s</tex>, так как <tex>r-s\equiv a(k-l)\pmod p</tex>, а <tex>p</tex> {{---}} простое число, <tex>a</tex> и <tex>(k-l)</tex> не равны нулю по модулю <tex>p</tex>. Значит, произведение <tex>r</tex> и <tex>s</tex> также отлично от нуля по модулю <tex>p</tex>. Таким, образом, коллизии "по модулю <tex>p</tex>" отсутствуют. Более того, каждая из <tex>p(p-1)</tex> возможных пар <tex>(a,b)</tex>, приводят к различным парам <tex>(r,s):r\ne s</tex>. Чтобы доказать это, достаточно рассмотреть возможность однозначного определения <tex>a</tex> и <tex>b</tex> по заданным <tex>r</tex> и <tex>s</tex>:
  
<tex>a=\left((r-s)((k-l)^{-1}\bmod p)\right)\bmod p,\ b=(r-ak)\bmod p</tex>.
+
<tex>a=\left((r-s)((k-l)^{-1}\mod p)\right)\mod p,\ b=(r-ak)\mod p</tex>.
  
 
Поскольку имеется только <tex>p(p-1)</tex> возможных пар <tex>(r,s):r\ne s</tex>, то имеется взаимнооднозначное соответствие между парами <tex>(a,b)</tex> и парами <tex>(r,s):r\ne s</tex>. Таким образом, для любых <tex>k,l</tex> при равномерном случайном выборе пары <tex>(a,b)</tex> из <tex>Z_p^*\times Z_p</tex>, получаемая в результате пара <tex>(r,s)</tex> может быть с равной вероятностью любой из пар с отличающимися значениями по модулю <tex>p</tex>.
 
Поскольку имеется только <tex>p(p-1)</tex> возможных пар <tex>(r,s):r\ne s</tex>, то имеется взаимнооднозначное соответствие между парами <tex>(a,b)</tex> и парами <tex>(r,s):r\ne s</tex>. Таким образом, для любых <tex>k,l</tex> при равномерном случайном выборе пары <tex>(a,b)</tex> из <tex>Z_p^*\times Z_p</tex>, получаемая в результате пара <tex>(r,s)</tex> может быть с равной вероятностью любой из пар с отличающимися значениями по модулю <tex>p</tex>.
Строка 42: Строка 42:
 
|definition=
 
|definition=
 
Пусть <tex> H </tex> {{---}} универсальное семейство хеш-функций.
 
Пусть <tex> H </tex> {{---}} универсальное семейство хеш-функций.
Говорят что оно обладает свойством '''попарной независимости'''(англ. ''pairwise independence''), если при фиксированных <tex> x, y</tex>  <tex> (0 \le x, y \le m-1)</tex> для каждой пары ключей <tex> k, l \in U (k\ne l) </tex>  вероятность того, что <tex> h(k) = x </tex>  и  <tex> h(l) = y </tex>, равна  <tex dpi = "150"> \frac{1}{m^2} + o(\frac{1}{m^2}) </tex>.
+
Говорят что оно обладает свойством '''попарной независимости''', если при фиксированных <tex> x, y</tex>  <tex> (0 \le x, y \le m-1)</tex> для каждой пары ключей <tex> k, l \in U (k\ne l) </tex>  вероятность того, что <tex> h(k) = x </tex>  и  <tex> h(l) = y </tex>, равна  <tex dpi = "150"> \frac{1}{m^2} + o(\frac{1}{m^2}) </tex>.
 
}}
 
}}
  
Строка 52: Строка 52:
 
Для функции <tex>h_{a,b}</tex> получаем
 
Для функции <tex>h_{a,b}</tex> получаем
  
<tex>x = (ak+b)\bmod p \bmod m</tex>
+
<tex>x \equiv (ak+b)\bmod p \bmod m</tex>
  
<tex>y = (al+b)\bmod p \bmod m</tex>
+
<tex>y \equiv (al+b)\bmod p \bmod m</tex>
  
 
Выразим отсюда <tex>a</tex> и <tex>b</tex>. Вычтя из первого уравнения второе, получим:
 
Выразим отсюда <tex>a</tex> и <tex>b</tex>. Вычтя из первого уравнения второе, получим:
Строка 84: Строка 84:
 
Остаётся подытожить наши выкладки.
 
Остаётся подытожить наши выкладки.
  
<tex>P( [x = (ak+b)\bmod p \bmod m]</tex>  <tex>\wedge</tex>  <tex>[y = (al+b)\bmod p \bmod m])</tex>  
+
<tex>P( [x \equiv (ak+b)\bmod p \bmod m]</tex>  <tex>\wedge</tex>  <tex>[y \equiv (al+b)\bmod p \bmod m])</tex>  
 
<tex>=</tex>
 
<tex>=</tex>
  
Строка 101: Строка 101:
 
}}
 
}}
  
==Источники информации==
+
==Источники==
  
 
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2005. — с. 294. — ISBN 5-8459-0857-4
 
* Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ — 2-е изд. — М.: «Вильямс», 2005. — с. 294. — ISBN 5-8459-0857-4
  
 
[[Категория: Дискретная математика и алгоритмы]][[Категория:Хеширование]]
 
[[Категория: Дискретная математика и алгоритмы]][[Категория:Хеширование]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: