З.1.Хеш-таблицы

Для работы с словарем требуются поиск, вставка и удаление. Один из наиболее эффективных способов реализации словаря - хеш-таблицы. Среднее время поиска элемента в них есть 0(1), время для наихудшего случая - О(п). Прекрасное изложение хеширования можно найти в работах Кормена[2] и Кнута[1]. Чтобы читать статьи на эту тему, вам понадобится владеть соответствующей терминологией. Здесь описан метод, известный как связывание или открытое хеширование[3]. Другой метод, известный как замкнутое хеширование[3] иёё заёбибау адресация[1], здесь не обсуждаются. Ну, как?

Теория

Хеш-таблица - это обычный массив с необычной адресацией, задаваемой хеш-функцией. Например, на hashTable рис. 3.1 - это массив из 8 элементов. Каждый элемент представляет собой указатель на линейный список, хранящий числа. Хеш-функция в этом примере просто делит ключ на 8 и использует остаток как индекс в таблице. Это дает нам числа от 0 до 7 Поскольку для адресации в hashTable нам и нужны числа от 0 до 7, алгоритм гарантирует допустимые значения индексов.

HashтaЫe

 

 

 

 

 

 

0

 

 

#

 

 

 

 

 

 

 

 

1

#

 

16

 

 

 

2

#

 

 

 

 

 

3

 

 

 

 

 

 

#

 

 

 

 

 

 

4

#

 

11

 

27

 

19

5

#

 

 

 

 

 

6

 

 

 

 

#

 

 

 

 

 

 

7

#

 

22

 

6

 

Рис. 0.1: Хеш-таблица

Чтобы вставить в таблицу новый элемент, мы хешируем ключ, чтобы определить список, в который его нужно добавить, затем вставляем элемент в начало этого списка. Например, чтобы добавить 11, мы делим 11 на 8 и получаем остаток 3. Таким образом, 11 следует разместить в списке, на начало которого указывает hashTaЫe[3]. Чтобы найти число, мы его хешируем и проходим по соответствующему списку. Чтобы удалить число, мы находим его и удаляем элемент списка, его содержащий.

Если хеш-функция распределяет совокупность возможных ключей равномерно по множеству индексов, то хеширование эффективно разбивает множество ключей. Наихудший случай - когда все ключи хешируются в один индекс. При этом мы работаем с одним линейным списком, который и вынуждены последовательно сканировать каждый раз, когда что-нибудь делаем. Отсюда видно, как важна хорошая хеш-функция. Здесь мы рассмотрим лишь несколько извозможных подходов. При иллюстрации методов предполагается, что unsigned char располагается в 8 бедах, unsigned short int - в 16, unsigned long int - в 32.

• Деление (размер таблицы hashTableSize - простое число). Этот метод использован в последнем примере. Хеширующее значение hashValue, изменяющееся от 0 до (hashTableSize - 1), равно остатку от деления ключа на размер хеш-таблицы. Вот как это может выглядеть:

typedef int hashlndexType;

hashlndexType hash(int Key) {

return Key % hashTableSize;

}

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

• Мультипликативный метод (размер таблицы hashTableSize есть степень 2n). Значение Key умножается на константу, затем от результата берется необходимое число

битов. В качестве такой константы Кнут[1] рекомендует золотое сечение       -1) /2 =

0.6180339887499. Пусть, например, мы работаем с байтами. Умножив золотое сечение на 28, получаем 158. Перемножим 8-битовый ключ и 158, получаем 16-битовое целое. Для таблицы длиной 25 в качестве хеширующего значения берем 5 младших битов младшего слова, содержащего такое произведение. Вот как можно реализовать этот метод:

/* 8-bit index */

typedef unsigned char hashlndexType; static const hashlndexType K = 158;

/* 16-bit index */

typedef unsigned short int hashlndexType; static const hashlndexType K = 40503;

/* 32-bit index */

typedef unsigned long int hashlndexType; static const hashlndexType K = 2654435769;

/* w=bitwidth(hashIndexType),  size of table=2**m */ static const int S = w - m;

