Книга: Фундаментальные алгоритмы и структуры данных в Delphi

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

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

В заключение рассмотрим двойное хеширование (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 для вычисления хеш-значений, которые будут использоваться для пропуска ячеек. Я предлагаю читателям самостоятельно выполнить это простое упражнение по реализации такой хеш-таблицы двойного хеширования.

Оглавление книги