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

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

Существует много способов создания функций хеширования, использующих преобразование произвольного натурального числа к натуральному индексу, лежащему в заданном диапазоне 0..m. Поэтому перед хешированием значения ключей приводятся к натуральному значению, если по своей природе они таковыми не являются. Например, последовательности ASCII-символов можно интерпретировать как целые числа, записанные в системе счисления с основанием 256. Вещественные числа можно привести к натуральному типу с некоторой заданной точностью, предварительно умножив на соответствующую степень 10.

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

Хеш-функция, основанная на выборе цифр, формирует хеш-значение, как комбинацию отдельных цифр ключа. Например, для хеш-таблицы с размером m = 1000 из 12-значного ключа можно выбрать первую, шестую и двенадцатую цифры. Запись этих цифр в позиционной десятичной системе и будет представлять хеш-значение, лежащее в диапазоне от 0 до 999. Но такой способ хеширования оправдывает себя, если ключи элементов, вставляемых в таблицу, равномерно распределены на всём диапазоне значений.

Метод свёртки группирует цифры ключа и складывает группы цифр по модулю m. Например, для m = 1000 ключ 123342954451 можно преобразовать по схеме:

123 + 342 + 954 + 451 = 870.

Можно применять свёртку, комбинированную с выбором цифр. Например, сначала выполняется простое суммирование групп цифр ключа, а из полученной суммы выбирается нужное количество цифр.

Метод деления с остатком (модульное хеширование) даёт простые и эффективные хеш-функции. Ключу k ставится в соответствие остаток от деления k на m. Хеш-функция вычисляется, как уравнение h(k) = k mod m.

Mетод хорошо работает, если в качестве m выбирать простые числа, далеко отстоящие от степени двойки. Ниже приведены рекомендуемые размеры хеш-таблиц (числа Мерсенне) для модульного хеширования [8]:

Таблица 2

2^n		2^n - 
8	5	251
9	3	509
10	3	1 021
11	9	2 039
12	3	4 093
13	1	8 191
14	3	16 381
15	19	32 749
16	15	65 521
17	1	131 071
18	5	262 139
19	1	524 287
20	3	1 048 573
21	9	2 097 143
22	3	4 194 301
23	15	8 388 593
24	3	16 777 213
25	39	33 554 393

Метод умножения (мультипликативный) вычисляет хеш- функцию по формуле

h(k) = m (kA mod1)

, где A- некоторая константа, удовлетворяющая условию 0 < A <1, kA mod1 – дробная часть произведения k A.

Достоинство метода умножения заключается в том, что качество хеш-функции мало зависит от выбора m. Но обычно в качестве m выбирают степень двойки, так как в большинстве компьютеров умножение на степень двойки реализуется быстро, как сдвиг слова. Метод умножения работает при любом выборе константы А, но некоторые значения А могут быть лучше других. Удачным значением является число – «золотое сечение» [4]:

А = ( - 1)/2  0,6180339887

Если ключ является строкой символов произвольной длины, то можно применить преобразование строки к натуральному числу и затем применить к этому числу один из описанных выше методов. Но такой способ хеширования не всегда себя оправдывает. Существуют специальные методы хеширования строк. Например, если строки включают только заглавные буквы латинского алфавита, то каждой букве от A до Z можно поставить в соответствие числа от 1 до 26. Строка символов заменяется конкатенацией битовых образов этих чисел, соответствующих символам строки. К десятичному значению получившейся битовой последовательности можно применить любой из описанных выше методов хеширования [3].

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

² = m/P (f _i –P/m)²

, где P – количество ключей, использованных для получения распределения, m- размер хеш - таблицы, f _i - количество ключей с хеш-значением, равным i [8].

Если использованные ключи являются случайными на всём пространстве значений ключей U, значение функции ² должно быть равно m  с вероятностью 1 - 1/c, где c=U/m.