Хеш-таблица на С

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Архитектору

Хеш-таблица на С

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

В Python пишут d["name"] = "Alice". На С ту же идею реализуют структурами, указателями и malloc — это упражнение для понимания структур и памяти.

Теория в общем виде — в разделе структуры данных.

Термины

Термин	Объяснение
Ключ	по чему ищем (`"user_id"`, число, указатель)
Значение	что храним (число, структура, указатель на объект)
Хеш	целое число, вычисленное из ключа
Корзина (bucket)	ячейка массива, куда попадают ключи с одним индексом
Коллизия	два разных ключа дали один индекс
Load factor	`count / capacity` — насколько таблица заполнена

Идея

Есть массив корзин (buckets) фиксированной длины capacity.
Хеш-функция превращает ключ в целое hash и выбирает индекс: index = hash % capacity.
При коллизии (два ключа попали в одну корзину) применяют стратегию разрешения.

Качество хеш-функции влияет на равномерность заполнения. Для строк часто используют алгоритмы вроде FNV-1a или djb2; для целых ключей — смешивание битов (xor-shift), чтобы похожие числа не садились в соседние ячейки.

Индекс корзины из хеша:

unsigned h = hash_string(key);
size_t index = h % map->capacity;   /* или: h & (map->capacity - 1) для степени двойки */

Разбор:

Сначала ключ превращается в число h, затем выбирается корзина в диапазоне 0 .. capacity-1.
Оператор % универсален, но медленнее на некоторых CPU; маска & (capacity - 1) работает только если capacity — степень двойки.
Одинаковый index у разных ключей означает коллизию, которую дальше разрешают цепочкой или пробированием.

unsigned hash_string(const char *s)
{
    unsigned h = 2166136261u;
    while (*s) {
        h ^= (unsigned char)*s++;
        h *= 16777619u;
    }
    return h;
}

Разбор:

Функция hash_string вычисляет детерминированный unsigned-хеш для строкового ключа, чтобы затем получить индекс корзины.
while (*s) идёт по строке до нулевого терминатора \0, обрабатывая каждый символ последовательно.
Операция h ^= (unsigned char)*s++ смешивает текущий байт в состояние хеша и одновременно сдвигает указатель.
Умножение на 16777619u усиливает распределение значений, уменьшая вероятность длинных цепочек коллизий.

Структура на цепочках (chaining)

Каждая корзина — голова связного списка узлов. Вставка: создать узел, вставить в начало списка buckets[index].

typedef struct Entry {
    char *key;
    int value;
    struct Entry *next;
} Entry;

typedef struct HashMap {
    Entry **buckets;
    size_t capacity;
    size_t count;
} HashMap;

Разбор:

Entry хранит пару key/value и указатель next, то есть один узел цепочки в корзине.
Поле Entry **buckets в HashMap — массив указателей на головы списков; индекс вычисляется через хеш.
capacity задаёт размер таблицы, а count хранит текущее число элементов для оценки load factor.
Такое разделение позволяет быстро находить корзину и локально обходить только нужную цепочку.

Плюсы: простая вставка и удаление, таблица может быть заполнена сильнее 100% (при длинных цепочках падает производительность). Минусы: дополнительные указатели и аллокации на каждый узел.

Поиск: пройти список в корзине, сравнить ключи (strcmp для строк).

bool hashmap_get(const HashMap *map, const char *key, int *out_value)
{
    unsigned h = hash_string(key);
    size_t index = h % map->capacity;

    for (Entry *e = map->buckets[index]; e != NULL; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            *out_value = e->value;
            return true;
        }
    }
    return false;
}

Разбор:

Функция вычисляет тот же индекс, что и при вставке, поэтому ищет в правильной корзине.
Цикл for проходит связный список узлов в этой корзине.
strcmp(e->key, key) == 0 сравнивает строковые ключи посимвольно.
false означает "ключ не найден"; вызывающий код не должен читать *out_value в этом случае.

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

Все элементы лежат в самом массиве слотов без списков. При занятой ячейке ищут следующую по пробированию:

линейное: (index + 1) % capacity;
квадратичное: (index + i*i) % capacity;
двойное хеширование: шаг зависит от второго хеша ключа.

typedef enum { SLOT_EMPTY, SLOT_OCCUPIED, SLOT_DELETED } SlotState;

typedef struct {
    SlotState state;
    char *key;
    int value;
} Slot;

Разбор:

SlotState кодирует жизненный цикл ячейки — пусто, занято, удалено; это нужно для корректного пробирования.
Состояние SLOT_DELETED сохраняет непрерывность цепочки поиска после удаления элемента.
В структуре Slot ключ и значение лежат прямо в массиве слотов, без дополнительных списков и указателей next.
Такой формат повышает кэш-локальность, но требует аккуратной стратегии очистки "мёртвых" записей.

