AOP_Tom3 (1021738), страница 149
Текст из файла (страница 149)
Хеш-функции. Для определенности в данном разделе предполагается, что хеш- функция имеет не более М различных значений, причем для всех ключей К 0<0(К) < М. На практике ключи в реальном файле зачастую избыточны, а потому мы должны быть очень внимательны при поиске хеш-функции, чтобы не допустить создания кластеров из близких ключей с целью уменьшения количества коллизий. Теоретически невозможно определить хеш-функцию так, чтобы она создавала случайные данные из реальных неслучайных файлов. Однако на практике не так уж сложно создать неплохую имитацию случайных данных с помощью простых арифметических лействий, как обсуждалось в главе 3.
В действительности зачастую можно достичь даже лучших результатов, находя и используя неслучайные свойства данных для построения хеш-функций с минимальным количеством коллизий (меньшим, чем при истинно случайных данных). Рассмотрим, например, десятизначные ключи на десятичном компьютере. Напрашивается следующий способ выбора хеш-функции: положить, скажем, М = 1000 и в качестве 6(К) использовать три цифры, выбранные около средины двадцатизначного произведения К х К. Казалось бы, этот метод должен давать довольно равномерное распределение значений между 000 и 999 с низкой вероятностью коллизий, однако эксперименты с реальными данными показывают, что такой метод "середины квадрата' неплох при условии, что ключи пе имеют большого количества Содержимое г11 -9 — 9 -9 -15 -16 -9 — 9 -9 -15 — 16 — 2 5 6 — 7 -18 — 2 5 6 -7 -18 29 .
. 25 4 29 5 б 2э 4 29 5 6 25 4 20 20 -16 -23 -16 -23 — 5 — 23 -5 -23 30 1 ЗО 1 30 1 — 26 -26 -14 — 14 — 14 -10 -10 -23 -23 — 23 — 23 — 23 -23 -23 -23 1 1 1 1 1 1 -22 — 18 — 22 -18 -6 2 -6 2 -б 2 — 2 -2 с определенным -23 -26 -26 -23 -26 -26 -15 -ЗЗ -26 -15 -33 -26 17 -16 -2 17 -16 -2 17 — 16 -2 -22 -21 -22 -21 11 -1 11 — 1 11 -1 -5 — 26 -28 -26 -28 — 25 -20 — 25 -20 0 12 0 12 0 12 — 5 8 — 5 8 29 29 29 11 11 21 21 8 21 8 21 8 нулей слева или справа. Подобно тому, как в главе 3 метод середины квадрата оказался не самым хорошим датчиком случайных чисел, но для него нашлись альтернативные методы, так и в нашем случае имеются более простые и надежные способы хеширования.
Многочисленные тесты показали хорошую работу двух основных типов хешфункций, один из которых основан на делении, а другой — на умножении. Метод деления весьма прост; мы просто используем остаток от деления на М: (2) Ь(К) = К гпос1 и. 1.РХ К гХ +- К. ЕМТЛ 0 гА е- О. 019 =1009= гХ +- К шос1 1009. (3) Мультипликатнвная схема хеширования также просто реализуется, однако сложнее описывается, поскольку необходимо представить, что мы работаем с дробями, а не с целыми числами. Пусть ш — размер машинного слона" (чта в случае И1Х- компьютера обычно составляет 10го или 2зо). Целое число А можно рассматривать как дробь А/ш, еглн представить, что разделяющая точка (точкв, разделяющая целую и дробную части числа в различных системах счисления, например десятичная точка) расположена слева от числа.
Метод состоит в выборе некоторой целой константы А, взаимно простой с ю, после чего можно положить (4) В этом случае обычно иа двоичном компьютере в качестве ЛХ используется степень двойки, так что Ь(К) состоит из старших битов правой половины произведения АК. " Напомним, что Д. Кнут понимает под размером машквного слова не количество содержащихся в нем битов, а максимальное количество нредетввляемых нм значений. Твк, рвзмер 92-бнтового олова 1ВМ РС по Кнуту составляет 2зз = 4 2949б7299. — Прим. нерее.
В этом случае очевидно, что, нюзример, при четном М значение Л(К) будет четным при четном К и нечетным — при нечетном, что приведет к значительному смещению данных во многих файлах. Еще хуже обстоят дела, если М представляет собой степень основания счисления компьютера, поскольку при этом К шос1 М представляет собой несколько цифр числа К, расположенных справа, и не зависит от остальных цифр. Точно так же можно показать, что ЛХ не должно быль кратно трем, поскольку при буквенных ключах два нз них, отличающиеся только перестановкой букв, могут девать числовые значения с разностью, кратной 3 (это происходит, поскольку 2 о шос(3 = 1 и 10нпюс13 = 1). В целом, следует избегать значений М., делящих г' ш и, где 74 н а — небольшие числа, а г ".
"основание системы ь счисления" набора используемых алфавитна-цифровых символов (обычно г = 64, 256 или 100), так как остаток от деления по модулю на такие значении М зачастую представляет простую суперпозицию цифр ключа. Приведенные рассуждения приводят к мысли, что лучше всего использовать ы качестве М простое ~недо, такое, что гв ~ ша (па модулю Л1) при небольпшх й и а.
В большинстве случаев подобный выбор вполне удовлетворителен. Например, для И1Х-коезпьютера можно выбрать М = 1009, вычисляя 74(К) при помощи следующих операций. Для бинарного П1Х-компьютера, полагая, что Ы = 2, хеш-функция вычисляется так. 1.0А К гА е-К. ИШ. А гАХ ~- АК. ЕНОТА О гАХ+- АК шайи. (5) БЕВ гп Сдвиг гАХ иа гл бит влево. Вычисленное значение Ь(К) помещается в регистр А. Поскольку И1Х достаточно медленно производит операции умножения и сдвига, программы (3) и (5) работают одинаковое время: однако на многих компьютерах умножение выполняется значительно быстрее деления.
По сути, предложенный метод представляет собой обобщение метода (3), поскольку можно, например, в качестве Л использовать приближение в/1009; умножение на обратную величину зачастую происходит быстрее деления. Технология (5) практически совпадает с методом середины квадрата, но с одним важным отличием: в дальнейшем мы увидим, что умножение на подходящую константу имеет много полезных свойств. Одна иэ привлекательных черт мультипликативной схемы заключается в отсутствии потери информации в (5); мы в состоянии восстановить значение К по содержимому регистра гАХ по окончании работы (5). Дело в том, что Л и ш взаимно просты и при помощи алгоритма Евклида можно найти константу Л', такую, что ЛЛ'шог1 ю = 1; отсюда следует, что К = (Л'(ЛКшог1ш)) щоби>.
Другими словами, если обозначить через /(К) содержимое регистра Х непосредственно перед выполнением команды ЗЕВ в (5), то К, ~ Кэ повлечет /(Кг) ф /(Кэ). (6) Конечно, /(К) принимает значения в диапазоне от 0 до и~ — 1, поэтому ее нельзя считать сколь-нибудь хорошей хеш-функцией. Однако она может быть весьма полезной в качестве Рассеивающей в5уикции (эсгаш51гпй /ипсйпп), т. е.
функции, удовлетворяющей (6) и обычно рандомизирующей ключи. Такая функция может эффективно использоваться и в связи с алгоритмами поиска по дереву из раздела 6.2.2 (если порядок ключей не имеет значения), поскольку она предотвращает возможность построения вырожденного дерева в случае поступления ключей в порядке возрастания (см. упр. 6.2.2-10). Рассеивающая функция может быть применена и для цифрового поиска по дереву из раздела 6.3 при смещении битов действительных юпочей. Другое свойство мультипликативного хеш-метода состоит в том, что он хорошо использует то, что реальные файлы неслучайны. Например, часто множества ключей представляют собой арифметические прогрессии, когда в файле содержатся ключи (К, К+0, К+2г1,..., К+И).
Например, рассмотрим имена типа (РАЕТ1, РАВТ2, РАЕТЗ) или (ТУРЕА,ТЕРЕВ,ТЕРЕС). Мультипликативный хе~в-метод преобразует арифметическую прогрессию в приближенно арифметическую прогрессию Ь(К), 5(К + И), й(К ч- 26), ... различных хеш-значений, уменьшая число коллизий по сравнению со случайной ситуацией. Метод деления обладает тем же свойством.
На рис. 37 проиллюстрирован этот аспект мультипликативного хеширования в интересном частном случае. Предположим, что Л/и приближенно равно золотому сечению 4 г = (ьД вЂ” 1)/2 = 0.6180339887; при этом последовательность значений (еф ~) о Е 1 г З 4 З Е 7 З Э Га и Ш ЭЗ и Рнс. 37. Хеширование Фибоначчи. Ь(К), Ь(К + 1), Ь(К + 2), ... ведет себя точно так же, как последовательность хеш-значений Ь(0), Ь(1), Ь(2), ..., так что естественным становится следующий эксперимент; на отрезке [0..1) последовательно отмечаем точки (ф '), (2ф ~)., (Зф '), ..., где (х) означает дробную часть числа х (т. е.
х — [х) или х той 1). Как показано на рис. 37, эти точки достаточно хорошо отделены одна от другой; каждая вновь добавляемая точка попадает в один из наибольших оставшихся интервалов и делит его в соответствии с золотым сечением! [Данное явление было впервые замечено Я. Одерфельдом (3. Ооег(е1о) и доказано С. Сверчковскнм (8. 6кчегсз1сошз1о), Ропоатеп1а МаНь 46 (1958), 187 — 189.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
