Эффективность хеширования и сравнение с другими методами поиска

Как уже отмечалось, скорость поиска с использованием хеширования не зависит напрямую от количества записей, среди которых выполняется поиск (формально этот факт записывается как T(n) = O(1)). Время поиска складывается из времени вычисления хеш-функции и, возможно, времени, затрачиваемого на разрешение возникших коллизий. В качестве меры времени удобно принять число попыток (проверок ключа) при поиске. Минимально возможное число попыток равно 1 (в случае отсутствия коллизии). Каждая проба другой позиции или каждое продвижение на шаг по списку увеличивает число попыток на 1.

Хотя прямой зависимости от числа записей нет, время поиска (число попыток) существенно зависит от такого показателя, как заполненность хеш-таблицы, которая представляет собой отношение числа записей к числу всех позиций хеш-таблицы: a = n/N.

Характер зависимости определяется выбранным способом разрешения коллизий. Приведем приближенные формулы для двух вариантов:

· если используется алгоритм линейных проб, то T(a) » (1-a/2)/(1-a);

· если используются списки во внешней памяти, то T(a) » 1 + a/2.

Графики обеих функций приведены на рис. 6.3.

Рис. 6.3. Зависимость числа попыток от заполненности таблицы

Судя по графикам, алгоритмы разрешения коллизий ведут себя существенно по-разному при большой заполненности таблицы. Если для линейных проб значения a, близкие к 1, – просто катастрофа, то алгоритм списков во внешней памяти допускает даже заполненность, значительно превышающую 1, хотя при этом хеширование будет работать не намного быстрее линейного поиска.

Общий вывод, который можно сделать из графиков, следующий. Для успешного применения хеширования мало написать хорошую хеш-функцию и выбрать удачный алгоритм разрешения коллизий. Еще одно важнейшее условие – невысокая заполненность таблицы. Желательно обеспечить условие a < 1/2, в крайнем случае – a < 2/3. В этом случае хеширование действительно демонстрирует очень высокую скорость работы, намного превышающую возможности бинарного поиска.

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

· Для успешного хеширования требуется заранее оценить предполагаемое количество записей и разместить в памяти хеш-таблицу избыточного размера.

· Если число записей превышает предварительные оценки, то нет лучшего способа продолжить работу, чем разместить таблицу большего размера и перенести в нее все записи из старой таблицы, затратив на это немалое время. Эта трудоемкая операция называется рехешированием.

· Все способы поиска, основанные на сортированных массивах или деревьях поиска, позволяют, если понадобится, легко найти минимальный и максимальный элементы таблицы, а также перечислить все элементы в порядке возрастания. Хеширование же не дает таких дополнительных возможностей.

· Невозможно раз и навсегда запрограммировать универсальную процедуру «хеширования чего угодно». Выбор алгоритмов хеширования и разрешения коллизий должен производиться исходя из конкретного типа и количества ключей.

· Хорошее хеширование строковых ключей требует использования всех символов ключа, что для длинных ключей может отнимать ощутимое время, сопоставимое с временем поиска по нагруженному дереву.

Вопросы и упражнения

1. Как будет вести себя программа, использующая поиск с хешированием, если из-за ошибки программирования значением хеш-функции всегда будет одна и та же константа?

2. Можно ли использовать хеширование в случае хранения данных на внешнем устройстве?

3. Почему требуется, чтобы хеш-функция принимала все значения из множества индексов I? Чем плохо, если она будет принимать, например, только четные значения?

4. Как можно реализовать удаление ключа из хешируемой таблицы? Для каких способов разрешения коллизий это сделать легче?

5. Почему значения функции двойного хеширования hh(x) должны быть взаимно просты с размером хеш-таблицы?

6. Разместить в хеш-таблице из 11 элементов следующие ключи: 60, 24, 77, 126, 100, 239, 2, 93. Использовать алгоритм деления и алгоритм линейных проб.

Дополнительные вопросы поиска