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

Многочисленные тесты показали хорошую работу двух основных типов хеш-функций, один из которых основан на делении, а другой - на умножении.

Метод деления весьма прост; мы просто используем остаток от деления на М:

h{K) = К mod М. (2)

В этом случае очевидно, что, например, при четном М значение h{K) будет четным при четном К и нечетным - при нечетном, что приведет к значительному смещению данных во многих файлах. Еще хуже обстоят дела, если М представляет собой степень основания счисления компьютера, поскольку при этом К mod М представляет собой несколько цифр числа К, расположенных справа, и не зависит от остальных цифр. Точно так же можно показать, что М не должно быть кратно трем, поскольку при буквенных ключах два из них, отличающиеся только перестановкой букв, могут давать числовые значения с разностью, кратной 3 (это происходит, поскольку 2"mod3 = 1 и 10" mod 3 = 1). В целом, следует избегать значений М, делящих ± а, где к и а - небольшие числа, а г - "основание системы счисления" набора используемых алфавитно-цифровых символов (обычно г = 64, 256 или 100), так как остаток от деления по модулю на такие значения М зачастую представляет простую суперпозицию цифр ключа. Приведенные рассуждения приводят к мысли, что лучше всего использовать в качестве М простое число, такое, что г ф ±а (по модулю М) при небольших к па. В большинстве случаев подобный выбор вполне удовлетворителен.

Например, для MIX-компьютера можно выбрать М = 1009, вычисляя h{K) при помощи следующих операций.

LDX К гХ<г-К.

ENTA О гА <- 0. (3)

DIV =1009= гХ <-А" mod 1009. Мультипликативная схема хеширования также просто реализуется, однако сложнее описывается, поскольку необходимо представить, что мы работаем с дробями, а не с целыми числами. Пусть w - размер машинного слова* (что в случае MIX-компьютера обычно составляет 10" или 2). Целое число А можно рассматривать как дробь A/w, если представить, что разделяющая точка (точка, разделяющая целую и дробную части числа в различных системах счисления, например десятичная точка) расположена слева от числа. Метод состоит в выборе некоторой целой константы А, взаимно простой с w, после чего можно положить

h{K) =

