Основная причина выбора в качестве размера М хеш-таблицы простого числа для модульного хеширования иллюстрируется на рис. 14.3. В этом примере символьных данных с 7-разрядным кодированием ключ трактуется как число с основанием 128 - по одной цифре для каждого символа в ключе. Слово now соответствует числу 1816567, которое может быть также записано как

ПО- 128+ 111 128+ 119-128

поскольку в ASCII-коде символам п, о и w соответствуют числа 156 = ПО, 1578= 1 11 и 1678= 119. Далее, выбор размера таблицы Л/ = 64 неудачен для этого типа ключа, поскольку добавление к х значений, кратных 64 (или 128), не оказывает влияния на значение х mod 64 - для любого ключа значением хеш-функции является значение последних 6 разрядов этого ключа. Безусловно, хорошая хеш-функция должна учитывать все разряды ключа, особенно для ключей, образованных символами. Аналогичные ситуации могут возникать, когда М содержит множитель, являющийся степенью 2. Простейший способ избежать этого - выбрать в качестве М простое число.

Модульное хеширование весьма просто реализовать, за исключением того, что размер таблицы необходимо определить простым числом. Для некоторых приложений можно довольствоваться небольшим известным простым числом или же поискать простое число, близкое к требуемому размеру таблицы, в списке известных простых чисел. Например, числа равные 2- 1 являются простыми при t= 2, 3, 5, 7, 13, 19 и 31 (и ни при каких других значениях t < 31): это хорошо известные простые числа Мерсенне (Mersenne). Чтобы динамически распределить таблицу определенных размеров, нужно вычислить простое число, близкое к определенному значению. Это вычисление не тривиально (хотя и существует остроумный алгоритм выполнения этой задачи, который исследуется в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульнЬго хеширования - не единственная причина, по которой размер таблицы определяется простым числом; другая причина рассматривается в разделе 14.4.

РИСУНОК 14.3 МОДУЛЬНЫЕ ХЕШ-ФУНКЦИИ ДЛЯ КОДИРОВАННЫХ СИМВОЛОВ

в каждой строке этой таблицы приведены 3-символьное слово, представление этого слова в ASCII-коде как 21-разрядное число в восьмеричной и десятичной формах и стандартные модульные хеш-функции для таблицы с размерами 64 и 31 (два крайних справа столбца). Размер таблицы, равный 64, приводит к нежелательным результатам, поскольку для получения хеш-значения используются только самые правые разряды ключа, а символы в словах обычного языка распределены неравномерно. Например, всем словам, завершаюш,имся на букву у, соответствует хеш-значение 57. И напротив, простое значение 31 вызывает меньше конфликтов в таблице, размер которой составляет менее половины предыдуш,ей.

Другая альтернатива обработки целочисленных ключей - объединение мультипликативного и модульного методов: следует умножить ключ на константу в диапазоне между О и 1, а затем выполнить деление по модулю М. Другими словами, необходимо использовать функцию h{k) = Vka.\ mod М. Между значениями а. Л/ и эффективным основанием ключа существует взаимодействие, которое теоретически могло бы привести к аномальному поведению, но если использовать умеренное значение а, в реальном приложении вряд ли придется столкнуться с какой-либо проблемой. Часто в качестве а выбирают значение ф = 0.618033... {золотое сечение). Изучено множество других вариаций на эту тему, в частности хеш-функции, которые могут быть реализованы с помощью таких эффективных машинных инструкций, как сдвиг и маскирование {см. раздел ссылок).

Во многих приложениях, в которых используются таблицы символов, ключи не являются числами и не обязательно являются короткими; чаще они оказываются алфавитно-цифровыми строками, которые могут быть длинными. Как вычислить хеш-функцию для такого слова, как

averylongkey?

В 7-разрядном А8СИ-коде этому слову соответствует 84-разрядное число

97-128 + 118- 128°+ 101 1284 114- 128 121 128 + 108 1284 111 128 + 110 1284 103 128 + 107-1284 101- 1284 121 128

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

Чтобы вычислить модульную хеш-функцию для длинных ключей, последние преобразуются фрагмент за фрагментом. Можно воспользоваться арифметическими свойствами функции mod и задействовать алгоритм Гор-нера (Ногпег) (см. раздел 4.9).

РИСУНОК 14.4 ПРОСТЫЕ ЧИСЛА ДЛЯ ХЕШ-ТАБЛИЦ

Эта таблица наибольших простых чисел, которые меньше 2 для 8 < л < 32, может использоваться для динамического распределения хеш-таблицы, когда требуется, чтобы размер таблицы определялся простым числом. Для любого данного положительного значения в указанном диапазоне эту таблицу можно использовать для получения простого числа, отличающегося от него менее чем в 2 раза.

Этот метод основывается на еще одном способе записи чисел, соответствующих ключам. Для рассматриваемого примера запишем следующее выражение:

((((((((((97- 128 + 118)-128 + 101)-128 + 114)-128 + 121)-128 + 108)-128 + 111)- 128 + ПО)- 128 + 103)- 128 + 107)-128 + 101)- 128 + 121.

То есть, можно вычислить десятичное число, соответствующее коду символа строки при просмотре ее слева направо, умножая полученное значение на 128, а затем добавляя кодовое значение следующего символа. Со временем, в случае длинной строки, этот способ вычисления создал бы число, которое больше того, которое вообще можно представить в компьютере. Однако вычисленное число нас не интересует, поскольку требуется только остаток от его деления на Л/, который мал. Результат можно получить, даже не сохраняя большое накопленное значение, т.к. в любой момент вычисления можно отбросить число, кратное М - при каждом выполнении умножения и сложения нужно хранить только остаток деления по модулю М. Результат такой же, как если бы у нас имелась возможность вычислять длинное число, а затем выполнять деление (см. упражнение 14.10). Это наблювение ведет к непосредственному арифметическому способу вычисления модульных хеш-функций для длинных строк (см. программу 14.1). В программе используется еще одно, последнее ухищрение: вместо основания 128 в ней используется простое число 127. Причина такого изменения рассматривается в следующем абзаце.

Программа 14.1 Хеш-функция для дроковых ключей

Эта реализация хеш-функции для строковых ключей требует одного умножения и одного сложения на каждый символ в ключе. Если бы константу 127 мы заменили константой 128, программа просто вычисляла бы остаток от деления числа, соответствующего 7-разрядному ASCII-представлению ключа, на размер таблицы с использованием метода Горнера. Простое основание, равное 127, помогает избежать аномалий, если размер таблицы является степенью 2 или кратным 2.

int hash (char *v, int M) { int h = 0, a = 127; for (; *v != 0; v++) h = (a*h + *v) % M; return h;

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