Изменения
Нет описания правки
'''Двойное хеширование (double hashing)''' - один из методов закрытого хеширования. Перебор ячеек – метод борьбы с возникающими коллизиями при [[Открытое_и_закрытое_хеширование#Закрытое хеширование|закрытом хешировании]], в котором хеш-таблицы, возникающий таблица заполняется равномерней чем при двойном хешировании[[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейном разрешении коллизий]] коллизий, обладает свойствами, присущими равномерному хешированиючто способствует уменьшению размеров кластеров. При двойном хешировании хеш-функция <tex> h </tex> имеет следующий вид:
==Принцип двойного хеширования==При двойном хешировании используются две независимые хеш-функции <tex> h_1(k) </tex> и <tex> h_2(k) </tex>. Пускай <tex> k </tex> это наш ключ, <tex> m </tex> размер нашей таблицы, <tex> mod \; m </tex> это остаток от деления на <tex> m </tex>, тогда сначала исследуется ячейка с адресом <tex> h_1(k) <center/tex>, если она уже занята рассматривается <tex> h(h_1(k) + h_2(k)) \; mod \; m </tex>,iзатем <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> h_1 </tex> может быть обычной хеш-функцией. Однако что бы в случаях коллизий была проверенна вся хеш-таблица, <tex> h_2 </tex> должна возвращать значения:*не равные <tex> 0 </tex>*независимые от <tex> h_1 </tex>*взаимно простые с величиной хеш-таблицы Например, если размер таблицы равен <tex> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \; mod \; (m-1) + 1 </centertex>
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
<center>
==Простая реализация==
Пускай у нас есть некоторый объект <tex> item </tex>, в котором определено поле <tex> key </tex>, от которого можно вычислить хеш-функции <tex> h_1(key)</tex> и <tex> h_2(key) </tex>
Так же у нас есть таблица <tex> table </tex> величиной <tex> m </tex> состоящая из объектов типа <tex> item </tex>.
===Вставка===
<pre>insert(item){
return
}
x = (x + y) % mod m
}
error() //ошибка, требуется увеличить размер таблицы
else
return null
x = (x + y) % mod m
}
return null
==Реализация с удалением==
Что бы наша хеш-таблица поддерживала удаление, требуется добавить массив <tex>deleted</tex> типов <tex>bool</tex>, равный по величине массиву <tex>table</tex>. Теперь при удалении мы просто будем помечать наш объект ''как удалённый'', а при добавлении как ''не удалённый'' и замещать новым добавляемым объектом. При поиске, помимо равенства ключей, мы смотрим, удалён ли элемент, если да, то идём дальше.
===Вставка===
<pre>insert(item){
return
}
x = (x + y) % mod m
}
error() //ошибка, требуется увеличить размер таблицы
else
return null
x = (x + y) % mod m
}
return null
else
return
x = (x + y) % mod m
}
}</pre>
