Хеш-адресация

Данный метод в целом более эффективен, чем линейные списки, и используется для таблиц символов в большинстве случаев [13]. Схема открытого хеширования (хеш-таблица размера 211) приведена на рис.5.16. Структура данных состоит из двух частей – хеш-таблицы и блоков.

1. Хеш-таблица представляет собой фиксированный массив из m указателей на записи таблицы.

2. Записи таблицы организованы в виде m отдельных связанных списков, именуемых блоками (некоторые блоки могут быть пустыми).

Каждая запись в таблице символов встречается только в одном из этих списков.

Для определения, существует ли в таблице символов запись для строки s, мы вычисляем хеш-функцию h от строки s, возвращающую целое число от 0 m-1. Если строка s имеется в таблице символов, то она находится в списке с номером h(s). Если s в таблице символов еще отсутствует, то она вносится в таблицу путем создания записи в начале списка с номером h(s) [13].

Используя такой алгоритм можно сделать время обращения к элементу таблицы константой. Пусть средняя длина списка при n записях в таблице символов и хеш-таблице размера m —m/n. Можно выбрать m настолько большим, чтобы n/m было ограничено небольшой величиной, например 2.

Пространство, занимаемое таблицей символов определяется как m+cn, где с – количество слов в одной записи таблицы символов.

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

 

 

Массив заголовков

списков, индексируемый

хеш-значением

Список элементов, созданный для указанных имён

 

 

Рис. 5.16.

 

Текст хеш-функции из компилятора С. Вайнбергера на языке С [13]:

int RHeshTable::hashpjw(char *s)

{ char *p;

unsigned int h = 0, q;

for (p=s;*p!=0;p++)

{ q = (h=(h<<4)+*p);

if(h & 0xF0000000)

h^=q >> 24^q; }

return h%211; }

Рис. 5.17.