мер, если бы MIX был десятичным компьютером, можно было бы воспользоваться множителем

Он хорошо рассеивает алфавитные ключи типа LIST1, LIST2, LISTS. Однако при рассмотрении изменения ключей в четвертой позиции - например, SUMlu, SUM2u, SUMSu - получим, что рассеяние происходит так же, как если бы теорема S использовалась св = [ША/ги] - .80339887 вместо в = .6180339887 = A/w. В результате данное рассеяние оказывается несколько хуже, чем при в - ф~, хотя и остается достаточно хорошим. Однако в случае изменения во второй позиции ключа - Aluuu) A2uuuj ASuuu - эффективное значение в равно .9887, что, пожалуй, слишком близко к 1.

Поэтому можно было бы работать с множителем

вместо множителя (7); такой множитель будет хорошо разделять последовательности ключей, отличающиеся в любой позиции. К сожалению, подобный выбор приводит к новой проблеме, аналогичной возникающей при делении на г*±1: ключи типа XY и УХ попадут при хешировании в одно и то же место! Один из путей обхода возникающих неприятностей начинается с более пристального рассмотрения структуры, лежащей в основе теоремы S. Для коротких последовательностей ключей важны лишь несколько первых частичных отношений представлений в в виде цепной дроби. Маленькие частичные отношения соответс i вуют "хорошим" свойствам распределения. Поэтому можно показать, что наилучшие значения в лежат в интервалах

1<

<1

Значение А можно составить так, что каждый из его байтов будет находиться в "хорошем" интервале и будет не слишком близок к значениям других байтов (или их дополнениям), например

Такой множитель может быть смело рекомендован к использованию. (Изложенные в этом разделе идеи по мультипликативному хешированию в основном принадлежат Р. В. Флойду (R. W. Floyd).)

Хорошая хеш-функция должна удовлетворять двум требованиям.

a) Ее вычисление должно выполняться очень быстро.

b) Она должна минимизировать количество коллизий.

Свойство (а) зависит от особенностей компьютера, а свойство (Ь) - от особенностей данных. Если бы все ключи были действительно случайными, можно было бы использовать несколько битов из них и с их помощью получить хеш-функцию; однако на практике для удовлетворения (Ь) требуется функция, зависящая от всех битов ключа.

До сих пор мы рассматривали хеширование "однословных" ключей. С ключами, состоящими из нескольких слов, и с ключами переменной длины можно работать.

как с числами с многократной точностью и применять к ним все рассмотренные методы. Второй путь состоит в комбинировании слов в одно и в выполнении единственной операции умножения или деления, как описано выше. Эта комбинация может быть осуществлена путем сложения по модулю w или вьшолнения операции "исключающее или" бинарного компьютера. Обе операции используют все биты обоих аргументов; "исключающее или" однако, предпочтительнее, поскольку позволяет избежать арифметического переполнения. Основной недостаток такого метода заключается в том, что указанные операции коммутативны, а значит, хеш-адреса {X, Y) и (F, X) будут совпадать. Чтобы устранить этот недостаток, Г. Д. Кнотт (G. D. Knott) предложил выполнять перед арифметической операцией циклический сдвиг.

Еще лучший путь хеширования состоящих из I символов (или / слов) ключей К = х\Х2 XI заключается в вычислении

h{K) = {hi{xi) + h2{x2) + + hi{xi)) mod M, (9)

где каждое hj представляет собой независимую хеш-функцию. Эта идея, предложенная Дж. Л. Картером (J. L. Carter) и М. Н. Вегманом (М. N. Wegman) в 1977 году, в особенности эффективна, когда каждый Xj представляет собой отдельный си.\шол, поскольку в таком случае можно использовать предвычисленный массив для каждой функции hj. Такие массивы делают умножение ненужным. И если М представляет собой степень двойки, то в (9) можно избежать деления, используя "исключающее или" вместо сложения. Таким образом, (9), определенно, удовлетворяет свойству (а). Более того. Картер и Вегман доказали, что если hj выбирается случайным образом, то будет выполняться и свойство (Ь) независимо от входных данных (см. упр. 72).

