logo search
Высокоцровневые методы информатики и првые методы информатики и программированияограммирования

4.4 Способы построения хеш – функций Выбор хорошей хеш-функции

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

для j=0,1,…,m – 1 (4.1)

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

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

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

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

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