355
правок
Изменения
м
Нет описания правки
==Определение==
Качественная хеш-функция удовлетворяет (приближенно) условию простого равномерного хеширования: для каждого ключа, независимо от хеширования других ключей, равновероятно помещение его в любую из <tex> m </tex> ячеек. Но это условие обычно невозможно проверить, так как распределение вероятностей, с которыми поступают входные данные, как правило, неизвестно. К тому же, вставляемые ключи могут и не быть независимыми. Если наш противник будет умышленно выбирать ключи для хеширования при помощи конкретной хеш-функции, то при некоторых реализациях хеш-таблиц может получиться так, что все ключи будут записанны в одну и ту же ячейку таблицы, что приведет к среднему времени выборки <tex> \thetaTheta(n) </tex>. Таким образом, любая фиксированная хеш-функция становится уязвимой. И единственный эффективный выход из данной ситуации {{---}} случайный выбор хеш-функции. Такой подход называется универсальным хешированием. Он гарантирует хорошую производительность в среднем, вне зависимости от данных, выбранных злым человеком.
{{Определение
|definition=
Пусть <tex> H </tex> {{---}} конечное множество хеш-функций, которые отображают пространство ключей <tex>\ U </tex> в диапазон <tex> \{0, 1, 2, .. , m - 1\} </tex>.
Такое множество называется '''универсальным''', если для каждой пары ключей <tex> k, l \in U :k\ne l</tex> количество хеш-функций <tex> h \in H </tex>, для которых <tex> h(k) = h(l) </tex> не превышает <texdpi = "180"> \frac{|H| / }{m } </tex>.
}}
Иными словами, при случайном выборе хеш-функции из <tex> H </tex> вероятность коллизии между различными ключами <tex> k, l </tex> не превышает вероятности совпадения двух случайным образом выбранных хеш-значений из множества <tex> \{0, 1, 2, .. , m - 1\} </tex>, которая равна <texdpi = "180"> \frac{1/}{m } </tex>.
==Построение универсального множества хеш-функций==
<tex>s=(al+b)\mod p</tex>.
<tex>r\ne s</tex>, так как <tex>r-s\equiv a(k-l)(\!\!\!\mod 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):a\ne0</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}\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):a\ne0</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>k,l</tex> приводят к коллизии, равна вероятности того, что <tex>r\equiv s(\!\!\!\mod m)</tex> при произвольном выборе отличающихся по модулю <tex>p</tex> значений <tex>r</tex> и <tex>s</tex>. Для данного <tex>r</tex> имеется <tex>p-1</tex> возможное значение <tex>s</tex>. При этом число значений <tex>s:s\ne r</tex> и <tex>s\equiv r(\!\!\!\mod p)</tex>, не превышает
<texdpi = "150">\left\lceil \frac{p/}{m}\right\rceil-1\le((\frac{p+m-1)/}{m)}-1=(\frac{p-1)/}{m}</tex>.
Вероятность того, что <tex>s</tex> приводит к коллизии с <tex>r</tex> при приведении по модулю <tex>m</tex>, не превышает <texdpi = "150">((\frac{p-1)/}{m)}(p-1)=\frac{1/(}{p-1)}=\frac{1/}{m}</tex>.
Значит, <texdpi = "150">\forall k\ne l\in Z_p\ P(h_{a,b}(k)=h_{a,b}(l))\le1/le\frac{1}{m}</tex>, что означает, что множество хеш-функций <tex>H_{p,m}</tex> является универсальным.
}}
