Хеш-таблица

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

Существует два варианта хэш-таблиц: с прямой и открытой адресацией. Хэш-таблица содержит некоторый массив H, элементы которого есть пары (хэш-таблица с открытой адресацией) или списки пар (хэш-таблица с прямой адресацией).

Выполнение операции в хэш-таблице начинается с вычисления хэш-функции от ключа. Получающееся хэш-значение i = hash_function(key) играет роль индекса в массиве H. Затем выполняемая операция (добавление, удаление и поиск) перенаправляется тому объекту, что хранится в соответствующей ячейке массива H[i].

Ситуация, когда для различных ключей получается одно и то же хэш-значение, называется коллизией (collision).

Число хранимых элементов делённое на размер массива H (число возможных значений хэш-функции) называется коэффициентом заполнения хэш-таблицы (load factor) и является важным параметром, от которого зависит среднее время выполнения операций.

[править] Свойства хэш таблицы

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

[править] Разрешение коллизий

Существует несколько способов разрешения колизий.

[править] Прямая адресация

В массиве H хранятся списки пар. Коллизии просто приводят к тому, что появляются списки длиной более одного элемента.

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

[править] Открытая адресация

В массиве H хранятся сами пары. В случае возникновения коллизии, алгоритм поиска (удаления, добавления) объекта просто перемещается на ячейку вправо до момента разрешения коллизии. Разрешение коллизии происходит при достижении пустой ячейки или ячейки, в котором хранится пара с заданным ключом.

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

Ниже представлен простой код её демонстрирующий.

#21f0f1 P 30011
char *dict[P];
char dict_size = 0;
int hash_index[P]; // необходимо инициализировать элементы значением -1
 
/* Функция get_id возвращает индекс слова word в массиве dict.
 * При этом происходит добавление слова word в словарь dict, если его там нет.
 */
int 
get_id(const char *word) {
    unsigned int len = 0, h1 = 0, h2 = 0;
    const char *p = word;
    // Вычислим две хэш-функции от слова word:
    // h1 лежит в [0..P-1], h2 лежит в [1..P-1]
    while ( *(p++) ) {
        h1 *= 17; h1 += 13*(*p); 
        h2 *= 13; h2 += 17*(*p);
        len++;
    }
    h1 %= P;
    h2 %= (P-2); h2 += 1;
 
    while ( hash_index[h1] != -1  ) {
        if ( strcmp (word, dict[ hash_index[h1] ] ) == 0 ) {
            return hash_index[h1];
        } 
        h1 += h2; h1 %= P;
    }
    len++;
    dict[dict_size] = (char*) malloc ( len * sizeof(char) );
    strcpy ( dict[dict_size], word );
    hash_index[h1] = dict_size;
    return dict_size++;
}

[править] См. также

• Ассоциативный массив

[править] Ссылки

• Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2002. — 960 с. — ISBN 5-900916-37-5
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд.. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4

Это незавершённая статья по информатике. Вы можете помочь проекту, исправив и дополнив её.