AOP_Tom3 (1021738), страница 150
Текст из файла (страница 150)
В доказательстве, важную роль играют числа Фибоначчи.) Это замечательное свойство золотого сечения в действительности является частным случаем болев общей теоремы, предложенной Хьюго Штейнгаузом (Небо Вье1пЬапэ) и впервые доказанной Верой Туран Шош (Ъега Тпгйп Вбз) [Ас1а МасЬ. Асад. Всб Ннпб. 8 (1957), 461 — 471; Апп. Птю Всб Виоаречб Еойьоэ беси МазЬ. 1 (19о8), 127-134).
Теорема Б. Пусть  — произвольное иррациональное число. При раэмещезшн точек (В), (2В), ..., (иВ) на отрезке [О .. 1) длины и + 1 образовавшихся отрезков имеют не более трех различных значений, Кроме того, очередная точка ((и+1) В) попадет и одни пз наибольших уже полученных отрезков. Таким образом, точки (В), (2В),..., (иВ) расположены между 0 и 1 достаточно равномерно. Если  — рациональное число, то теорема остается верна (при подходящей интерпретации отрезков нулевой длины, которые образуются при и, большем или равном знаменателю В). Доказательство теоремы 8 вместе с подробным анализом сложившейся ситуации приводится в упр. 8. Оказывается, что отрезки данной длины создаются и уничтожаются в порндке очереди ("первым вошел — первым вышел"; бгэ14п-бгзыопс — ЕЛО).
Конечно, одни значения В лучше других; например, если В близкб к 0 или 1, сначала получим много маленьких отрезков и один большой. В упр. 9 показано, чтодва числа, аименно — ф ' и ф г = 1-ф ' приводят к "наиболее равномерно распределенным" последовательностям среди всех чисел В между 0 и 1. Рассмотренная теория подводит нас к хешированию Фибояаччи, при котором в качестве А берется ближайшее к ф 'ш целое число, взаимно простое с ш. Напри- мер, если бы И1Х был десятичным компьютером, можно было бы воспользоваться множителем (7) Он хорошо рассеивает алфавитные ключи типа Ь1811, 91ЯТ2, Ь1ЯТЗ. Однако при рассмотрении изменения ключей в четвертой позиции — — например, 8081о, 80И2сь ЯЗИЗо — получим, что рассеяние происходит так же, как если бы теорема 8 использовалась с В = (100А/<л) = .80339887 вместо В = .6180339887 = А/<л.
В результате данное рассеяние оказывается несколько хуже, чем при В = <А <, хотя и остается достаточно хорошим. Однако в случае <гэменения во второй позиции ключа А1„«о, А2««с,, АЗ«„~ — эффективное значение В равно.9887, что, пожалуй, слишком близко к 1. Поэтому можно было бы работать с множителем вместо множителя (7); такой множитель будет хороню разделять последовательности ключей, отличающиеся в любой позиции.
К сожалению, подобный выбор приводит к новой проблеме, аналогичной возникающей при делении на г" + 1: ключи типа ХУ и УХ попадут при хешировании в одно и то же место! Один из путей обхода возникающих неприятностей начинается с более пристального рассмотрения структуры, лежащей в основе теоремы 8. Для коротких последовательностей ключей важны лишь несколько первых частичных отношений представлений В в виде цепной дроби. Маленькие частичные отношения соответг<вуют "хорошим" свойствам распределения. Поэтому можно показать, что наилучшие значения В лежат в интервалах -<В— ' — « В«-, — В<-.
1 3 4 2 7 3 3 7' 7 3 <О 4' -<В<— 1 3 4 <а Значение А можно составить так, что каждый иэ его байтов будет находиться в "хорошем" интервале и будет не слишком близок к значениям других байтов (или их дополнениям), например (8) Такой множитель может быть смело рекомендован к использованию. (Изложенные в этом разделе идеи по мультипликативному хешированию в основном принэ<тлежат Р. В.
Флойду (1ь. %. Г<оу<)).) Хорошая хеш-функция должна удовлетворять двум требованиям. а) Ее вычисление должно выполняться очень быстро. Ь) Она должна минимизировать количество коллизий. Свойство (а) зависит от особенностей компьютера, а свойство (Ь) — от особенностей данных. Если бы все ключи были действительно случайными, можно было бы использовать несколько битов иэ них и с их помощью получить хеш-функцию; однако на практике для удовлетворения (Ь) требуется функция, зависящая от всех битов ключа.
До сих пор мы рассматривали хеширование "однословных" ключей. С ключами, состоящими из нескольких слов, и с ключами переменной длины можно работать, как с числами с многократной точностью и применять к ним все рассмотренные методы. Второй путь состоит в комбинировании слов в одно и в выполнении единственной операции умножения или деления, как описано выше. Эта комбинация может быть осуществлена путем сложения по модулю со или выполнения операции»исключающее или» бинарного компьютера.
Обе операции используют все биты обоих аргументов; "исключающее или", однако, предпочтительнее, поскольку позволяет избежать арифметического переполнения. Основной недостаток такого метода заключается в том, что указанные операции коммутативны, а значит, хеш-адресв (Х, У) н (1; Х) будут совпадать.
'1тобы устранить этот недостаток, Г. Д. Кнотт (6. О. Класс) предложил выполнять перед арифметической операцией циклический сдвиг. Еще лучпсий путь хеширования состоящих из 1 символов (или 1 слов) ключей К = хсхз... хс заключается в вычислении Ь(К) = (Ь,(хс) + Iсэ(хв) + . + Ьс(хс)) шас4 М, (9) К(х) шос1 Р(х) = Ь,» сх'» ~ + .. + 1цх+ Ьо, используя палиномиальпую арифметику по модулю 2. В таком случае Ь(К) (Ь» -с ..Ьс Ьв)сг При правильном выборе Р(х) эта хеш-функция может гарантировать отсутствие коллизий между почти одинаковыми ключами.
Например, при и = 15, пс = 10 и Р(х) = х' + х'+ хв + х" + х'+ х + 1 (10) где каждое Ь представляет собой независимую хеш-функцию. Эта идея, предложенная Лмс. Л. Картером (д. Е. Сагсег) и М. Н. Вегманом (М, Х. %еипсап) в 1977 году. в особенности эффективна, когда каждый хв представляет собой отдельный сссзсвол, поскольку в таком случае можно использовать предвычисленный массив для каждой функции Ь,. Такие массивы делают умножение ненужным. И если М представляет собой степень двойки, то в (9) можно избежать деления, используя "исключанзщее или» вместо сложения.
Таким образом, (9), определенно, удовлетворяет свойству (а). Более того, Картер и Ватман доказали, чта если Ь выбирается случайным образом, то будет выполняться и свойство (Ь) независимо от втоднмт данных (см. упр. 72). Было предложено и множество других методов хеширования, однако ни для одного из них нс было доказано его преимущество перед простыми методами, описанными выше.
Обзор некоторых методов с детальными характеристиками их производительности при работе с реальными файлами можно найти в статье 1'. У. 1лпп, Р. Я. Т. сссеп, апс1 М. Оос1с!, СЛСМ 14 (1971), 228 — 239. Из других интересных методов хеширования, видимо, наибольший интсрес представляет технология, основанная на алгебраической теории кодирования. Эта технология аналогична методу деления, описанному выше. однако вместо деления на целое число осупсествляется деление на полинам по модулю 2. (Как упоминалось в разделе 4.6, эта операция аналогична делению, как сложение аналогично операции "исключающее или".) В даннолс методе М должно представлять степень 2 (М = 2»с), и мы используем полинам пс-й степени Р(х) = х + р сх»' + ..
+ ро ицифравой бинарный ключ К = (к„с... Йс йо)з лсожно рассматривать как полинам К(х) = Ь„сх" ' + . + Йсх + Йв и вычислить остаток К = ЕН, Тб, ТЕБ,. АТЕЕ, ГЕИ, БЕКЕ, ЯТЧ (11) (представляющих числа от 1 до 7 на норвежском языке), имеющих хеш-коды 11(К) + 1 = 3, 1, 4, 1, 5, 9, 2 соответственно. В первом списке содержится два элемента, три списка пусты.
(12) НЕАО О]: НЕАО 12]. НЕАОСЗ]: НЕАО И]: ННАО1М: неАО1Я: НЕАО 17] ННАО 1э]: неАО1О]. Рис. 38. Раздельные цепочки. В связи с тем, что цепочки коротки, рассматриваемый здесь метод является весьма быстродействующим. Если Зб5 человек соберутся вместе в одной комнате, вероятно, окажется много пар, имеющих один и тот же день рождения, однако среднее количество людей с данным днем рождения равно только 1! В общем случае, если имеется 57 ключей и М списков, средний размер списка будет равен Х/М; значит, хеширование приводит к уменыпенню среднего количества работы, необходимой для последовательного поиска, примерно в М раз (точная формула выводится в упр.
34). можно показать, что Ь(К1 ) будет всегда отлично от Ь(КА), если К1 и Кх — различные ключи, отличающиесн менее чем семью битами. (Дополнительная информация по этой теме приводится в упр. 7; в данном случае, конечно, батее уместна аппарат ная или микропрограммная реализация, а не программная.) Очень часто удобно использовать постояннук1 хеш-функцию Ь(15) = 9 в процессе отладки программы, так как все ключи будут храниться вместе; эффективная хеш-функция Ь(К) может бьггь подставлена позже. Разрешение коллизий методом "цепочек'! Мы уже говорили, что некоторые хеш-адреса могут быть одинаковыми для различных ключей. Вероятно, самый очевидный путь решении этой проблемы — поддержка М связных списков, по одному для каждого возможного значения хеш-кода.
Поле ПИК должно быть включено в каждую запись; кроме того, следует иметь М головных узлов списков, перенумерованных, скажем, от 1 до М. После хеширования ключа мы просто выполняем последовательный поиск в списке номер Ь(К) + 1. (Обратитесь к упр. 6.1 — 2. Ситуация весьма напоминает сортировку методом вставок в несколько списков; см. программу 5.2.1М.) На рнс. 38 показана простая схема с цепочками при М = 9 для последовательности нз ключей Этот метод представляет собой очевидную комбинацию обсуждавшихся ранее технологий, поэтому нет необходимости детально описывать алгоритм для хештаблиц с цепочками. Часто удобно хранить отдельные списки упорядоченными по ключам, что делает вставку и неудачный поиск более быстрыми.
Так, если бы в приведенном примере использовались списки в порядке возрастания, то узлы ТО и Г1ВЕ на рис. 38 поменялись бы местами, а все ссылки А были бы при этом заменены указателем на вспомогательную запись с ключом аа (см, алгоритм 6.1Т).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
