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

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

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

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

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

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

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

Термины

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

---

Идея

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

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

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

---

Структура на цепочках (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;

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

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

---

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

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

• линейное: (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;

Удаление помечают как 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) */

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

---

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 для строковых ключей:

1. h = hash_string(key)
2. index = h % map->capacity
3. пройти список map->buckets[index]; если ключ уже есть — обновить value
4. иначе создать Entry, скопировать ключ (strdup), вставить в голову списка, map->count++
5. если 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++;

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

---