( (А \ \ Ml (-Л" modi W )

В этом случае обычно на двоичном компьютере в качестве М используется степень двойки, так что h{K) состоит из старших битов правой половины произведения АК.

* Напомним, что Д. Кнут понимает под размером машинного слова не количество содержащихся в нем битов, а максимальное количество представляемых им значений. Так, размер 32-битового слова IBM PC по Кнуту составляет 22 = 4 294 967 296. - Прим. перев.

Для бинарного MIX-компьютера, полагая, что М = 2"*, хеш-функция вычисляется так.

LDA К гА 4- А".

MUL А rAX4-Aii:. ...

ENTA О гАХ 4- АА" mod w.

SLB m Сдвиг гАХ на т бит влево.

Вычисленное значение h{K) помещается в регистр А. Поскольку MIX достаточно медленно производит операции умножения и сдвига, программы (3) и (5) работают одинаковое время; однако на многих компьютерах умножение вьшолняется значительно быстрее деления.

По сути, предложенный метод представляет собой обобщение метода (3), поскольку можно, например, в качестве А использовать приближение w/1009; умножение на обратную величину зачастую происходит быстрее деления. Технология (5) практически совпадает с методом середины квадрата, но с одним важным отличием: в дальнейшем мы увидим, что умножение на подходящую константу имеет много полезных свойств.

Одна из привлекательных черт мультипликативной схемы заключается в отсутствии потери информации в (5); мы в состоянии восстановить значение К по содержимому регистра гАХ по окончании работы (5). Дело в том, что А п w взаимно просты и при помощи алгоритма Евклида можно найти константу А, такую, что ААmod w = 1; отсюда следует, что К = [А{АК mod w)) mod w. Другими словами, если обозначить через f{K) содержимое регистра X непосредственгю перед выполнением команды SLB в (5), то

Ki ф К2 повлечет f{Ki)f{K2). (6)

Конечно, f{K) принимает значения в диапазоне от О до w-1, поэтому ее нельзя считать сколь-иибудь хорошей хеш-функцией. Однако она может быть весьма полезной в качестве рассеивающей функции {scrambling function), т. е. функции, удовлетворяющей (6) и обычно рандомизирующей ключи. Такая функция может эффективно использоваться и в связи с алгоритмами поиска по дереву из раздела 6.2.2 (если порядок ключей не имеет значения), поскольку она предотвращает возможность построения вырожденного дерева в случае поступления ключей в порядке возрастания (см. упр. 6.2.2-10). Рассеивающая функция может быть применена и для цифрового поиска по дереву из раздела 6.3 при смещении битов действительных ключей.

Другое свойство мультипликативного хеш-метода состоит в том, что он хорошо использует то, что реальные файлы неслучайны. Например, часто множества ключей представляют собой арифметические прогрессии, когда в файле содержатся ключи {К, K+d, K+2d,..., K+td}. Например, рассмотрим имена типа {PART1, PART2, PART3} или {TYPEA, TYPEB, TYPEC}. Мультипликативный хеш-метод преобразует арифметическую прогрессию в приближенно арифметическую прогрессию h{K), h{K + d), h{K + 2d), ... различных хеш-значений, уменьшая число коллизий по сравнению со случайной ситуацией. Метод деления обладает тем же свойством.

На рис. 37 проиллюстрирован этот аспект мультипликативного хеширования в интересном частном случае. Предположим, что A/w приближенно равно золотому сечению = (\/5 - 1)/2 ~ 0.6180339887; при этом последовательность значений

о 1 2 3 4 5 6 7 8 9 10 11 12 13 n Рис. 37. Хеширование Фибоначчи.

ЦК), h{K + I), h{K + 2), ... ведет себя точно так же, как последовательность хеш-значений h{0), h{l), h(2), так что естественным становится следующий эксперимент: на отрезке [0..1] последовательно отмечаем точки {ф"}, {2ф~}, {Зф}, ..., где {х} означает дробную часть числа х (т. е. а; - [х\ или а; mod 1). Как показано на рис. 37, эти точки достаточно хорошо отделены одна от другой; каждая вновь добавляемая точка попадает в один из наибольших оставшихся интервалов и делит его в соответствии с золотым сечением! [Данное явление было впервые замечено Я. Одерфельдом (J. Oderfeld) и доказано С. Сверчковским (S. Swierczkovvski), Fundamenta Math. 46 (1958), 187-189. В доказательстве важную роль играют числа Фибоначчи.]

Это замечательное свойство золотого сечения в действительности является частным случаем более общей теоремы, предложенной Хьюго Штейнгаузом (Hugo Steinhaus) и впервые доказанной Верой Туран Шош (Vera Turan Sos) [Acta Math. Acad. Sci. Hung. 8 (1957), 461-471; Ann. Univ. Sci. Budapest. Eotvos Sect. Math. 1 (1958), 127-134].

Теорема S. Пусть в - произвольное иррациональное число. При размещении точек {в}, {2в}, {пв} на отрезке [О.. 1] длины п + 1 образовавшихся отрезков имеют не более трех различных значений. Кроме того, очередная точка {{п+1)в} попадет в один из наибольших уже полученных отрезков.

Таким образом, точки {в}, {2в},..., {пв} расположены между О и 1 достаточно равномерно. Если в - рациональное число, то теорема остается верна (при подходящей интерпретации отрезков нулевой длины, которые образуются при п, большем или равном знаменателю в). Доказательство теоремы S вместе с подробным анализом сложившейся ситуации приводится в упр. 8. Оказывается, что отрезки данной длины создаются и уничтожаются в порядке очереди ("первым вошел - первым вышел"; first-in-first-out - FIFO). Конечно, одни значения в лучше других; например, если в близко к О или 1, сначала получим много маленьких отрезков и один большой. В упр. 9 показано, что два числа, а именно - ф" и ф~ = 1-ф~ приводят к "наиболее равномерно распределенным" последовательностям среди всех чисел в между О и 1.

Рассмотренная теория подводит нас к хешированию Фибоначчи, при котором в качестве А берется ближайшее к ф~и1 целое число, взаимно простое с w. Напри-