Общие требования к хеш-функциям

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

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

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

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

Во-вторых, если множество ключей, реально встретившихся в конкретной задаче, неравномерно распределено по всему множеству допустимых ключей X, то эта неравномерность должна устраняться при хешировании.

Поясним подробнее. Что понимается под неравномерностью распределения ключей? Если речь идет о числовых ключах, то может, например, оказаться, что большая часть ключей лежит в небольшом диапазоне или что в качестве ключей часто используются «круглые» числа, или, скажем, все ключи – четные числа. Если ключами являются российские фамилии, то можно ожидать много значений, заканчивающихся на «-ов», «-ин», «-ский» и т.п., при этом фамилий на букву «К» наверняка будет намного больше, чем на «Ф» или «Щ». Если ключи – даты рождения студентов, то почти все они будут сгруппированы в пределах одного десятилетия. Во всех этих примерах требуется, чтобы хеш-функция «разбросала» ключи более или менее равномерно по всей хеш-таблице, поскольку любое сгущение значений в некоторой части таблицы приведет к более частым коллизиям и к трудностям при их разрешении.

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

Рассмотрим наиболее известные методы хеширования числовых ключей.