Характеристики метода. При двойном хешировании используются две независимые хеш-функции и

При двойном хешировании используются две независимые хеш-функции и . Пусть — это наш ключ, — размер нашей таблицы, — остаток от деления на , тогда сначала исследуется ячейка с адресом , если она уже занята, то рассматривается , затем и так далее. В общем случае идёт проверка последовательности ячеек где

Таким образом, операции вставки, удаления и поиска в лучшем случае выполняются за , в худшем — за , что не отличается от обычного линейного разрешения коллизий. Однако в среднем, при грамотном выборе хеш-функций, двойное хеширование будет выдавать лучшие результаты, за счёт того, что вероятность совпадения значений сразу двух независимых хеш-функций ниже, чем одной.

Пример

Показана хеш-таблица размером 13 ячеек, в которой используются вспомогательные функции:

Мы хотим вставить ключ 14. Изначально . Тогда . Но ячейка с индексом 1 занята, поэтому увеличиваем на 1 и пересчитываем значение хеш-функции. Делаем так, пока не дойдем до пустой ячейки. При получаем . Ячейка с номером 9 свободна, значит записываем туда наш ключ.

Таким образом, основная особенность двойного хеширования состоит в том, что при различных пара дает различные последовательности ячеек для исследования.

Дата добавления: 2015-08-17