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

12.3. Хеш-функции

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

Какой должна быть хорошая хеш-функция?

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

Е PW = t Для j = 0,l,...,m-l.(12.1)

k:h(k)=jт

К сожалению, распределение Р обычно неизвестно, так что проверить это невозможно (да и ключи не всегда разумно считать независимыми).

Изредка распределение Р бывает известно. Пусть, например, ключи - случайные действительные числа, независимо и равномерно распределённые на интервале [0; 1). В этом случае легко видеть, что хеш-функция h(k) = [km\ удовлетворяет условию (12.1).

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

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

функцией распределения Р, то такой метод даёт хорошие результаты.

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

Ключи как натуральные числа

Обычно предполагают, что область определения хеш-функции - множество целых неотрицательных чисел. Если ключи не являются натуральными числами, их обычно можно преобразовать к такому виду (хотя числа могут получиться большими). Например, последовательности символов можно интерпретировать как числа, записанные в системе счисления с подходящим основанием: идентификатор pt - это пара чисел (112,116) (таковы ASCII-коды букв р и t), или же число (112 • 128) + 116 = 14452 (в системе счисления по основанию 128). Далее мы всегда будем считать, что ключи - целые неотрицательные числа.

12.3.1. Деление с остатком

Построение хеш-функции методом деления с остатком (division method) состоит в том, что ключу к ставится в соответствие остаток от деления к на то, где то - число возможных хеш-значений:

h(k) = к mod то.

Например, если размер хеш-таблицы равен то = 12 и ключ равен 100, то хеш-значение равно 4.

При этом некоторых значений то стоит избегать. Например, если то = 2Р, то h(k) - это просто р младших битов числа к. Если нет уверенности, что все комбинации младших битов ключа будут встречаться с одинаковой частотой, то степень двойки в качестве числа то не выбирают. Нехорошо также выбирать в качестве то степень десятки, если ключи естественно возникают как десятичные числа: ведь в этом случае окажется, что уже часть цифр ключа полностью определяет хеш-значение. Если ключи естественно возникают как числа в системе счисления с основанием 2Р, то нехорошо брать то = 2р - 1, поскольку при этом одинаковое хеш-значение имеют ключи, отличающиеся лишь перестановкой «2р-ичных цифр».

Хорошие результаты обычно получаются, если выбрать в качестве то простое число, далеко отстоящее от степеней двойки. Пусть, например, нам надо поместить примерно 2000 записей в

Переводы надписей: w bits - w битов; extract р bits - выделить р битов. ВНИМАНИЕ: на рисунке надо УБРАТЬ знаки целой части, заменив [А 2W \ на А 2W !!!!!!!

Рис. 12.4 Хеширование методом умножения. Ключ к, представленный в виде го-битного числа, умножается на го-битное число А 2W, где А - константа из интервала (0; 1). У произведения берут младшие w битов, а из этих w битов выделяют р старших. Это и есть хеш-значение h(k).

хеш-таблицу с цепочками, причем нас не пугает возможный перебор трёх вариантов при поиске отсутствующего в таблице элемента. Что ж, воспользуемся методом деления с остатком при длине хеш-таблицы то = 701. Число 701 простое, 701 ~ 2000/3, и до степеней двойки от числа 701 тоже далеко. Стало быть, можно выбрать хеш-функцию вида

h(k) = к mod 701.

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

12.3.2. Умножение

Построение хеш-функции методом умножения (multiplication method) состоит в следующем. Пусть количество хеш-значений равно то. Зафиксируем константу А в интервале 0 < А < 1, и положим

h(k) = [т(кА mod 1) ,

где к A mod 1 - дробная часть к А.

Достоинство метода умножения в том, что качество хеш-функции мало зависит от выбора то. Обычно в качестве то выбирают степень двойки, поскольку в большинстве компьютеров умножение на такое то реализуется как сдвиг слова. Пусть, например, длина слова в нашем компьютере равна w битам и ключ к помещается в одно слово. Тогда, если то = 2Р, то вычисление хеш-функции можно провести так: умножим к на w-битное целое число А 2W (мы предполагаем, что это число является целым); получится 2«?-битное число

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