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

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

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

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

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

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

Var

i: Integer;

s: string[10];

Begin

s[1]:=chr(random(90-65)+65);

for i:=2 to 10 do

s[i]:=chr(random(122-97)+97);

end;

В примере допустимые коды символов располагаются последовательными непрерывными участками в кодовой таблице. Рассмотрим общий случай. Допустим, необходимо сгенерировать ключ из m символов с кодами в диапазоне от n1 до n2 (диапазон непрерывный):

for i:=1 to m do

str[i]:=chr(random(n2-n1)+n1);

На практике возможны варианты, когда символы в одних позициях ключа могут принадлежать к разным диапазонам кодов, причем между этими диапазонами может существовать разрыв. Пример генерации ключа из m символов с кодами в диапазоне от n1 до n4 с разрывом от n2 до n3 (рис. 8.3) приведен ниже.

Рис. 8.3. Диапазон кодов ключа.

for i:=1 to m do

Begin

x:=random((n4-n3)+(n2-n1));

if x <= (n2-n1) then

str[i]:=chr(x+n1) else

str[i]:=chr(x+n1+n3-n2);

end;