Изменения

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

Идеальное хеширование

256 байт убрано, 21:34, 6 мая 2012
Нет описания правки
'''Двойное хеширование''' {{---}} метод борьбы с возникающими коллизиями при [[Открытое_и_закрытое_хеширование#Закрытое хеширование|закрытом хешировании]], в котором хеш-таблица заполняется равномерней чем при [[Открытое_и_закрытое_хеширование#Линейное разрешение коллизий|линейном разрешении коллизий]] коллизий, что способствует уменьшению размеров кластеров.
==Принцип двойного хеширования==
При двойном хешировании используются две независимые хеш-функции <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) </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> h_1 </tex> может быть обычной хеш-функцией. Однако что бы в случаях коллизий была проверенна вся хеш-таблицачтобы последовательность исследования могла охватить всю таблицу, <tex> h_2 </tex> должна возвращать значения:
*не равные <tex> 0 </tex>
*независимые от <tex> h_1 </tex>
*взаимно простые с величиной хеш-таблицы
Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй {{---}} размер таблицы является степенью двойки, а <tex> h_2 </tex> возвращает нечетные значения. Например, если размер таблицы равен <tex> m </tex>, то в качестве <tex> h_2 </tex> можно использовать функцию вида <tex> h_2(k) = k \; mod \; (m-1) + 1 </tex>
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
<center>
<tex> h(k,i) = (h_1(k) + i \cdot h_2(k)) \; mod \; 13 </tex>
</center>
<center>
<tex> h_1(k) = k \; mod \; 13 </tex>
</center>
<center>
<tex> h_2(k) = 1 + k \; mod \; 11 </tex>
</center>
Мы хотим вставить ключ 14. Изначально <tex> i = 0 </tex>. Тогда <tex> h(14,0) = (h_1(14) + 0\cdot h_2(14)) \; mod \; 13 = 1 </tex>. Но ячейка с индексом 1 занята, поэтому увеличиваем <tex> i </tex> на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При <tex> i = 2 </tex> получаем <tex> h(14,2) = (h_1(14) + 2\cdot h_2(14)) \; mod \; 13 = 9 </tex>. Ячейка с номером 9 свободна, значит записываем туда наш ключ. Для того, чтобы последовательность исследования могла охватить всю таблицу, значение <tex> h_2 </tex> должно быть взаимно простым с размером таблицы. Есть два удобных способа это сделать. Первый состоит в том, что в качестве размера таблицы используется простое число, а <tex> h_2 </tex> возвращает натуральные числа, меньшие <tex> m </tex>. Второй - размер таблицы является степенью двойки, а <tex> h_2 </tex> возвращает нечетные значения.
Таким образом, основная особенность двойного хеширования состоит в том, что при различных <tex> k </tex> пара <tex> (h_1(k),h_2(k)) </tex> дает различные последовательности ячеек для исследования.
==Ссылки==
* [http://en.wikipedia.org/wiki/Double_hashing Wikipedia: Double_hashing]
* [http://rain.ifmo.ru/cat/view.php/vis/hashtables/hash-2001-2 Пример хеш таблицы]
* [http://research.cs.vt.edu/AVresearch/hashing/double.php Пример хеш таблицы с двойным хешированием]
Анонимный участник

Навигация