Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 40
Текст из файла (страница 40)
Поэтому можно показать, что наилучшие значения д лежат в интервалах — <9< -, т 7 з - <д< —, 1 з 4 ~а-. — <д< -, 1 э э 7' Значение А можно составить так„что каждый из его байтов будет находиться в "хорошем" интервале и будет не слишком близок к значениям других байтов (илн их дополнениям), например (8) Такой множитель может быть смело рекомендован к использованию.
(Изложенные в этом разделе идеи по мультнпликативиому хешированию в основном принадлежат р. В. ф Иду (В. 19. г(оуб).) Хорошая хеш-функция должна удовлетворять двум требованиям. а) Ее вычисление должно выполняться очень быстро. Ь) Она должна минимизировать количество коллизий. Свойство (а) зависит от особенностей компьютера, а свойство (Ь) — от особенностей данных. Если бы все ключи были действительно случайными, можно было бы использовать несколько битов нз них и с их помощью получить хеш-функцию; однако на практике для удовлетворения (Ь) требуется функция, завися~цап от всех битов ключа. До сих пор мы рассматривали хеширование "однословных" ключей. С ключами, состоящими из нескольких слов, и с ключами переменной длины можно работать, как с числами с многократной точностью и применять к ним все рассмотренные методы.
Второй путь состоит в комбинировании слов в одно и в выполнении единственной операции умножения или деления, как описано выше. Зта комбинация может быть осуществлена путем сложения по модулю ш или выполнения операции "исключающее или"' бинарного компьютера. Обе операции используют все биты обоих аргументов; "исключающее илн", однако, предпочтительнее, поскольку позволяет избежать арифметического переполнения.
Основной недостаток такого метода заключается в том, что указанные операции коммутативны, а значит, хеш-адреса (Х, У) и (У, Х) будут совпадать. Чтобы устранить этот недостаток, Г, Д. Кнотт (6. О. Кпоы) предложил выполнять перед арифметической операцией циклический сдвиг.
Еще лучший путь хеширования состоящих из 1 символов (или 1 слав) ключей К = х~ хз... я~ заключается в вычислении Ь(К) = (Ь|(л~) + Ьэ(хт) + + Ь|(л~)) шод М, (9) К(х) шоб Р(х) = Ь ~к'" ~ + .. + Ьгл+ Ье, используя полиномиальпую арифметику по модулю 2. В таком случае Ь(К) = (Ь,„..~...Ь| Ье)з.
Нри правильном выборе Р(х) эта хеш-функция может гарантировать отсутствие коллизий между почти одинаковыми ключами. Например, при и = 15, ш = 10 и р(к) = х'э+ ха+ ха +хэ+х~+к ч-1 (10) глс каждое Ьз представляет собой независимую хеш-функцию. Зта идея, предложенная Дж. Л. Картером (Л. 1.. Сагсег) и М, Н. Вегманом (М. 1э'. Жекшал) в 1977 голу, в особенности эффективна, когда каждый х- представляет собой отдельный символ, поскольку в таком случае можно использовать предвычисленный массив для каждой функции Ь,. Такие массивы делают умножение ненужным.
И если ЛХ представляет собой степень двойки, то в (9) можно избежать деления, используя "исключающее илн" вместо сложения. Таким образом, (9), определенно, удовлетворяет свойству (а). Более того, Картер и Вегман доказали, что если Ь1 выбирается случайным образом, то будет выполняться и свойство (Ь) независимо от входныт диннььх (см.
упр. 72). Было предложено и множество других методов хеширования, однако ни для одного из них не было доказано его преимущество перед простымн методами, описанными выше. Обзор некоторых методов с детальными характеристиками нх производителыюсти при работе с реальными файлами можно найти в статье Ъ', У. 1.шп, Р. 8. Т. Ъцеп, апб М. РосЫ, САСМ 14 (1971), 228-239. Из других интересных методов хеширования, видимо, наибольший интерес представляет технология, основанная иа алгебраическс9 теории кодирования.
Зта технология аналогична методу деления, описанному выше, однако вместо деления на целое число осуществляется деление на полином по модулю 2. (Как упоминалось в разделе 4.6, эта операция аналогична делению, как сложение аналогично операции "исключюощее или",) В данном методе Л7 должно представлять степень 2 (ЛХ = 2"'), и мы используем полипом щ-й степени Р(х) = х'" + р„, ~л'"-' + + ре. пцифровой бинарный ключ К = (Ь„ы .. Ьг Ье)т можно рассматривать как полипом К(х) = Ь„~х" ' + + Ь~х+ Ьа и вычислить остаток можно показать, что Ь(КА) будет всегда отлично от Ь(КА), если КА и Кэ — различные ключи, отличающиеся менее чем семью битами.
(Дополнительная информация по этой теме приводится в упр. 7; в данном случае, конечно, более уместна аппаратная или микропрограммная реализация, а не программная.) Очень часто удобно использовать постоянную хеш-функцию Ь(К) = О в процессе отладки программы, так как все ключи будут храниться вместе; эффективная хеш-функция Ь(К) может быть подставлена позже. Разрешение коллизий методом "цепочек'! Мы уже говорили, что некоторые хеш-адреса могут быть одинаковыми для различных ключей. Вероятно, самый оче. видный путь решения этой проблемы — поддержка М связных списков, по одному для каждого возможного значения хеш-кода. Поле 1,1ИК должно быть включено в каждую запись: кроме того, следует иметь М головных узлов списков, перенумерованных, скажем, от 1 до М. После хеширования ключа мы просто выполняем последовательный поиск в списке номер Ь(К) + 1.
(Обратитесь к упр. 6,1-2. Ситуация весьма напоминает сортировку методом вставок в несколько списков; см. программу 5,2,1М.) Иа рис. 38 показана простая схема с цепочками при М = 9 лля последовательности из ключей К = ЕИ, ТО, ТИЕ, У1ИЕ, УЕИ, ЗЕКЗ, ЗТЧ (11) (представляющих числа от 1 до 7 на норвежском языке), имеющих хеш-коды Ь(К)+1=3, 1, 4, 1, о, 9, 2 соответственно. В первом списке содержится два элемента, три списка пусты. ННАВЩ: ннАРЕ71: ЯНАв Е31: ННАН Е41: НЕАЭ ЕЗ1: ннАН Е61: ннАН Е7): неАН 181: ннАэЕН1: Рнс. ЗЗ. Раздельные цепочки. В связи с тем, что цепочки коротки, рассматриваемый здесь метод является весьма быстродействующим. Если 365 человек соберутся вместе в одной комнате, вероятно, окажется много пар, имеющих один и тот же день рождения, однако среднее количество людей с данным днем рождения равно только 1! В общем случае, если имеется Х ключей и М списков, средний размер списка будет равен Ь7/М; значит, хеширование приводит к уменьшению среднего количества работы, необходимой для последовательного поиска, примерно в М раз (точная формула выводится в упр.
34). Этот метод представляет собой очевидную комбинацию обсуждавшихся ранее технологий, поэтому нет необходимости детально описывать алгоритм для хештаблиц с цепочками. Часто удобно хранить отдельные списки упорядоченными по ключам, что делает вставку и неудачный поиск более быстрыми. Так„если бы в приведенном примере использовались списки в порядке возрастания, то узлы ТО и ЕХВЕ на рис.
38 поменялись бы местами, а все ссылки Л были бы при этом заменены указателем на вспомогательную запись с ключом со (см. алгоритм 6.1Т). Другой подход предусматривает использование концепции "самоорганизованности", обсуждавшейся в разделе 6.1; записи могут быть упорядоченными не по значениям ключей списка, а по последнему времени обращения к ним. Для повышения быстродействия желательны большие значения М, однако в этом случае слишком многие списки будут пусты и будут зря расходовать память на содержание заголовков списков. При неболыпих размерах записей можно воспользоваться следующим подходом: совместить пространство для записей с пространством для заголовков списков, отводя место для М записей и М ссылок вместо места для Х записей и М + У ссылок. Иногда можно совершать проход по всем данным для поиска заголовков списков, которые будут использоваться, а затем при втором проходе вставлять "переполняющие" записи в пустые "щели".
Однако зачастую это непрактично или невозможно, поэтому хотелось бы иметь метод, работающий с каждой записью только раз — при ее помещении в систему. Следующий алгоритм, предложенный в работе Г. А. У9111!ашэ, САСАКИ 2,6 (Зппе, 1959), 21-24, позволяет быстро решить эту задачу. Алгоритм С (Поиск и вставка в ясш-таблице с цепочками). Этот алгоритм (рис. 39) ищет данный ключ К в таблице из М узлов.
Если К в таблице отсутствует, а таблица не заполнена, К вставляется в таблицу. Узлы таблицы обозначаются через ТАВЗЕН, О < 1 < М, и могут быть двух различных типов — пустссми и занятмми. В занятом узле содержатся поле ключа КЕТ[О, поле ссылки 1.1ВК [П и, возможно, другие поля. Алгоритм использует хеш<функцию А(К). Применяется также вспомогательная переменная В для упрощения поиска пустых мест; если таблица пуста, 11 = ЛХ + 1; по мере выполнения вставок всегда будет оставаться истинным утверждение, что узлы ТАВ1Е[у] заняты для всех у в диапазоне Л < З < М.
По соглашению узел ТАВ1.Е [0) всегда пуст, С1. )Хеширование.) Установиты в- Ь(К) +1. (Теперь 1 < 1 < М.) С2. )Есть ли списокТ) Если ТАВ[Е[1) пуст, перейти к шагу Сб. (В противном случае ТАВЕЕ Ы занят и мы приступим к поиску в списке, начинающемся в этом узле.) СЗ.
[Сравнение.) Если К = КЕТ [1), алгоритм успешно завершаетсн. С4. )Переход к следуя>щему.) Если 1.1КК Я ~ О, установиты +- Е1ЖК Ы и вернуться к шагу СЗ. Сб. )Поиск пустого узла.) (Поиск был неудачным, и необходимо найти пустое место в таблице.) Уменьшать В один или более раз, пока не будет найдено такое значение, при котором узел ТАВ[.Е[К) будет пуст. Если 11 = О, алгоритм завершается в связи с переполнением (свободных узлов больше нет); в противном случае установить |,ХИКСА ~- )т', 1 ~ — В. Переаекеееее Рис. 39. Поиск и вставка в хеш-таблице с цепочками. Сб.
[Вставка нового ключа.~ Пометить узел ТАВ[ЕИ как занятый с КЕТЫ ч- К и [.1ИК[г3 ч- О. $ Алгоритм позволяет объединить несколько списков, позтому записи не нужно перемещать после вставки в таблицу. Например, взгляните на рис. 40, на котором БЕКЕ попадает в список, содержащий Т0 и ГХВЕ, поскольку последний уже был вставлен в позицию 9. тлвьв[ц: тле[я[91: тлвькЫ: тля[в[41: тлв[лМ: тлвьк[е1: тлеьк[П: тле[в[91: тле[к[93: Рис. 40.
"Сросвиеся" цепочки. Дпя сравнения алгоритма С с другими алгоритмами втой главы можно написать следующую И1Х-программу. Выполненный анализ показал, что цепочки„как правило, коротки, и приведенная программа написана с учетом зтого факта. Программа С [Поиск и вставка е хеш-таблице с цепочками). Для удобства считаем, что ключи состоят из трех байтов, а узлы имеют следующий вид: Пустой узел Занятый узел В качестве размера таблицы М выбирается простое число; ТАВ[.ЕИ хранится по адресу ТАВ1Е + ю'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
