Cтруктуры данных. Хранение информации.

Хеш-таблицы

Теория. Открытое Хеширование

Хеш-таблица - это обычный массив с необычной адресацией, задаваемой хеш-функцией.

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

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

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

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

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

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

typedef int HashIndexType;

HashIndexType Hash(int Key) {
    return Key % HashTableSize;
}

Для успеха этого метода очень важен выбор подходящего значения hashTableSize. Если, например, hashTableSize равняется двум, то для четных ключей хеш-значения будут четными, для нечетных - нечетными. Ясно, что это нежелательно - ведь если все ключи окажутся четными, они попадут в один элемент таблицы. Аналогично, если все ключи окажутся четными, то hashTableSize, равное степени двух, попросту возьмет часть битов Key в качестве индекса. Чтобы получить более случайное распределение ключей, в качестве hashTableSize нужно брать простое число, не слишком близкое к степени двух.
• Мультипликативный метод (размер таблицы hashTableSize есть степень 2ⁿ). Значение key умножается на константу, затем от результата берется необходимое число битов. В качестве такой константы Кнут рекомендует золотое сечение (sqrt(5) - 1)/2 = 0.6180339887499. Пусть, например, мы работаем с байтами. Умножив золотое сечение на 28, получаем 158. Перемножим 8-битовый ключ и 158, получаем 16-битовое целое. Для таблицы длиной 25 в качестве хеширующего значения берем 5 младших битов младшего слова, содержащего такое произведение. Вот как можно реализовать этот метод:

/* 8-bit index */
typedef unsigned char HashIndexType;
static const HashIndexType K = 158;
  
/* 16-bit index */
typedef unsigned short int HashIndexType;
static const HashIndexType K = 40503;
  
/* 32-bit index */
typedef unsigned long int HashIndexType;
static const HashIndexType K = 2654435769;
  
/* w=bitwidth(HashIndexType), size of table=2**m */
static const int S = w - m;
HashIndexType HashValue = (HashIndexType)(K * Key) >> S;

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

typedef unsigned short int HashIndexType;
  
HashIndexType Hash(int Key) {
    static const HashIndexType K = 40503;
    static const int S = 6;
    return (HashIndexType)(K * Key) >> S;
}

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

typedef unsigned char HashIndexType;

HashIndexType Hash(char *str) {
    HashIndexType h = 0;
    while (*str) h += *str++;
    return h;
}

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

typedef unsigned char HashIndexType;
unsigned char Rand8[256];
  
HashIndexType Hash(char *str) {
    unsigned char h = 0;
    while (*str) h = Rand8[h ^ *str++];
    return h;
}

Здесь Rand8 - таблица из 256 восьмибитовых случайных чисел. Их точный порядок не критичен. Корни этого метода лежат в криптографии; он оказался вполне эффективным.
• Исключающее ИЛИ для строк переменной длины (размер таблицы <= 65536). Если мы хешируем строку дважды, мы получим хеш-значение для таблицы любой длины до 65536. Когда строка хешируется во второй раз, к первому символу прибавляется 1. Получаемые два 8-битовых числа объединяются в одно 16-битовое.

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
}

Реализация

Метод закрытой адресации.

Поэтому закрытые хеш-таблицы особенно эффективны, когда максимальные размеры входящего набора данных уже известены. Было доказано, что, когда закрытая таблица заполняется более чем на 50 процентов, ее эффективность значительно ухудшается (см. Структуры Данных, и Программируйте Проект на C, Робертом Крус, Брюсом Леунг, и Clovis Tondo, Prentice Холл, 1991).

Закрытые таблицы обычно используются для быстродействующего макетирования (они просты для программирования и быстры) и там, где быстрый доступ (нет связаного списока) приоритетен, а память легко доступна.

         val:  array [0..n-1] of T;
         used: array [0..n-1] of boolean;
		 

Пример функции хеширования, используемой в Unix'ах:

/*--- HashPJW	-----------------------------------------------------------*
  (Адаптация PJW) обобщенного алгоритма хеширования Питера Веинбергер,     *
  Основанного на версии Аллена Холуб. Принимает указатель на               *
  элемент данных, который нужно проиндексировать и возвращает unsigned int *
---------------------------------------------------------------------------*/

#include <limits.h>

#define BITS_IN_int     ( sizeof(int) * CHAR_BIT )
#define THREE_QUARTERS  ((int) ((BITS_IN_int * 3) / 4))
#define ONE_EIGHTH      ((int) (BITS_IN_int / 8))
#define HIGH_BITS       ( ~((unsigned int)(~0) >> ONE_EIGHTH ))

unsigned int HashPJW
             ( const char * datum )
{
 unsigned int hash_value, i;

for ( hash_value = 0; *datum; ++datum )
 {
   hash_value = ( hash_value << ONE_EIGHTH ) + *datum;
   if (( i = hash_value & HIGH_BITS ) != 0 )
    hash_value = (hash_value ^ (i >> THREE_QUARTERS)) & ~HIGH_BITS;
 }
 return ( hash_value );
}

Вверх по странице, к оглавлению и навигации.