в вычислении целого числа, меньшего Л/, использовались все разряды ключа. В программе 14.1 показан один из способов выполнения этого: использование простого основания вместо степени 2, связанного с задействованием целого числа, которое соответствует ASCII-представлению строки. На рис. 14.5 показано, как это изменение препятствует плохому распределению типовых строковых ключей. Теоретически хеш-значения, созданные программой 14.1, могут не подходить для размеров таблицы, которые кратны числу 127 (хотя на практике это, скорее всего, скажется минимальным образом); для создания рандомизованного алгоритма можно было бы выбрать значение множителя наугад. Еще более эффективный подход - использование случайных значений коэффициентов в вычислении и другого случайного значения для каждой цифры ключа. Такой подход дает рандомизованный алгоритм, называемый универсальным хешированием.

Теоретически идеальная универсальная хеш-функция - это функция, для которой вероятность конфликта между двумя различными ключами в таблице размером М равна в точности 1/Л/. Можно доказать, что использование в качестве коэффициента а в профамме 14.1 последовательности случайных различных значений вместо фиксированного произвольного значения преобразует модульное хеширование в универсальную хеш-функцию. Однако затраты на генерирование нового случайного числа для каждого символа в ключе, скорее всего, окажутся неприемлемыми. В прбфамме 14.2 продемонстрирован практический компромисс: мы варьируем коэффициенты, генерируя простую псевдослучайную последовательность.

Профамма 14.2 Универсальная хеш-функция (для строковых ключей)

Эта программа выполняет те же вычисления, что и программа 14.1, однако для аппроксимации вероятности возникновения конфликтов для двух несовпадающих ключей до значения 1/М вместо фиксированных оснований системы счисления применяются псевдослучайные значения коэффициентов. С целью минимизации нежелательных временных затрат при вычислении хеш-функции используется грубый генератор случайных чисел.

int hashU(char *v, int М) { int h, a = 31415, b = 27183; for (h = 0; *v != 0; v++, a = a*b % (M-1))

h = (a*h + *v) % M; return (h < 0) ? (h + M) : h;

РИСУНОК 14.5 ХЕШ-ФУНКЦИИ для СИМВОЛЬНЫХ СТРОК

На этих диаграммах показано распределение для набора английских слов (первых 1000 слов романа Мелвилла Моби Дик ) в случае применения программы 14.1 при

М = 96 w а = 128 (вверху) М = 97 w а = 128 (в центре) и М = 96 м а = 127 (внизу) Неравномерное распределение в первом случае является результатом неравномерного употребления букв и того, что и размер таблицы, и множитель кратны 32, что ведет к сохранению неравномерности. Остальные два примера выглядят случайными, поскольку размер таблицы и множитель являются взаимно простыми числами.

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

inline int hash (Key v, int M)

{ return (int) M* (v-s)/(t-s) ; }

выполняет эту задачу для ключей с плаваюшей точкой, имеющих значения между s и /; для целочисленных ключей можно просто вернуть значение v % М. Если М не является простым числом, хеш-функция может возвращать

(int) (.616161 * (float) v) % М

или результат аналогичного целочисленного вычисления, такой как

(16161 * (unsigned) v) % М

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

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

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

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

inline int hash (Key v, int M) { return V & (M-1); }

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

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

Для проверки гипотезы, что хеш-функция создает случайные значения, можно использовать функцию статистического распределения (см. упражнение 14.5), но, возможно, это требование - слишком жесткое. Действительно, нас вполне может удовлетворить, если хеш-функция создает каждое значение одинаковое количество раз, что соответствует значению функции статистического распределения yj, равному О, и местами не является случайным. Тем не менее, следует с подозрением относиться к очень большим значениям функции статистического распределения у}. На практике, вероятно, достаточно использовать проверку того, что значения распределены до такой степени, чтобы ни одно из значений не доминировало (см. упражнение 14.15).

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

Упражнения

> 14.1 Используя абстракцию digit из главы 10 для обработки машинного слова как последовательности байтов, реализуйте рандомизованную хеш-функцию для ключей, которые представлены разрядами в машинных слова.

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