Оценка качества хеш-функции

Begin

Var

Begin

Var

i: Integer;

Hash: LongInt;

Hash:=0;

for i:=1 to Length(aKey) do

Hash:=((Hash*17)+ord(aKey[i])) mod aTableSize;

Result:=Hash;

if Result < 0 then

Inc(Result, aTableSize);

end;

Функция принимает в качестве параметров значение строкового ключа и размер таблицы. Алгоритм поддерживает постоянно изменяющееся хеш-значение, изначально установленное равным нулю. Это значение изменяется для каждого символа в строке путем его умножения на небольшое простое число, добавления кода следующего символа и деления по модулю на размер таблицы. Если конечное значение окажется отрицательным (особенность операции деления по модулю в Delphi), к результату добавится значение размера таблицы.

Другая известная функция, именуемая ELF-хешем (формат исполняемых и компонуемых модуле, Executable and Linking Foramt), была предложена П.Дж.Вайнбергером. Отличие алгоритма от приведенного выше заключается в применении эффекта рандомизации, когда операция XOR вновь загружает старший полубайт действующей рабочей переменной хеша (полубайт, который должен исчезнуть в результате переполнения при выполнении следующей операции умножения), если он не равен нулю, в младшую часть переменной. Затем старший полубайт устанавливается в ноль, в результате чего хеш-значение никогда не будет неотрицательным.

function SimpleHash(aKey: string; aTableSize: Integer): Integer;

i: Integer;

G,Hash: LongInt;

Hash:=0;

for i:=1 to Length(aKey) do

Hash:=(Hash shl 4)+ord(aKey[i]);

G:=Hash and LongInt($F0000000);

if G <> 0 then

Hash:=(Hash xor (G shr 24)) xor G;

Result:=Hash mod aTableSize;

end;

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

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

Рис. 8.2. Распределение коллизий в адресном пространстве таблицы.

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

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

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

Дата добавления: 2014-01-07