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

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

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

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

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

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

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

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

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

Алгоритм деления

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

h(x) = x mod N .

Здесь N – размер хеш-таблицы, так что вычисленное значение индекса будет в пределах от 0 до N–1, как принято в программах на C. Если массив описан от 1 до N (как обычно бывает в Паскале), то нужно еще прибавить к индексу единицу.

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

Поясним сказанное таким примером. Пусть N = 10 000, а значения всех используемых ключей заканчиваются на 0. Очевидно, что тогда и все значения h(x) тоже будут заканчиваться на 0, т.е. будет использоваться лишь 1/10 часть всех позиций таблицы, что приведет к частым коллизиям.

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