Функции хеширования

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

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

12.4.1 Хеш-функции для целочисленных ключей

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

h(Кey) = КeyMod N.

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

2) Значение хеш-функции, использующей метод умножения, формируется следующим образом. Допустим, что число позиций в таблице, обозначаемое как N, равно целой степени числа 2, т. е. N =2ⁿ, где n – целое. Представим хешируемый ключ Кey в виде двоичного числа, умножим его на некоторое заранее выбранное значение a и выделим в произведении Кey*a дробную часть. Обозначим эту дробную часть как {Кey*a}. В методе умножения в качестве значения хеш-функции принимается значение, представленное n старшими разрядами двоичного представления {Кey*a}. Иными словами,

h(Кey) = ]N×{Кey*a}[ ,

где ]х[ - наибольшее целое, не превосходящее х.

Заметим, что в методе умножения, во-первых, в качестве значения a рекомендуется использовать иррациональное число, которое близко к длине машинного слова; хорошие результаты дает значение a=(Sqrt(5)-1)/2, где Sqrt - функция вычисления квадратного корня; во-вторых, требование, заключающееся в том, чтобы N была целой степенью двойки, необязательно.

3) В методе преобразования системы счисления ключ представляется в некоторой р-ичной системе счисления:

Кey = d₀ + d₁×p + d₂×p² + …

Выбирается основание q новой системы счисления такое, что q < p. Пусть s – некоторое целое число. Тогда для метода преобразования системы счисления значение хеш-функции вычисляется в новой системе счисления со «старыми» коэффициентами:

h(Кey) = d₀ + d₁×q + d₂×q² + … + d_S-1×q^S-1 .

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

4) Для хеш-функции, использующей метод деления многочленов, рассматривается значение ключа, выраженное в двоичной системе счисления, которое записывается так:

Кey = b₀ + b₁×2 + b₂×2² + … + b_m-1×2^m-1,

и ключ представляется в виде многочлена

Кey(t) = b₀ + b₁×t + b₂×t² + … + b_m-1×t^m-1,

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

C(t) = c₀ + c₁×t + c₂×t² + … + c_m-1×t^m-1,

В качестве значения хеш-функции используется остаток от деления Кey(t)на C(t), рассматриваемый в двоичной системе счисления. Если в качестве C(t)выбрать простой неприводимый многочлен, то при key1 ¹ key2 обязательно выполнится условие h(key1) ¹ h(key2), т. е. эта хеш-функция обладает сильным свойством рассеивания скученности.

5) При использовании метода, известного какметод середины квадрата, ключ умножается сам на себя и в качестве индекса используется несколько средних цифр этого квадрата. Если данный квадрат рассматривается как десятичное число, то размер таблицы должен быть некоторой степенью 10, а если он рассматривается как двоичное число, то размер таблицы должен быть степенью 2. Причиной возведения числа в квадрат до извлечения средних цифр является то, что все цифры первоначального числа дают свой вклад в значение средних цифр квадрата.

6) Приметодесвертки ключ разбивается на несколько сегментов, над которыми выполняется операция сложения или нетождественности для формирования хеш-функции. Например, предположим, что внутреннее представление некоторого ключа в виде последовательности разрядов имеет вид 010111001010110 и для индекса отводится пять двоичных разрядов. Над тремя последовательностями разрядов 01011, 10010 и 10110 выполняется операция нетождественности:

01011 11001

10010 10110

11001 01111- результат применения операции нетождественности,

что дает 01111или двоичное представление числа 15. (Операциянетождественности двух разрядов дает 1, если значения этих двух разрядов различны, и 0, если значения их равны.)

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

12.4.2 Хеш-функции для строковых ключей

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

В методе слияния для создания некоторого целого числа используется порядковый номер в ANSI-последовательности каждой буквы. Так, заглавная буква русского алфавита ’И’ представляется цифрами 200, а малая буква ’в’ представляется цифрами 226. Ключ «Иван» после слияния всех номеров букв представляется целым числом 200226224237. Когда существует некоторое целое представление строки символов, то для сведения его к приемлемому размеру может быть использован метод свертки или середины квадрата.

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

Function SimpleHash(Const aKey: String;
N: Integer): Integer;

Var i: Integer;

Hash: LongInt;

Begin

Hash:= 0;

For i:= 1 To Length(aKey) Do

Hash:= ((Hash*17) + Ord(aKey[i])) Mod N;

Result:= Hash;

If Result < 0 Then Inc(Result, N);

End;

Эта подпрограмма воспринимает два параметра: первый из них - хешируемая строка, второй - число ячеек в таблице. Алгоритм по циклу изменяет переменную Hash, умножая ее текущее значение на простое число 17 и прибавляя порядковый номер i-ого символа; завершается изменение делением по модулю на размер таблицы. Заключительный If требуется потому, что промежуточное значение переменной может быть отрицательным, а программа, вызывающая эту функцию, ожидает получить результат, значение которого находится в диапазоне от 0 до N-1.