Таблица 14.1 Данные экспериментального исследования реализаций хеш-таблиц

Эти относительные значения времени построения и поиска в таблицах символов, состоящих из случайных последовательностей 32-разрядных целых чисел, подтверждают, что для ключей, которые легко поддаются хешированию, хеширование работает значительно быстрее, чем поиск с использованием дерева. Двойное хеширование работает медленнее, чем раздельное связывание и линейное зондирование для разреженных таблиц (из-за необходимости вычисления второй хеш-функции), но значительно быстрее линейного зондирования, когда таблица заполняется; кроме того, этот метод - единственный, который может обеспечить быстрый поиск с использованием лишь небольшого дополнительного объема памяти. Динамические хеш-таблицы, построенные с использованием линейного зондирования и расширения путем удвоения, требуют больших затрат времени при конструировании, чем другие хеш-таблицы, из-за необходимости распределения памяти и повторного хеширования, но несомненно обеспечивают наиболее быстрый поиск. Этот метод является предпочтительным, когда чаще всего выполняется поиск, и когда заранее нельзя точно предвидеть количество ключей.

конструирование

промахи при поиске

R RB-дерево бинарного поиска (программы 12.8 и 13 6)

Н Раздельное связывание (программа 14.3 при размере таблицы, равном 20000)

Р Линейное зондирование (программа 14.4 при размере таблицы, равном 200000)

D Двойное хеширование (программа 14.6 при размере таблицы, равном 200000)

Р Линейное зондирование с расширением путем удвоения (программа 14.7)

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

Сравнение линейного зондирования и двойного хеширования с раздельным связыванием выполнить сложнее, поскольку необходимо точно учитывать используемый объем памяти. Раздельное связывание использует дополнительный объем памяти для связей; методы с открытой адресацией используют дополнительную память неявно внутри таблицы для завершения последовательностей зондирования. Следующий конкретный пример иллюстрирует ситуацию. Предположим, что имеется таблица Л/списков, построенная при помощи раздельного связывания, что средняя длина списков равна 4, а каждый элемент и каждая связь занимают по одному машинному слову. Предположение, что элементы и ссылки занимают одинаковый объем памяти, оправдано во многих ситуациях, поскольку очень большие элементы будут заменены ссылками на них. В этом случае таблица занимает 9М слов в памяти (4Л/для элементов и 5М для связей), и для выполнения поиска в среднем требуется 2 зондирования. Но при линейном зондировании для 4Л/ элементов в таблице размером 9М требуется всего (1 + 1/(1 -4/9)) / 2 = 1.4 зондирований для обнаружения попадания при поиске - что на 30 процентов меньше, чем требуется для раздельного связывания при том же объеме используемой памяти; а при линейном зондировании для AM элементов в таблице размером ЬМ требуется 2 зондирования для обнаружения попадания при поиске (в среднем) и, следовательно, используется памяти на 33 процента меньше, чем при раздельном связывании при том же времени выполнения. Более того, для обеспечения увеличения таблицы при остающемся небольшим коэффициенте ее загрузки можно использовать динамический метод, подобный реализованному в программе 14.7.

Приведенные в предшествующем абзаце рассуждения показывают, что обычно выбор раздельного связывания вместо открытой адресации по соображениям производительности не является вполне оправданным. Однако на практике раздельное связывание с фиксированным значением М часто выбирают по ряду других причин: его легко реализовать (особенно операцию remove); оно требует небольшого дополнительного объема памяти для элементов, которые имеют заранее выделенные поля связей, пригодные для использования таблицей символов и другими АТД, которые могут в них нуждаться; и, хотя его производительность снижается с увеличением количества элементов в таблице, это снижение допустимо и происходит так, что вряд ли повредит приложению, поскольку.производительность все же в Л/раз выше, чем производительность последовательного поиска.

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

Один класс методов перемещает элементы во время вставки при двойном хешировании, делая успешный поиск более эффективным. Так, Брент (Brent) разработал метод, при использовании которого среднее время успешного поиска может ограничиваться константой даже в заполненной таблице {см. раздел ссылок). Такой метод может быть удобным в приложениях, в которых попадания при поиске - основная операция.

Другой метод, называемый упорядоченным хешированием (ordered hashing), использует упорядочение для уменьшения затрат на безрезультатный поиск при использовании линейного зондирования, приближая их к затратам на успешный поиск. В стандартном линейном зондировании поиск прекрашается при обнаружении пустой позиции таблицы или элемента, ключ которого равен искомому; в упорядоченном хешировании поиск прекрашается при обнаружении ключа, который больше или равен искомому ключу (чтобы эта процедура работала, таблица должна конструироваться продуманно) {см. раздел ссылок). Это усовершенствование путем ввода упорядочения в таблицу аналогично достигаемому эффекту от упорядочения списков при раздельном связывании. Этот метод предназначен для приложений, в которых преобладают промахи при поиске.

Таблица символов, в которой быстро происходит обнаружение промахов при поиске и несколько медленнее - попаданий при поиске, может использоваться для реализации словаря исключений (exception dictionary). Например, система текстовой обработки может содержать алгоритм для разбиения слов на слоги, который успешно работает для большинства слов, но не работает в отдельных случаях (таких как bizarre ). Скорее всего, лишь небольшое количество слов в очень большом документе будет включено в словарь исключений, поэтому, скорее всего, почти все поиски будут завершаться промахами.

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

Задача реализации словаря исключений представляет собой пример приложения, в котором алгоритм можно слегка изменить для оптимизации производительности наиболее часто выполняемой операции - в данном случае обнаружения промаха при поиске. Например, предположим, что имеется словарь исключений, состоящий из 1000 элементов, 1 миллион элементов, которые необходимо искать в словаре, и ожидается, что буквально все поиски должны завершаться промахами. Эта ситуация могла бы возникнуть, если бы все элементы были исключениями языка или случайными 32-разрядными целыми числами. Один из подходов - хеширование всех слов, скажем, 15-разрядными значениями (в этом случае размер таблицы составит около 2). 1000 исключений занимают 1/64 часть таблицы и большинство из 1 миллиона поисков немедленно завершаются промахами при обнаружении пустой позиции таблицы при первом же зондировании. Но если таблица содержит 32-разрядные слова, задачу можно выполнить значительно эффективней, преобразовав ее в таблицу исключительных разрядов и используя 20-разрядные хеш-значения. При промахе (как имеет место в большинстве случаев) поиск завершается в результате проверки одного разряда; в случае попадания при поиске требуется выполнения второй проверки в меньшей таблице. Исключения занимают 1/1000 часть таблицы; промахи при поиске - наиболее