Хеш-таблицы

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

Теория

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


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

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

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

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

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


HashIndexType Hash(char *str) {
    HashIndexType h;
    unsigned char h1, h2;


    if (*str == 0) return 0;
    h1 = *str; h2 = *str + 1;
    str++;
    while (*str) {
        h1 = 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, имеется значительная свободы в выборе длины таблицы.
размер время размер время
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 15 8192 3

Таблица 3.1: Зависимость среднего времени поиска (µs) от hashTableSize. Сортируются 4096 элементов.

Реализация

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