Двойное хеширование

Двойное хеширование

В заключение рассмотрим двойное хеширование (double hashing). На практике эта схема оказывается наиболее удачной из всех альтернативных схем с открытой адресацией. Итак, выполним хеширование ключа элемента в значение индекса. Назовем его h(_1_). Выполним зондирование этой ячейки. Если она занята, выполним хеширование ключа путем применения совершенно иного и независимого алгоритма хеширования для получения другого значения индекса. Назовем его h(_2_). Выполним зондирование ячейки h(_1_) + h(_2_). Если она занята, выполним зондирование ячейки h(_1_) + 2h(_2_), затем h(_1_) + 3h(_2_) и так далее (понятно, что все вычисления выполняются с делением по модулю на размер таблицы). Обоснование этого алгоритма следующее: если первая функция хеширования для двух ключей генерирует один и тот же индекс, очень маловероятно, что вторая функция хеширования сгенерирует для них то же самое значение. Таким образом, два ключа, которые первоначально хешируются в одну и ту же ячейку, затем не будут соответствовать одной и той же последовательности зондирования. В результате мы можем ликвидировать "неизбежную" кластеризацию, сопряженную с линейным зондированием. Если размер таблицы равен простому числу, последовательность зондирования обеспечит посещение всех ячеек, прежде чем начнется сначала, что позволит избежать проблем, связных с квадратичным и псевдослучайным зондированием. Единственная реальная проблема, возникающая при использовании двойного хеширования, - если не принимать во внимание необходимость вычисления дополнительного хеш-значения - состоит в том, что вторая функция хеширования по понятным причинам никогда не должна возвращать значение, равное 0. На практике эту проблему легко решить, выполняя деление по модулю на размер таблицы минус 1 (в результате мы получим значение в диапазоне от 0 до TableSize-2), а затем добавляя к результату единицу.

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Двойное выполнение

Из книги автора

Двойное выполнение Остается одна маленькая неприятность (кто сказал, что будет легко?). Поскольку мы устанавливаем событие onload для всех (оставшихся) браузеров, то init сработает дважды — в IE и Firefox. Чтобы это обойти, нам нужно сообщить функции, что она должна выполняться


Уловки SEO — агентств: двойное дно, тройной прайс

Из книги автора

Уловки SEO — агентств: двойное дно, тройной прайс Случается, даже имеющие недурную репутацию SEO — агентства допускают нечистоплотность при заключении договоренностей с клиентами. Иногда такова политика компании в целом, иногда на обман решается «паршивая овца в стаде» –


Хеширование

Из книги автора

Хеширование Хеширование всегда было концепцией, трудной для объяснения. Хеш-функция AS/ 400 сначала выполняет над несколькими старшими и младшими разрядами VPN операцию «Исключающее или». Затем между полученным значением и разрядами маски из специального регистра,


Глава 7. Хеширование и хеш-таблицы

Из книги автора

Глава 7. Хеширование и хеш-таблицы В главе 4 были рассмотрены алгоритмы поиска элемента в массиве (например, TList) или в связном списке. Наиболее быстрым из рассмотренных методов был бинарный поиск, для выполнения которого требовался отсортированный контейнер. Бинарный


Кафедра Ваннаха: Хеширование знаний Ваннах Михаил

Из книги автора

Кафедра Ваннаха: Хеширование знаний Ваннах Михаил Опубликовано 25 июля 2011 года Тема единого государственного экзамена вызывает, как видно из комментариев, искренний и квалифицированный интерес у читателей. Давайте порассуждаем о тестах знаний,


Дмитрий Вибе: Двойное назначение Дмитрий Вибе

Из книги автора

Дмитрий Вибе: Двойное назначение Дмитрий Вибе Опубликовано 24 февраля 2012 года Баллистическую ракету, которая летит в твою сторону, хочется увидеть как можно раньше. Благодаря этому простому и понятному желанию уже многие десятилетия уверенно


Дмитрий Вибе: Двойное назначение

Из книги автора

Дмитрий Вибе: Двойное назначение Автор: Дмитрий ВибеОпубликовано 24 февраля 2012 годаБаллистическую ракету, которая летит в твою сторону, хочется увидеть как можно раньше. Благодаря этому простому и понятному желанию уже многие десятилетия уверенно держатся на плаву