Структура данных — Хеш-таблица

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


Хеш-функция и хеш-коллизия

Принцип хеш-таблицы — отображение хеш-функции
key=1 key=2 key=11 → hash(key) = key % 10 →
[0]
[1] 1,11
[2] 2
[3]
[4]
[5]
[6]
[7]
[8]
[9]

Красный слот = коллизия! key=1 и key=11 отображаются в одну и ту же позицию

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

Хорошая хеш-функция должна быстро вычисляться и давать равномерно распределённые результаты.

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


Методы разрешения коллизий

Разрешение хеш-коллизий — метод цепочек против открытой адресации

Метод цепочек

В каждом слоте хранится связный список; ключи, вызвавшие коллизию, добавляются в него.

Преимущества: простая реализация, простое удаление

Недостатки: накладные расходы на указатели, неоптимальное использование кэша

Коэффициент заполнения может превышать 1.0

Открытая адресация

При коллизии зондируется следующий пустой слот

Преимущества: нет указателей, кэш-дружественно

Недостатки: удаление требует ленивой пометки

Коэффициент загрузки должен быть ≤ 0.7

МетодПринципПреимуществаНедостатки
Метод цепочекКаждый слот хранит связанный список; коллизирующие ключи добавляются в связанный списокПростая реализация, лёгкое удаление, коэффициент загрузки может быть больше 1Дополнительные накладные расходы на указатели, неэффективно по кэшу
Открытая адресацияПри коллизии найдите следующий пустой слот в массиве согласно правилам пробированияУказатели не нужны, кэш-дружественноСложное удаление (требуется ленивое удаление), коэффициент загрузки должен контролироваться

При открытой адресации при удалении элемента нельзя просто очистить слот, иначе это нарушит цепочку поиска для последующих элементов. Обычный подход — использовать «ленивое удаление»: помечать позицию как «удалённую», а не «пустую».


Реализация методом цепочек

Пример

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10 /* ёмкость хеш-таблицы */

/* узел хеш-таблицы */
struct HashNode {
    int key;
    int value;
    struct HashNode* next;  /* указатель на следующий узел в том же слоте */
};

/* хеш-функция: простой метод по модулю */
int hashFunc(int key) {
    return key % TABLE_SIZE;
}

/* Вставка пары ключ-значение (цепочки)
Временная сложность: O(1) в среднем, O(n) в худшем случае (все ключи отображаются в один и тот же слот) */

void insert(struct HashNode* table[], int key, int value) {
    int index = hashFunc(key);
    struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = table[index];  /* Вставка в начало */
    table[index] = newNode;
}

/* Поиск: получить значение по ключу
Сначала вычислить хеш-значение, чтобы найти слот, затем пройти по связанному списку, чтобы найти совпадающий ключ */

int search(struct HashNode* table[], int key) {
    int index = hashFunc(key);
    struct HashNode* cur = table[index];
    while (cur != NULL) {
        if (cur->key == key) {
            return cur->value;  /* Найдено */
        }
        cur = cur->next;
    }
    return -1;  /* Не найдено */
}

int main() {
    struct HashNode* table[TABLE_SIZE] = {NULL};  /* Инициализировать все слоты пустыми */

    insert(table, 1, 100);   /* ключ=1, значение=100, индекс=1 */
    insert(table, 2, 200);   /* ключ=2, значение=200, индекс=2 */
    insert(table, 11, 300);  /* ключ=11, значение=300, индекс=1 — коллизия с ключом=1! */

    printf("key=1 → %d\n", search(table, 1));   /* Вывод: 100 */
    printf("key=2 → %d\n", search(table, 2));   /* Вывод: 200 */
    printf("key=11 → %d\n", search(table, 11)); /* Вывод: 300 (метод цепочек корректно обработал коллизию) */
    printf("key=99 → %d\n", search(table, 99)); /* Вывод: -1 (не найдено) */
    return 0;
}

Сценарии применения

СценарийОписание
Словарь/КартаХранение и быстрый поиск пар ключ-значение, например, dict в Python, HashMap в Java
Системы кэшированияВнутренняя реализация систем кэширования, таких как LRU Cache
Индексация баз данныхХеш-индексация обеспечивает поиск за O(1) для запросов на равенство
Таблица символов компилятораХранит сопоставление имён переменных, имён функций и их типов
Другие расширения