Изменения
Нет описания правки
'''Двойное хеширование''' {{---}} метод борьбы с коллизиями, возникающими коллизиями при [[Открытое_и_закрытое_хеширование#Закрытое хеширование|закрытом хешировании]], в котором основанный на использовании двух хеш-таблица заполняется равномерней чем при [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейном разрешении коллизий]] коллизий, что способствует уменьшению размеров кластеровфункций для построения различных последовательностей исследования хеш-таблицы.
==Принцип двойного хеширования==
При двойном хешировании используются две независимые хеш-функции <tex> h_1(k) </tex> и <tex> h_2(k) </tex>. Пусть <tex> k </tex> {{---}} это наш ключ, <tex> m </tex> {{---}} размер нашей таблицы, <tex> n \mod m </tex> это {{---}} остаток от деления <tex> n </tex> на <tex> m </tex>, тогда сначала исследуется ячейка с адресом <tex> h_1(k) </tex>, если она уже занята, то рассматривается <tex> (h_1(k) + h_2(k)) \mod m </tex>, затем <tex> (h_1(k) + 2 \cdot h_2(k)) \mod m </tex> и так далее. В общем случае идёт проверка последовательности ячеек <tex> (h_1(k) + i \cdot h_2(k)) \mod m </tex> где <tex> i = (0, 1, \; ... \;, m - 1) </tex> Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за <tex>O(1)</tex>, в худшем {{---}} за <tex>O(m)</tex>, что не отличается от обычного [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейного разрешения коллизий]].Однако в среднем, при грамотном выборе хеш-функций, двойное хеширование будет выдавать лучшие результаты, за счёт того, что вероятность совпадения значений сразу двух независимых хеш-функций ниже, чем одной. <center><tex>\forall x \neq y \; \exists h_1,h_2 : \Pr(h_1(x)=h_1(y))> \Pr((h_1(x)=h_1(y))\cap(h_2(x)=h_2(y)))</tex></center>
==Выбор хеш-функций==
==Простая реализация==
Так же у нас есть таблица <tex> table </tex> величиной <tex> m </tex> , состоящая из объектов типа <tex> item </tex>.
===Вставка===
<pre>insert(item){
x = h1(item.key)
y = h2(item.key)
for (i = 0; i < m; i++){ if (table[x] == null){
table[x] = item
return } x = (x + y) mod m } errortable.resize() //ошибка, требуется увеличить размер таблицы}</pre>
===Поиск===
<pre>search(key){
x = h1(key)
y = h2(key)
for (i = 0; i < m; i++){ if (table[x] != null) if (table[x].key == key)
return table[x]
else
return null
x = (x + y) mod m } return null}</pre>
==Реализация с удалением==
===Вставка===
<pre>insert(item){
x = h1(item.key)
y = h2(item.key)
for (i = 0; i < m; i++){ if (table[x] == null || deleted[x]){
table[x] = item
deleted[x] = false
return } x = (x + y) mod m } errortable.resize() //ошибка, требуется увеличить размер таблицы}</pre>
===Поиск===
<pre>search(key){
x = h1(key)
y = h2(key)
for (i = 0; i < m; i++){ if (table[x] != null) if (table[x].key == key && !deleted[x])
return table[x]
else
return null
x = (x + y) mod m } return null}</pre>
===Удаление===
<pre>remove(key){
x = h1(key)
y = h2(key)
for (i = 0; i < m; i++){ if (table[x] != null) if (table[x].key == key)
deleted[x] = true
else
return
x = (x + y) mod m }}</pre>
==См. также==
