Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 39
Текст из файла (страница 39)
Хеш-функции. Для определенности в данном разделе предполагается, что хеш- функция имеет не более М различных значений, причем для всех ключей К 0 < л(К) < М. На практике ключи в реальном файле зачастую избыточны, а потому мы должны быть очень внимательны при поиске хеш-функции, чтобы не допустить создания кластеров из близких ключей с целью уменьшения количества коллизий. Теоретически невозможно определить хеш-функцию так„ чтобы она создавала случайные данные из реальных неслучайных файлов.
Однако на практике не твк уж сложно создать неплохую имитацию случайных данных с помощью простых арифметических действий, как обсуждалась в главе 3. В действительности зачастую можно достичь даже лучших результатов, находя и используя неслучайные свойства данных для построения хеш-функций с минимальным количеством коллизий (меньшим, чем при истинна случайных данных). Рассмотрим, например, десятизначные ключи на десятичном компьютере. Напрашивается следующий способ выбора хеш-функции: положить, скажем, М = 1000 и в качестве Ь(К) использовать три цифры, выбранные около средины двалцатизначного произведения К х К.
Казалось бы, этот метод данкен давать довольно равномерное распределение значений между 000 и 999 с низкой вероятностью коллизий, однако эксперименты с реальными данными показывают, что такой метод "середины квадрата" неплох при условии, что ключи не имеют большого количества нулей слева или справа. Подобно тому, как в главе 3 метод середины квадрата оказался не самым хорошим датчиком случайных чисел, но для него нашлись альтернативные методы, так и в нашем случае имеются более простые и надежные способы хеширования. Многочисленные тесты показали хорошую рабату двух основных типов хешфункций, один из которых основан на делении, а другой — на умножении. Метод деления весьма прост: мы просто используем остаток от деления на М: (2) Ь(К) = К пго»1 М. В этом случае очевидна, что, например, прн четном М значение Ь(К) будет четным при четном К и иечетньгм — при нечетном, что приведет к значительному смещению данных во многпх файлах.
Еще хуже обстоят дела, если М представляет собой степень основания счислении компьютера, поскольку при этом К гпо»1 М представлиет собой несколько цифр чиста К, расположенных справа, и не зависит от остальных цифр. Точно так же можно показать, что М не должно быть кратно трем, поскольку при буквенных ключах два из них, отличающиеся только перестановкой букв, могут давать числовые значения с разностью, кратной 3 (эта происходит, поскольку 2знто»13 = 1 и 10оша»13 = 1).
В целом, следует избегать значений М, делящих г' ш а, где Й и а — неболыцие числа, а т — "основание системы а счисления' набора используемых алфавитна-цифровых символов (обычно г = 64, 256 нли 100), так как остаток от делеющ по модулю на такие значения М зачастую представляет простую суперпозицню цифр ключа.
Приведенные рассуждения приводят к мысли, что лучше всего использовать в кочесгпвс М простое число, такое, что гв ~ шо (по модулю М) при небольших Ь и а. В большинстве случаев подобный выбор вполне удовлетворителен. Например, для й1Х-компьютера можно выбрать М = 1009, вычисляя Ь(К) при помощи следующих операций. 10Х Е гХ» — К. ЕИТА 0 гЛ+- О. (3) 019 =1009= гХ +- К пю»1 1009. Мультипликативная схема хеширования также просто реализуется, однако сложнее описывается, поскольку необходимо представить, что мы работаем с дробями, а не с целыми числами. Пусть ш — размер машинного словае (что в случае н1Х- компьютера обычно составляет 10'о илн 2зо). Целое число А можно рассматрпвать как дробь А/ш, если представить, что разделиющая точка (точка, разделяющая целую и дробную части числа в различных системах счисления, например десятичная точка) расположена слева от числа.
Метод состоит в выборе некоторой целой константы А, взаимно простой г ш, после чшо можно положить (4) В этом случае обычно на двоичном компьютере в качестве М используется степень двойки, так чта Ь(К) состоит из старших битов правой половины произведении .4К. " Напомним, чзо Л. Кнут поннмвег под размером машинного г чона не количество содержаогнхся в нем битов, а максямальное количество представляемых нм значеннй. Так, размер 32-бнтового слова!ВМ РС по Кнуту составляет 2"т = 4294967296. - Прим. нерее.
Для бннарного 81Х-компьютера, пшлагая, что М = 2™, хеш-функция вычисля- ется так. 10А К гА +- К. ИШ. А гАХ < — АК, ЕВТА О гАХ <- АКшойш, (5) 81.8 гл Сдвиг гАХ на т бнт влево. Вычисленное значение Ь(К) помещается в регистр А, Поскольку ИХХ достаточно медленно производит операции умножения и сдвига, программы (3) и (5) работают одинаковое время; однако на многих компьютерах умножение выполняется значительно быстрее деления. По сути, предложенный метод представляет собой обобщение метода (3), поскольку можно, например, в качестве А использовать приближение ю/1009; умножение на обратную величину зачастую происходит быстрее деления.
Технологня (5) практическн совпадает с методом середины квадрата, но с одннц важным отличием: в дальнейшем мы увндим, что умножение на подходящую константу имеет много полезных свойств. Одна нз привлекательных черт мультнпликативной схемы заключается в отсутствии потери информация в (5); мы в состоянии восстановнть значенне К по содержимому регистра гАХ по окончании работы (5). Дело в том, что А н ю взаямно просты и прн помощи алгоритма Евклида можно найти константу А', такую, что АА'шокам = 1; отсюда следует, что К = (А'(АКшодю)) шобю. Друтими словамн, если обозначить через,5(К) содержимое регистра Х непосредственно перед выполнением команды 81.В в (5), то Ке ф Ка повлечет у(К,) ~ у(Кз), (б) Конечно, у (К) принимает значения в диапазоне от 0 до ю -1, поэтому ее нельзя считать сколь-нибудь хорошей хеш-функцяей.
Однако она может быть весьма полезной в качестве рассеивающей функция (зсгашАйпд ~иие1юп), т. е. функции, удовлетворяющей (6) и обычно рандомизирующей ключн. Такая функция может зффектнвно использоваться и в связи с алгоритмами поиска по дереву нз раздела 6.2.2 (если порядок ключей не имеет значения), поскольку она предотвращает возможность построения вырожденного дерева в случае поступления ключей в порядке возрастания (см.
упр. 6.'2.2-10). Рассеиваю1цая функция может быть применена и для цифрового поиска по дереву из раздела 6.3 при смещении битов действительных ключей. Другое свойство мультипликативного хеш-метода состоит в том, что он хорошо использует то, что реальные файлы неслучайны. Например, часто множества ключей представляют собой арифметические прогрессии, когда в файле содержатся ключи (К, К+И, К+28,..., К+Я). Например, рассмотрим имена типа (РАВТ1, РАВТ2„РАВТЗ) нли (ТУРЕА,ТЕРЕВ,ПРЕС). Мультипликативный хеш-метод преобразует арифметическую прогрессию в приближенно арифметическую прогрессию Ь(К), Ь(К + сУ), Ь(К+ Ы), ... различных хеш-значений, уменьшая число коллнзнй по сравнению со случайной ситуацией.
Метод деления обладает тем же свойством. На рис. 37 пронллюстрирован этот аспект мультипликативного хеширования в интересном частном случае. Предположим, что А7ю приближенно равно золотому сечению А ' = (чг5 — 1)/2 0.6180339887; прн этом последовательность значений о О 1 2 3 4 5 6 7 3 Э 10 11 12 13 и Рис.
37. Хеширование Фибоиаччи. Ь(К), Ь(К + 1), Ь(К + 2), ... ведет себя точно так же, как последовательность хеш-значений Ь(0), Ь(1), Ь(2), ..., так что естественным становится следующий эксперимент: на отрезке (О.. 1] последовательно отмечаем точки (ф '), (26 (ЗС5 '), ..., где (х) означает дробную часть числа х (т. е. х — (х) или х шоб 1).
Как показано на рис. 57, эти точки достаточно хорошо отделены одна от другой; каждая вновь добавляемая точка попадает в один из наибольших оставшихся интервалов и делит его в соответствии с золотым сечением! (Данное явление было впервые замечено Я. Одерфельдом (2. ОбеНеЫ) и доказано С. Сверчковским (Б.
Ыегсх1готгзЫ), г)н11Ьшелга МаГЬ. 46 (1958), 187-189. В доказательстве важную роль играют числа Фибоначчи.) Это замечательное свойство золотого сечения в действительности является частным случаем более общей теоремы, предложенной Хьюго Штейигаузом (Надбо Бсе1пЬапе) и впервые доказанной Верой Туран Шош (Чета Тпгап Ббз) (Асга МагЬ. Асад. БН. Нилб.
8 (1957), 461-471; Алл. Уп1ю Бой Виг)арез1 Ео2163 Беса МагЬ. 1 (1958), 127-134). Теорема Б. Пусть д — произвольное иррациональное число. Прн размещении точек (д), (26), ..., (пд) на отрезке (О .. 1] длйны и + 1 образовавшихся отрезков имеют не более трех различных значений. Кроме того, очередная точка ((и+1) 6) попадет в адин лз нанболыпнх уже полученных отрезков. $ Таким образом, точки (д), (26),..., (пд) расположены между 0 и 1 досшточно равномерно. Воли д — рациональное число, то теорема остается верна (при подходящей интерпретации отрезков нулевой длины, которые образуются при и, большем или равном знаменателю 6). Доказательство теоремы Б вместе с подробным анализом сложившейся ситуации приводится в упр. 8.
Оказывается, что отрезки данной длины создаются и уничтожаются в порядке очереди ("первым вошел — первым вышел"; бгзг-ш-бгет-онг — НГО). Конечно, одни значения 6 лучше других; например, если д близкб к 0 или 1, сначала получим много маленьких отрезков и один болыпой. Вупр. 9показано, чтодвачигла,аименно — 4 ' и4 2 = 1 — б ' приводят к "наиболее равномерно распределенным" последовательностям среди всех чисел д между 0 и 1. Рассмотренная теория подводит нас к хешированию 1Рпбоначчи, при котором в качестве А берется ближайшее к ф 1п1 целое число, взаимно простое с кс Напри- мер, если бы ИХХ был десятичным компьютером, можно было бы воспользоваться множителем А= (7) Ои хорошо рассеивает алфавитные ключи типа Ь1БТ1, ЬТБТ2, 1.1БТЗ.
Однако при РассмотРении измЕнениЯ ключей в четвеРтОЙ поэиЦии — напРимеР, ББИ1о, БУИ2о, 80ИDŽ— получим, что рассеяние происходит так же, как если бы теорема Б использовалась с д = (100А/и ) = .80339887 вместо д = .6180339887 = А/ю. В результате данное рассеяние оказываетгл несколько хуже, чем при д = 4 ', хотя и остается достаточно хорошим. Однако в случае изменения во второй позиции ключа— А1 „„, А2,эль АЗ~,о — эффективное значение д равно .9887, что, пожалуй, слишком близко к 1. Поэтому можно было бы работать с множителем вместо множители (7); такой множитель будет хорошо разделять последовательности ключей, отличающиеся в любой позиции, К сожалению, подобный выбор приводит к новой проблеме, аналогичной возникающей при делении на гьх1: ключи типа ХТ и ТХ попадут при хешировании в одно и то же место! Один из путей обхода возникающих неприятностей начинается с более пристального рассмотрения структуры, лежащей в основе теоремы 8. Для коротких последовательностей ключей важны лишь несколько первых частичных отношений представлений 9 в виде цепной дроби, Маленькие частичные отношения соответствуют 'хорошим" свойствам распределения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
