Сравнение методов. Мы изучили много различных методов поиска, однако какой метод лучше выбрать для конкретного приложения? В нескольких словах невозможно изложить все, что хотелось бы учесть при выборе метода поиска; однако следующие соображения представляются наиболее важными в отношении скорости работы алгоритма и объема памяти, требуемой этими методами.

На рис. 44 представлены результаты анализов алгоритмов, проведенных в данном разделе, и показано, что различные методы разрешения коллизий приводят к различному числу проб. Однако количество проб - не единственный критерий, так как при использовании разных методов на проведение пробы требуется разное время, что существенно влияет на время работы в целом (см. рис. 42). При линейном исследовании приходится значительно чаще по сравнению с другими методами, показанными на рис. 44, обращаться к таблице, зато этот метод чрезвычайно прост. Кроме того, линейное исследование - не такой уж плохой метод: при заполненности таблицы на 90% алгоритм L требует в среднем меньше 5.5 проб для поиска в таблице случайного элемента (впрочем, при 90% заполненности таблицы алгоритм L нуждается в примерно 50.5 пробах для вставки каждого нового элемента).

Как показано на рис. 44, метод цепочек очень экономичен с точки зрения числа проб и не экономичен с точки зрения требуемой дополнительной памяти для хранения полей ссылок, что особенно неприятно при наличии малых записей. При этом более выгодным по сравнению с методом цепочек становится метод открытой адресации. Так, при выборе между таблицей с цепочками объемом 500 элементов и таблицей с открытой адресацией объемом 1000 элементов последняя явно предпочтительнее, поскольку обеспечивает эффективный поиск среди 500 записей и вмещает в два раза больше данных. С другой стороны, иногда в силу размера записей или специфики используемого формата можно получить место для полей ссылок фактически бесплатно (см. упр. 65).

Как ведут себя методы хеширования по сравнению с другими методами поиска, изученными в этой главе? С точки зрения скорости работы они лучше других методов при большом количестве записей, поскольку среднее время поиска при хеш-методе остается ограниченным, когда N -¥ оо, если таблица не становится слишком заполненной. Например, программа L требует всего лишь 55 единиц времени для успешного поиска при заполненной на 90% таблице, что быстрее самой быстрой MIX-программы (см. упр. 6.2.1-24) при N > 600, и цена этой скорости составляет 11% пространства. Более того, бинарный поиск годится только для фиксированных таблиц, в то время как хеш-таблицы позволяют делать эффективные вставки.

Можно также сравнить программу L с методами поиска, ориентированными на работу с деревьями, которые позволяют выполнять динамические вставки. Программа L при таблице, заполненной на 90%, работает быстрее, чем программа 6.2.2Т при iV > 90, и быстрее, чем программа 6.3D (упр. 6.3-9) при N > 75.

Только один метод из рассмотренных в данной главе эффективен в случае удачного поиска и не перерасходует память - это модификация Брента алгоритма D. Метод Брента позволяет поместить iV записей в таблицу размером М = N + 1 и найти любую запись в среднем за 2.5 пробы. При этом не требуется дополнительное пространство для полей ссылок или битов дескрипторов; однако неудачный поиск может оказаться весьма медленным (для него может потребоваться около N/2 проб).

0.2 0.3 0.4 0.5 0.6 0.7 0.8 Коэффициент заполненности, a - NjM (a) Неудачный поиск

0.9 1.0

О «"

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Коэффициент заполненности, а = N/M (b) Удачный поиск

Рис. 44. Сравнение методов разрешения коллизий: предельные значения среднего количества проб при М -> оо.

Таким образом, хеширование имеет ряд преимуществ. С другой стороны, есть три важных аспекта, по которым хеширование уступает рассмотренным ранее методам.

А) После неудачного поиска в хеш-таблице известно только то, что искомый ключ отсутствует в таблице, а методы, основанные на сравнении ключей, всегда дают дополнительную информацию, например позволяют найти наибольший ключ < К и/или наименьший ключ > К*. Во многих приложениях получить такую информацию крайне важно; например, она позволяет интерполировать функцию

* Впрочем, поскольку мы говорим о неудачном поиске, приведенные автором неравенства становятся строгими. - Прим. перев.

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

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

C) Наконец, нужно свято верить в теорию вероятностей, применяя .методы хеширования, поскольку они эффективны только в среднем, в то время как наихудшие случаи просто ужасны. Как и при использовании датчиков случайных чисел, никогда нельзя быть абсолютно уверенным в том, что хеш-функция будет удовлетворительно работать с новым множеством данных. Таким образом, хеширование - не самый подходящий метод для некоторых приложений реального времени (наподобие контроля за дорожным движением), когда на карту поставлены человеческие жизни. Алгоритмы сбалансированных деревьев из разделов 6.2.3 и 6.2.4 более безопасны, поскольку обеспечивают гарантированную верхнюю границу времени поиска.

История. Идея хеширования впервые была высказана Г. П. Ланом (Н. Р. Luhn) при написании внутреннего меморандума IBM в январе 1953 года с предложением использовать метод цепочек. В этом меморандуме фактически впервые предлагалось использовать связанные линейные списки при решении практических задач. Он указал, что для внешнего поиска желательно использовать блоки, содержащие более одного элемента. Вскоре после этого Э. Д. Лин (А. D. Lin) развил теорию Лана и предложил технологию для обработки переполнений с помощью "вырожденных адресов"; например, при переполнении первичного блока 2 748 переполняющих записей попадают во вторичный блок 274; переполнения из этого блока попадают в третичный блок 27 и т. д. (в предположении, что имеется 10000 первичных блоков, 1000 вторичных, 100 третичных и т. д.). Хеш-функция, предложенная Ланом, по своей природе была буквенно-цифровой, например комбинировались соседние пары цифр ключа при помощи суммирования по модулю 10, так что 31415 926 упаковывалось до 4 548.

Примерно в то же время идея хеширования независимо возникла и у другой группы сотрудников IBM: Жини М. Амдал (Gene М. Amdahl), Элейн М. Боэм (Elaine М. Boehme), Н. Рочестера (N. Rochester) и Артура Л. Сэмюэла (Arthur L. Samuel). Они создавали программу на ассемблере для IBM 701. Для разрешения проблемы, связанной с коллизиями, Жини Амдал предложила использовать открытую адресацию с линейным исследованием.

В открытой печати хеширование впервые было описано Арнольдом И. Думи (Arnold I. Dumey) [Computers and Automation 5,12 (December, 1956), 6-9]. Он был