Удаление помечают как DELETED, иначе обрывается цепочка проб. Много "мёртвых" слотов ухудшает поиск — периодически нужна перестройка.

Плюсы: компактность, кэш-локальность. Минусы: при заполнении > ~0.7 растёт число проб; resize обязателен раньше, чем при цепочках.

Выбор размера и перехеширование

capacity часто берут простым числом или степенью двойки. Для степени двойки индекс — hash & (capacity - 1) — быстрее, чем %, но хуже, если низкие биты хеша коррелированы с ключами.

При росте count таблицу расширяют (обычно в 2 раза), заново вставляют все пары — rehash. Старые индексы меняются, потому что меняется модуль/маска.

bool hashmap_insert(HashMap *map, const char *key, int value);
/* при load_factor > 0.75 вызвать hashmap_grow(map) */

Разбор:

Сигнатура показывает привычный контракт — bool сообщает успех операции, а параметры передают карту, ключ и значение.
Порог load_factor > 0.75 служит эвристикой для расширения таблицы до резкого ухудшения времени поиска.
Вызов hashmap_grow(map) обычно создаёт более ёмкий массив корзин и перехеширует все существующие элементы.

load_factor = count / capacity — эвристика для вызова grow.

Схема grow в двух шагах:

Код ITЗагрузка примера кода…

Разбор:

Создаётся новая таблица с удвоенной ёмкостью, старая остаётся источником данных до завершения переноса.
Двойной цикл обходит все корзины и все узлы цепочек.
Каждый элемент вставляется в новую таблицу заново, потому что индекс зависит от capacity.
После переноса старая память освобождается, а *map получает новое состояние.

API минимального уровня

Операция	Поведение
`create(capacity)`	выделить `buckets`, инициализировать
`get(key)`	найти значение или "нет"
`set(key, value)`	вставить или обновить
`remove(key)`	удалить, освободить копию ключа при необходимости
`destroy`	обойти все узлы/слоты, `free` ключей и массива

Ключи-строки обычно копируют при вставке (strdup или свой дубликатор), чтобы вызывающий мог освободить исходный буфер.

Коллизии и безопасность

Хеш-таблица не защищает от злонамеренных ключей, подобранных под одну корзину (hash flooding). В сетевых сервисах иногда переходят на деревья в корзине или случайный seed хеша на процесс.

Для встраиваемых систем с фиксированным набором ключей иногда используют perfect hashing — отдельная тема; для общего случая достаточно chaining + resize.

Когда что выбирать

Сценарий	Подход
Неизвестное число ключей, частые удаления	цепочки
Мало памяти, предсказуемый размер	открытая адресация
Ключи — `int`/`uint64_t`	хеш = сам ключ после mixing
Многопоточность	отдельные таблицы на поток, или блокировка корзин

Готовые реализации встречаются в проектах (uthash, khash, таблицы в компиляторах); для обучения полезно один раз написать свою версию на 100–150 строк.

Пошаговый пример — вставка с цепочками

Псевдокод set для строковых ключей:

h = hash_string(key)
index = h % map->capacity
пройти список map->buckets[index]; если ключ уже есть — обновить value
иначе создать Entry, скопировать ключ (strdup), вставить в голову списка, map->count++
если count / capacity > 0.75 — вызвать grow: новый массив в 2 раза больше, все элементы вставить заново (rehash)

Поиск get: те же шаги 1–2, затем strcmp по списку.

Удаление — найти узел, вытащить из списка, free(key), free(node), уменьшить count.

Ошибки, которые стоит обрабатывать: malloc вернул NULL; дубликат ключа (политика: обновить или вернуть ошибку); destroy обходит все корзины и освобождает узлы.

/* упрощённый фрагмент вставки в голову списка */
Entry *e = malloc(sizeof *e);
if (!e) return false;
e->key = strdup(key);
if (!e->key) { free(e); return false; }
e->value = value;
e->next = map->buckets[index];
map->buckets[index] = e;
map->count++;

Разбор:

malloc(sizeof *e) выделяет память под новый узел; проверка if (!e) сразу обрабатывает нехватку памяти.
strdup(key) создаёт независимую копию ключа, поэтому исходную строку можно безопасно освободить у вызывающего кода.
e->next = map->buckets[index] и последующее присваивание в buckets[index] вставляют узел в начало цепочки за O(1).
map->count++ поддерживает корректную статистику заполнения для дальнейших решений о rehash.

См. также — Структуры и объединения, SQLite из С, Идиомы ошибок.

Хеш-таблица на С