Было предложено и множество других методов хеширования, однако ни для одного из них не было доказано его преимущество перед простыми методами, описанными выше. Обзор некоторых методов с детагшными характеристиками их производительности при работе с реальными файлами можно найти в статье V. Y. Lum, Р. S. Т. Yuen, and М. Dodd, САСМ 14 (1971), 228-239.

Из других интересных методов хеширования, видимо, наибольший интерес представляет технология, основанная на алгебраической теории кодирования. Эта технология аналогична методу деления, описанному выше, однако вместо деления на целое число осуществляется деление на полином по модулю 2. (Как упоминалось в разделе 4.6, эта операция аналогична делению, как сложение аналогично операции "исключающее или") В данном методе М должно представлять степень 2 (М = 2™), и мы используем полином т-й степени Р{х) = х™ + Pm-ix"~ + -I-ро- п-цифровой бинарный ключ К = (fc„ i... fci fco)2 можно рассматривать как полином К{х) = кп-\х~ +----\-kix + ко и вычислить остаток

К{х) mod Р{х) = /i-ia;"- + + Цх + ho,

используя полиномиальную арифметику по модулю 2. В таком случае h{K) = (/im i .../11/10)2- При правильном выборе Р{х) эта хеш-функция может гарантировать отсутствие коллизий между почти одинаковыми ключами. Например, при п = 15, m = 10 и

Р{х) = а;1° + ж + 2) + ж" + + а; 4-1 (10)

можно показать, что h{Ki) будет всегда отлично от h{K2), если Ki и К2 - различные ключи, отличающиеся менее чем семью битами. (Дополнительная информация по этой теме приводится в упр. 7; в данном случае, конечно, более уместна аппаратная или микропрограммная реализация, а не программная.)

Очень часто удобно использовать постоянную хеш-функцию h{K) = О в процессе отладки программы, так как все ключи будут храниться вместе; эффективная хеш-функция h{K) может быть подставлена позже.

Разрешение коллизий методом "цепочек". Мы уже говорили, что некоторые хеш-адреса могут быть одинаковыми для различных ключей. Вероятно, самый очевидный путь решения этой проблемы - поддержка М связных списков, по одному для каждого возможного значения хеш-кода. Поле LINK должно быть включено в каждую запись; кроме того, следует иметь М головных узлов списков, перенумерованных, скажем, от 1 до М. После хеширования ключа мы просто выполняем последовательный поиск в списке номер h{K) + 1. (Обратитесь к упр. 6.1-2. Ситуация весьма напоминает сортировку методом вставок в несколько списков; см. программу 5.2.1М.)

На рис. 38 показана простая схема с цепочками при М = 9 для последовательности из ключей

К = EN, ТО, TRE, FIRE, FEM, SEKS, SYV (11)

(представляющих числа от 1 до 7 на норвежском языке), имеющих хеш-коды

/i(if) + 1 = 3, 1, 4, 1, 5, 9, 2 (12)

соответственно. В первом списке содержится два элемента, три списка пусты.

HEADC1] HEAD[2] HEAD[3] HEAD[4] HEAD[5] HEAD[6] HEAD[7] HEAD[8] HEAD[9]

FIRE

Рис. 38. Раздельные цепочки.

В связи с тем, что цепочки коротки, рассматриваемый здесь метод является весьма быстродействующим. Если 365 человек соберутся вместе в одной комнате, вероятно, окажется много пар, имеющих один и тот же день рождения, однако среднее количество людей с данным днем рождения равно только 1! В общем случае, если имеется ключей и М списков, средний размер списка будет равен N/M; значит, хеширование приводит к уменьшению среднего количества работы, необходимой для последовательного поиска, примерно в М раз (точная формула выводится в упр. 34).