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

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

Псевдослучайное зондирование || Оглавление || Разрешение конфликтов посредством связывания


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



Новости за месяц

  • Июнь
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс