AOP_Tom3 (1021738), страница 157
Текст из файла (страница 157)
е. №66(о), как и говорилось выше. Подробный анализ формулы (61) приводится в упр. 55. Обсуждение практических вопросов построения внешних хеш-таблиц дано Чарльзом А. Ольсоном (СЬаг!еэ А. О)зоп) (Ргос. АСМ Лап СопГ. 24 (1969), 539- 549). В его работу включено несколько практических примеров; в ней указано, что количество переполняющих записей значительно увеличивается, если файл служит объектом частых вставок/удалений без перемещения записей. В работе также представлен анализ этой ситуации, выполненный совместно с Дж. А. деПейстером (Я. А.
деРеуаьег). Сравнение методов. Мы изучили много различных методов поиска, однако какой метод лучше выбрать для конкретного приложения? В нескольких словах невозможно изложить все, что хотелось бы учесть при выборе метода поиска; однако следующие соображения представляются наиболее важными в отношении скорости работы алгоритма н объема памяти, требуемой этими методами. На рис. 44 представлены результаты анализов алгоритмов, проведенных в данном разделе, и показано, что различные методы разрешения коллизий приводят к различному числу проб.
Однако количество проб — не единственный критерий, так как при использовании разных методов на проведение пробы требуется разное время, что существенно влияет на время работы в целом (см. рис. 42). При линейном исследовании приходится значительно чаще по сравнению с другими методами, показанными на рис. 44, обращаться к таблице, зато этот метод чрезвычайно прост. Кроме того, линейное исследование — не такой уж плохой метод: при заполненности таблицы па 90% алгоритм Ь требует в среднем меньше 5.5 проб для поиска в таблице случайного элемента (впрочем, при 90% заполненности таблицы алгоритм Ь нуждается в примерно 50.5 пробах для вставки каждого нового элемента).
Как показано на рис. 44, метод цепочек очень экономичен с точки зрения числа проб и не экономи сев с точки зрения требуемой дополнительной памяти для хранения полей ссылок, что особенно неприятно при наличии малых записей. При атом более выгодным по сравнению с методом цепочек становится метод открытой адрегации. Так, при выборе между таблицей с цепочками объемом 500 элементов и таблицей с открытой адресацией объемом 1 000 элементов последняя явно предпочтительнее, поскольку обеспечивает эффективный поиск среди 500 записей и вмещает в два раза болыпе данных. С другой стороны, иногда в силу размера записей или специфики используемого формата можно получить место для полей ссылок фактически бесплатно (см. упр.
65). Как ведут себя методы хеширования по сравнению с другими методами поиска, изученными в этой главе? С точки зрения скорости работы опи лучше других методов при большом количестве записей, поскольку среднее время поиска при хешметоде остается ограниченным, когда Х -> оо, если таблица не становится слишком заполненной. Например, программа Ь требует всего лишь 55 единиц времени для успешяого поиска при заполненной на 90% таблице, что быстрее самой быстрой ИХХ-программы (см, упр, 6.2.1-24) при 57 > 600, и цена этой скорости составляет 11% пространства.
Более того, бинарный поиск годится только для фиксированных таблиц, в то время как хеш-таблицы позволяют делать эффективные вставки. Можно также сравнить программу Ь с методами поиска, ориентированными на работу с деревьями, которые позволяют выполнять динамические вставки. Программа Ь при таблице, заполненной на 90%, работает быстрее, чем программа 6.2.2Т при Х > 90, и быстрее, чем программа 6.3Р (упр. 6.3-9) при Х > 75. Только один метод из рассмотренных в данной главе эффективен в случае удачного поиска и не перерасходует память — это модификация Брента алгоритма П. Метод Брента позволяет поместить Т записей в таблицу размером М = Ж + 1 и найти любую запись в среднем за 2.5 пробы.
При этом не требуется дополнительное пространство для полей ссылок или битов дескрипторов; однако неудачный поиск может оказаться весьма медленным (для него может потребоваться около Т/2 проб). 3 и 3 о о и о й ч о и о. ы 1 о ол 0.9 1.0 0.2 0 3 ОЛ 0.6 О 6 О 7 0.8 Коэффициент заполиеняости, о = гтгМ (а) Неудачпые поиск и 3 и я и 3 й о М 2 я 1 0 0.1 0.2 0.3 0 А 0.3 0.6 0.7 0.8 0.9 1.0 Коэффициент запачиепности, а = йг/М (Ь) Удачный поиск Рис.
44. Сравнение методов разрешении коллизий: предельные значения среднего количества проб лри М -+ со. Таким образом, хеширонание имеет ряд преимугцеств. С другой стороны, есть три важных аспекта, по которьгм хеширование уступает рассмотренным раяее методам. А) После неудачного поиска в хеш-таблице известно только то, что искомый ключ отсутствует в таблице, а методы, основанные на сравнении ключей, всегда дают дополнительную информацию, например позноляют найти наибольший ключ < К и/нли наименьший ключ > К*.
Во многих приложениях получить такую информацию крайне нажно; например, она позволяет интерполироввть функцию * Впрочем, поскольку мы говорим о неудачном поиске, приведенные автором неравенства становятся строгиии. — Прим, персе. по ее табличным значениям или использонать алгоритм, основанный на сравнении ключей для поиска всех ключей, лежащих между двумя данными значениями К и К'. Кроме того, алгоритмы поиска по дереву из раздела 6.2 позволяют легко представить содсржимое таблицы в порядке возрастания без отдельной сортировки. В) Часто очень сложно распределить память для хеш-таблицы — для нее следует заблаговременно выделить область памяти, и не всегда удается заранее сказать, какой размер необходим. Выделяя слишком много памяти, можно тем самым ограничить объем памяти для других списков илн других пользователей; при выделении недостаточного количества памяти произойдет переполнение таблицы.
В протиноположность этому методу алгоритмы поиска и вставки по дереву никогда не увеличиваются сверх необходимого размера. В среде с виртуальной памятью можно локализовать обращения к памяти при выполнении поиска по дереву (или цифрового поиска по дереву), н то время как при создании большой хеш-таблицы необходимо обращаться к операционной системе, чтобы получить доступ к новой страяице памяти почти всякий раз при хешировании очередного ключа. С) Наконец, нужно свято верить в теорию вероятностяй, применяя методы хеширования, поскольку они эффективны только в среднем., в то время как наихудшие случаи просто ужасны. 1(ак и при использовании датчиков случайных чисел, никогда нельзя быть абсолютно уверенным в том, что хеш-функция будет удовлетворительно работать с новым множеством данных.
Таким образом, хеширование — не самый подходящий метод для некоторых приложений реального времени (наподобие контроля за дорожным движением), когда на карту поставлены человеческие жизни. Алгоритмы сбалансированных деревьев из разделов 6,2.3 и 6.2.4 более безопасны, поскольку обеспечивают гарантированную верхнюю границу времени поиска. История. Идея хеширования впервые была высказана Г. П. Ланом (Н. Р. ЬиЬп) при написании внутреннего меморандума 1ВМ в январе 1953 года с предложением использовать метод цепочек.
В этом меморандуме фактически впервые предлагалось использовать связанные линейные списки при решении практических задач. Он указал, что для внешнего поиска желательно использовать блоки, содержащие более одного элемента. Вскоре после этого Э. Д. Лин (А. В. 1лп) развил теорию Лана и предложил технологию для обработки переполнений с помощью "вырожденных адресов"; например, при переполнении первичного блока 2 748 переполняющих записей попадают во вторичный блок 274; переполнения из этого блока попадают в третичный блок 27 и т.
д. (в предположении, что имеется 10000 первичных блоков, 1000 вторичных, 100 третичных и т. д.), Хеш-функция, предложенная Ланом, по своей природе была букненно-цифровой, например комбинировались соседние пары цифр ключа при помощи суммирования по модулю 10, так что 31415926 упаковывалось до 4 548. Примерно в то же время идея хеширования независимо возникла и у другой группы сотрудников 1ВМ: Жини М.
Амдал (Оепе М. Апк1аЫ), Элейн М. Боэм (Е!а~не М. ВоеЬше), Н. Рочестера (Х. НосЬеэтег) и Артура Л. Сэмюэла (АггЬпг Ь. 8апше1), Они создавали программу на ассемблере для 1ВМ 701. Для разрешения проблемы, связанной с коллизиями, Жини Амдал предложила использовать открытую адресацию с линейным исследованием. В открытой печати хеширование впервые было описало Арнольдом И. Думи (Агпо16 1.
Вшпеу) (Сошрп1егв апН Апгошаиоп 5, 12 (ВесешЬег, 1956), 6 — 9]. Он был первюм, кто упомянул идею деления на простое число и использование остатка в качестве хеш-адреса. В интересной статье Думи упоминает цепочки, но открытой адресации в ней нет. Советский математик А.
П. Ершов в 1957 году независимо разработал метод линейной открытой адресации (ДАН СССР 118 (1958), 427-430); он опубликонал эмпирические результаты по количеству проб, справедливо предподожив, что среднее количество проб для успешного поиска < 2 при Аг/М < 2!3, Классическая статья ЪЪ'. %. Ресегеоп, 1ВМ Х НеяеагсЛ Хг Реке!оргг1епг 1 (1957), 130-146, была первой важной работой, посвященной поиску в больших файлах. Петерсон определил открытую адресацию в общем случае, проанализировал производительность равномерного исследования и привел многочисленные эмпирические статистические данные о понедении линейной открытой адресации с блоками различных размеров, указав на ухудшение производительности прн удалении элементов. Другой всесторонний обзор предмета был опубликован шестью годами позже Вернером Букхольцем (Жегпег ВнсЬЬо!к) (!ВМ ЯукГешз Х 2 (1963), 86-111!.
В его работе особый упор сделан на исследовании хеш-функций. Корректный анализ алгоритма Е был впервые опубликован А. Г. Конхеймом (А. С. КопЬе)пз) и Б. Вейссом (В. тте)зэ) (5!АМ Х Арр!. МагЬ. 14 (1966), 1266-1274), а также В. Поддерюгиным (И узэепэсЛай!!сйе ЕейзсйгтУГ г!ег 2есЛп!всЛеп ЬЭть егнйац 1)гезс)еп 17 (1968), 1087 10893.
К этому времени линейное исследование было единственным типом гхегны открытой адресации, описанной в литературе, хотя несколькими исследователями независимо была разработана другая схема, основанная на неоднократном случайном применении независимых хеш-функций (см. упр. 48). В течение нескольких последующих лет хеширование стало широко использоваться, хотя ие было опубликовано никаких новых работ. Затем Роберт Моррис (НоЬегс Могг)з) написал обзор по хешированию )САСМ 11 (1968), 38 — 44], оказавший впоследствии большое влияние на работы в этом направлении.
В обзоре впервые появилась идея случайного исследования с вторичной кластеризацией. Статья Морриса оказалась наброском дальнейших исследований в этой области, которые завершились созданием алгоритма П и его усовершенствованных версий. Интересно отметитьч что слово 'хеширование" (ЬазЬбп8), по-видимому, ни разу не появилось в печати (н его современном значении) до 60-х годов. хотя к тому времени оно прочно заняло место в компьютерном жаргоне во всем мире. Впервые это слово, вероятно, было использовано в книге Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