hashlndexType hashValue =  (hashIndexType)(K * Key)   >> S;

Пусть, например, размер таблицы hashTableSize равен 1024 (210). Тогда нам достаточен 1б-битный индекс и S будет присвоено значение 1б - 10 = б. В итоге получаем:

typedef unsigned short int hashlndexType;

hashIndexType hash(int Key) {

static const hashlndexType K = 40503;

static const int S = 6;

return  (hashIndexType)(K * Key)   >> S;

}

а Аддитивный метод для строк переменной длины (размер таблицы равен 256). Для строк переменной длины вполне разумные результаты дает сложение по модулю 25б. В этом случае результат hashValue заключен между 0 и 244.

typedef unsigned char hashlndexType;

hashIndexType hash(char *str) { hashlndexType h = 0; while   (*str)  h += *str++; return h;

}

а Исключающее ИЛИ для строк переменной длины (размер таблицы равен 256). Этот метод аналогичен аддитивному, но успешно различает схожие слова и анаграммы (аддитивный метод даст одно значение для XY и YX). Метод, как легко догадаться, заключается в том, что к элементам строки последовательно применяется операция "исключающее или". В нижеследующем алгоритме добавляется случайная компонента, чтобы еще улучшить результат.

typedef unsigned char hashlndexType; unsigned char Rand8[256];

hashIndexType hash(char *str) { unsigned char h = 0;

while   (*str)  h = Rand8[h л *str++]; return h;

}

Здесь Rand8 - таблица из 25б восьмибитовых случайных чисел. Их точный порядок не критичен. Корни этого метода лежат в криптографии; он оказался вполне эффективным [4].

а Исключающее ИЛИ для строк переменной длины (размер таблицы < 65536). Если мы хешируем строку дважды, мы получим хеш-значение для таблицы любой длины до б553б. Когда строка хешируется во второй раз, к первому символу прибавляется 1. Получаемые два 8-битовых числа объединяются в одно 1б-битовое.

typedef unsigned short int hashlndexType; unsigned char Rand8[256];

hashIndexType hash(char *str) { hashlndexType h; unsigned char hi, h2;

if  (*str == 0)   return 0; hi = *str; h2 = *str + 1;

str++;

while   (*str) {

hi = Rand8[h1 л *str]; h2 = Rand8[h2 л *str]; str++;

}

/* h is in range 0..65535 */

h =  ((hashIndexType)h1 << 8)|(hashIndexType)h2; /* use division method to scale */ return h % hashTableSize

}

Размер хеш-таблицы должен быть достаточно велик, чтобы в ней оставалось разумное число пустых мест. Как видно из таблицы 3.1, чем меньше таблица, тем больше среднее время поиска ключа в ней. Хеш-таблицу можно рассматривать как совокупность связанных списков. По мере того, как таблица растет, увеличивается количество списков и, соответственно, среднее число узлов в каждом списке уменьшается. Пусть количество элементов равно n. Если размер таблицы равен 1, то таблица вырождается в один список длины n. Если размер таблицы равен 2 и хеширование идеально, то нам придется иметь дело с двумя списками по n/100 элементов в каждом. Как мы видим в таблице 3.1, имеется значительная свободы в выборе длины таблицы.

size time size time

_1 869 128 _9_

_2 432 256 _6_

_4 214 512 _4_

_8 106 1024 _4_

_16 54 2048 _3_

32 28 4096 _3_

64 I 15 I   8192 I T

Таблица 0.1: Зависимость среднего времени поиска (us) от hashTableSize.

Сортируются 4096 элементов.

Реализация алгоритма на Си находится в разделе 4.5. Операторы typedef T и compGT следует изменить так, чтобы они соответствовали данным, хранимым в массиве. Для работы программы следует также определить hashTableSize и отвести место под hashTable. В хеш-функции hash использован метод деления. Функция insertNode отводит память под новый узел и вставляет его в таблицу. Функция deleteNode удаляет узел и освобождает память, где он располагался. Функция findNode ищет в таблице заданный ключ.