Принцип двойного хеширования

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

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

Дата добавления: 2015-07-26; просмотров: 156; Нарушение авторских прав

Мы поможем в написании ваших работ!