Изменения
Новая страница: «'''Двойное хеширование (double hashing)''' - один из методов закрытого хеширования. Перебор ячеек хе…»
'''Двойное хеширование (double hashing)''' - один из методов закрытого хеширования. Перебор ячеек хеш-таблицы, возникающий при двойном хешировании, обладает свойствами, присущими равномерному хешированию. При двойном хешировании хеш-функция <tex> h </tex> имеет следующий вид:
<center>
<tex> h(k,i) = (h_1(k) + i\cdot h_2(k)) \; mod \; m </tex>
</center>
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
где <tex> h_1 </tex> и <tex> h_2 </tex> - вспомогательные хеш-функции, <tex> m </tex> - размер хеш-таблицы. Иными словами, последовательность индексов исследуемых ячеек при работе с ключом <tex> k </tex> представляет собой арифметическую прогрессию (по модулю <tex> m </tex>) с первым членом <tex> h_1(k) </tex> и шагом <tex> h_2(k) </tex>. Следовательно, в данном случае последовательность исследования зависит от ключа k по двум параметрам - выбор начальной исследуемой ячейки и расстояние между двумя исследуемыми ячейками, так как оба параметра зависят от значения ключа.
Пример вставки элемента при двойном хешировании приведен на рисунке справа.
Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:
<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> (h_1(k),h_2(k)) </tex> дает отличающуюся от других последовательность исследований.
== Литература ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''' — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1.
<center>
<tex> h(k,i) = (h_1(k) + i\cdot h_2(k)) \; mod \; m </tex>
</center>
[[Файл: Вставка при двойном хэшировании.svg.jpeg|thumb|right|Вставка при двойном хешировании]]
где <tex> h_1 </tex> и <tex> h_2 </tex> - вспомогательные хеш-функции, <tex> m </tex> - размер хеш-таблицы. Иными словами, последовательность индексов исследуемых ячеек при работе с ключом <tex> k </tex> представляет собой арифметическую прогрессию (по модулю <tex> m </tex>) с первым членом <tex> h_1(k) </tex> и шагом <tex> h_2(k) </tex>. Следовательно, в данном случае последовательность исследования зависит от ключа k по двум параметрам - выбор начальной исследуемой ячейки и расстояние между двумя исследуемыми ячейками, так как оба параметра зависят от значения ключа.
Пример вставки элемента при двойном хешировании приведен на рисунке справа.
Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:
<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> (h_1(k),h_2(k)) </tex> дает отличающуюся от других последовательность исследований.
== Литература ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. '''Алгоритмы. Построение и анализ''' — Вильямс, 2010. - 1296с. — ISBN 978-5-8459-0857-4, 0-07-013151-1.
