Миф про O(1)
Говорят, что хэш-таблицы обеспечивают поиск за O(1) — константное время, вне зависимости от размера. В теории они идеальны.
На практике я сталкивался с тем, что производительность хэш-таблиц оказывалась ниже, чем у линейного поиска по массиву.
Я оптимизировал таблицу символов для компилятора. Таблица символов использовала хэш-таблицу с 1024 бакетами, и у нас было примерно 500 символов. Расчёты выглядели отлично: средний размер бакета = 500/1024 ≈ 0,5, поэтому большинство операций поиска должно выполняться за один запрос.
Но профилировщик рассказал иную историю:
$ perf stat -e cache-misses,instructions ./compiler Performance counter stats: 1,234,567 cache-misses 5,000,000 instructions
1,2 миллиона промахов кэша на 5 миллионов команд? Для хэш-таблицы, которая должна быть O(1)?
Проблема заключалась в конфликтах кэша. Хэш-таблица была большой (1024 бакетов × 8 байт = 8 КБ), а паттерн доступа вызывал конфликты линий кэша. Каждая операция поиска была промахом кэша.
Я заменил хэш-таблицу простым линейным поиском по массиву из 500 элементов. В результате выполнение ускорилось в 3 раза.
В этой главе мы разберёмся, когда хэш-таблицы бывают быстрыми, когда медленными, и как сделать их удобными для кэша.
Основы хэш-таблиц
Хэш-таблица сопоставляет ключи со значениями при помощи хэш-функции:
typedef struct { char *key; int value; } entry_t; #define TABLE_SIZE 1024 entry_t *table[TABLE_SIZE]; int hash(const char *key) { unsigned int h = 0; while (*key) { h = h * 31 + *key++; } return h % TABLE_SIZE; } void insert(const char *key, int value) { int index = hash(key); entry_t *entry = malloc(sizeof(entry_t)); entry->key = strdup(key); entry->value = value; table[index] = entry; } int lookup(const char *key) { int index = hash(key); entry_t *entry = table[index]; if (entry && strcmp(entry->key, key) == 0) { return entry->value; } return -1; // Не найдено }
Это хэш-таблица с прямым сопоставлением (одна запись на бакет). Она не обрабатывает коллизии.
Разрешение коллизий
Если два ключа хэшируются в один индекс, возникает коллизия. Существует две основные стратегии:
1. Объединение в цепочку (связанный список для каждого бакета):
typedef struct entry { char *key; int value; struct entry *next; } entry_t; entry_t *table[TABLE_SIZE]; void insert(const char *key, int value) { int index = hash(key); entry_t *entry = malloc(sizeof(entry_t)); entry->key = strdup(key); entry->value = value; entry->next = table[index]; table[index] = entry; } int lookup(const char *key) { int index = hash(key); entry_t *entry = table[index]; while (entry) { if (strcmp(entry->key, key) == 0) { return entry->value; } entry = entry->next; } return -1; // Не найдено }
2. Открытая адресация (зондирование следующего пустого слота):
typedef struct { char *key; int value; int occupied; } entry_t; entry_t table[TABLE_SIZE]; void insert(const char *key, int value) { int index = hash(key); // Линейное зондирование while (table[index].occupied) { index = (index + 1) % TABLE_SIZE; } table[index].key = strdup(key); table[index].value = value; table[index].occupied = 1; } int lookup(const char *key) { int index = hash(key); while (table[index].occupied) { if (strcmp(table[index].key, key) == 0) { return table[index].value; } index = (index + 1) % TABLE_SIZE; } return -1; // Не найдено }
Как сравнение этих решений выглядит в учебниках:
Объединение в цепочку: справляется с любым коэффициентом нагрузки, но требует дополнительной памяти (указатели)
Открытая адресация: дополнительная память не требуется, но деградирует при высоких коэффициентах нагрузки
С точки зрения кэша:
Объединение в цепочку: ужасно (следование по указателям, разбросанные по памяти распределения)
Открытая адресация: лучше (последовательное зондирование, на основе массива)
Проблема конфликтов кэша
Давайте проанализируем поведение кэша при поиске по хэш-таблице.
Объединение в цепочку (наихудший случай):
int lookup(const char *key) { int index = hash(key); // 1. Вычисление хэша entry_t *entry = table[index]; // 2. Загрузка указателя бакета (промах кэша) while (entry) { if (strcmp(entry->key, key) == 0) { // 3. Загрузка элемента (промах кэша) return entry->value; // 4. Загрузка ключа (промах кэша) } entry = entry->next; // 5. Следование по указателю (промах кэша) } return -1; }
Промахи кэша на одну операцию поиска:
Указатель бакета: 1 промах
Каждый элемент в цепочке: 2-3 промаха (элемент, ключ, возможно, следующий элемент)
Итого: 3-10 промахов для цепочки длиной 3
Открытая адресация (линейное зондирование):
int lookup(const char *key) { int index = hash(key); while (table[index].occupied) { // Последовательный доступ if (strcmp(table[index].key, key) == 0) { return table[index].value; } index = (index + 1) % TABLE_SIZE; } return -1; }
Промахи кэша:
Первый запрос: 1 промах (загружает линию кэша с примерно 8 элементами)
Следующие 7 запросов: 0 промахов (та же линия кэша)
Итого: 1-2 промахов для типичной операции поиска
При открытой адресации промахов кэша в 3-5 раз меньше.
Бенчмарк: объединение в цепочку и открытая адресация
Давайте замерим разницу:
// Тест: 1000 вставок, 10000 операций поиска // Коэффициент нагрузки: 0,5 (1000 элементов, 2048 бакетов) Объединение в цепочку: Вставка: 450 000 тактов Поиск: 2 100 000 тактов Промахов кэша: 45 000 Открытая адресация (линейное зондирование): Вставка: 180 000 тактов Поиск: 650 000 тактов Промахи кэша: 12 000
Открытая адресация в 3,2 быстрее и имеет в 3,75 раза меньше промахов кэша.
Качество хэш-функции
Хорошая хэш-функция крайне важна. Плохая хэш-функция вызывает кластеризацию, из-за чего страдает производительность.
Плохая хэш-функция (плохое распределение):
int bad_hash(const char *key) { return key[0] % TABLE_SIZE; // Использует только первый символ! }
Результат: у всех ключей, начинающихся с «a», возникают коллизии, как и у всех ключей, начинающихся с «b», и так далее.
Более качественная хэш-функция (FNV-1a):
uint32_t fnv1a_hash(const char *key) { uint32_t hash = 2166136261u; while (*key) { hash ^= (uint8_t)*key++; hash *= 16777619u; } return hash; }
Ещё более качественная (для integer, идентификационный хэш):
uint32_t int_hash(uint32_t key) { // Для последовательных integer, идеальная идентификация return key; }
Для указателей (умножение на нечётное число):
uint32_t ptr_hash(void *ptr) { uintptr_t p = (uintptr_t)ptr; // Указатели часто выровнены, так что выполняем сдвиг и умножение return (uint32_t)((p >> 3) * 2654435761u); }
Бенчмарк (1000 случайных строк):
Плохой хэш (первый символ): Средняя длина цепочки: 38,5 Простой хэш (сумма): Средняя длина цепочки: 2,1 FNV-1a: Средняя длина цепочки: 0,98
Хорошие хэш-функции снижают количество коллизий в 40 раз.
Коэффициент нагрузки и изменение размера
Коэффициент нагрузки = количество элементов / размер таблицы
Объединение в цепочку: может превышать 1.0, но при этом деградирует производительность
Открытая адресация: должен быть меньше 0.7-0.8, иначе падает производительность
Почему? Когда таблица заполняется, последовательности зондирования становятся дольше:
Коэффициент нагрузки 0,5: среднее количество запросов = 1,5 Коэффициент нагрузки 0,7: среднее количество запросов = 3,6 Коэффициент нагрузки 0,9: среднее количество запросов = 10,5 Коэффициент нагрузки 0,95: среднее количество запросов = 20,5
Решение: увеличение размера, когда коэффициент нагрузки превышает пороговое значение
void resize_table(void) { int old_size = table_size; entry_t *old_table = table; table_size *= 2; table = calloc(table_size, sizeof(entry_t)); // Рехэширование всех элементов for (int i = 0; i < old_size; i++) { if (old_table[i].occupied) { insert(old_table[i].key, old_table[i].value); } } free(old_table); } void insert(const char *key, int value) { if (count >= table_size * 0.7) { resize_table(); } // ... обычная вставка ... }
Затраты: изменение размера за O(n), но амортизированное O(1) при удвоении размера.
Структура хэш-таблицы, удобная для кэша
Вот, как выглядит удобная для кэша структура хэш-таблицы:
1. Использование открытой адресации (линейное зондирование)
2. Плотная упаковка элементов
typedef struct { uint32_t hash; // Сохраняем хэш, чтобы избежать повторного вычисления uint32_t key; // Предполагаем, что используются ключи integer uint32_t value; } entry_t; // 12 байт, в линию кэша умещается 5 элементов
3. Использование размера, равного степени двойки (быстрое деление с остатком)
#define TABLE_SIZE 2048 #define MASK (TABLE_SIZE - 1) int index = hash & MASK; // Быстро!
4. Разделение ключей и значений (если значения большие)
typedef struct { uint32_t keys[TABLE_SIZE]; uint32_t hashes[TABLE_SIZE]; value_t *values[TABLE_SIZE]; // Указатели на большие значения } hash_table_t;
Зачем? Зондирование затрагивает только ключи и хэши, не касаясь больших значений.
5. Использование SIMD для зондирования
// Проверяем по 8 элементов за раз при помощи AVX2 __m256i target = _mm256_set1_epi32(hash); __m256i entries = _mm256_loadu_si256((__m256i*)&table[index]); __m256i cmp = _mm256_cmpeq_epi32(target, entries); int mask = _mm256_movemask_epi8(cmp); if (mask) { int pos = __builtin_ctz(mask) / 4; return table[index + pos].value; }
Хэширование Robin Hood
Хэширование Robin Hood — это вариант линейного зондирования, снижающий разброс длительности зондирования.
Принцип: если при вставке расстояние зондирования уже существующего элемента меньше, чем у вашего, меняем их местами и продолжаем вставлять перемещённый элемент.
Процесс принятия решения:
Пример:
Исходное состояние: ┌─────┬──────────┬──────────┐ │ [0] │ Пусто │ dist: - │ │ [1] │ key1 │ dist: 0 │ (hash=1, идеальная позиция) │ [2] │ key2 │ dist: 1 │ (hash=1, зондирование на 1 шаг) │ [3] │ Пусто │ dist: - │ │ [4] │ Пусто │ dist: - │ └─────┴──────────┴──────────┘ Вставка key3 (hash=2): Пробуем [2]: занято key2 key3 probe_dist = 0 key2 probe_dist = 1 0 ≤ 1 → Продолжаем зондировать Пробуем [3]: Пусто → Вставка После key3: ┌─────┬──────────┬──────────┐ │ [1] │ key1 │ dist: 0 │ │ [2] │ key2 │ dist: 1 │ │ [3] │ key3 │ dist: 1 │ └─────┴──────────┴──────────┘ Вставка key4 (hash=1): Пробуем [1]: занято key1 key4 probe_dist = 0, key1 probe_dist = 0 → Продолжаем Пробуем [2]: занято key2 key4 probe_dist = 1, key2 probe_dist = 1 → Продолжаем Пробуем [3]: занято key3 key4 probe_dist = 2, key3 probe_dist = 1 2 > 1 → ОБМЕН! (Робин Гуд: забираем у богатых, отдаём бедным) После обмена, продолжаем вставлять удалённый ключ key3: Пробуем [4]: Пусто → Вставка key3 Окончательное состояние: ┌─────┬──────────┬──────────┐ │ [1] │ key1 │ dist: 0 │ │ [2] │ key2 │ dist: 1 │ │ [3] │ key4 │ dist: 2 │ ← Вставлено обменом │ [4] │ key3 │ dist: 2 │ ← Удалён, вставлен повторно └─────┴──────────┴──────────┘ Результат: более равномерные расстояния зондирования (max=2 вместо потенциально неограниченного)
void insert(uint32_t key, uint32_t value) { uint32_t hash = hash_func(key); int index = hash & MASK; int probe_dist = 0; entry_t entry = {hash, key, value}; while (1) { if (!table[index].occupied) { table[index] = entry; table[index].occupied = 1; return; } int existing_dist = (index - table[index].hash) & MASK; if (probe_dist > existing_dist) { // Обмен местами: мы зондировали дальше, чем имеющийся элемент entry_t temp = table[index]; table[index] = entry; entry = temp; probe_dist = existing_dist; } index = (index + 1) & MASK; probe_dist++; } }
Преимущества: более равномерные длины зондирования, улучшенная производительность в наихудшем случае.
Бенчмарк:
Линейное зондирование: В среднем: 1,5 проверки, Max: 12 проверок Хэширование Robin Hood: В среднем: 1,5 проверки, Max: 4 проверки
Улучшение для наихудшего случая (важно для систем реального времени).
Маленькие хэш-таблицы: просто используйте массивы
В случае маленьких таблиц (< 100 элементов) линейный поиск по массиву часто оказывается быстрее, чем хэширование.
Почему?
Затраты на вычисление хэшей
Затраты на операции деления с остатком
Потенциальные промахи кэша
Бенчмарк (50 элементов):
Хэш-таблица (открытая адресация): 850 тактов на операцию поиска Линейный поиск (массив): 420 тактов на операцию поиска
Для маленьких таблиц линейный поиск в 2 раза быстрее!
Рекомендация: используйте линейный поиск для < 50-100 элементов, хэш-таблицу для большего количества.
Встраиваемые системы: идеальное хэширование
Во встраиваемых системах все ключи часто бывают известны во время компиляции (например, имена команд, имена регистров). Можно использовать идеальное хэширование — хэш-функцию с нулевыми коллизиями.
Пример: парсер команд с 16 командами
// Команды: "read", "write", "reset", "status", ... // Генерация идеальной хэш-функции во время компиляции const char *commands[] = { "read", "write", "reset", "status", "start", "stop", "config", "debug", // ... всего 16 }; // Идеальная хэш-функция (генерируемая gperf или вручную) int command_hash(const char *cmd) { // Тщательно подобрана так, чтобы обеспечить ноль коллизий return (cmd[0] * 3 + cmd[1] * 7) & 15; } void (*handlers[16])(void) = { [command_hash("read")] = handle_read, [command_hash("write")] = handle_write, // ... }; void dispatch_command(const char *cmd) { int index = command_hash(cmd); if (strcmp(commands[index], cmd) == 0) { handlers[index](); } }
Преимущества:
Ноль коллизий (гарантировано O(1))
Нет зондирования
Минимальная память
Быстрая (один хэш, одно сравнение)
Инструменты: gperf генерирует идеальные хэш-функции из списков ключевых слов.
Пример из реального мира: оптимизация таблицы символов
Вернёмся к моей таблице символов компилятора. Вот, что я поменял:
┌─────────────────────────────────────────────────────────────────┐ │ ДО: Хэш-таблица с объединением в цепочку │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ Хэш-таблица [1024 бакета] │ │ ┌────┐ │ │ │ [0]│ → NULL │ │ │ [1]│ → Symbol("foo") → Symbol("bar") → NULL │ │ │ [2]│ → NULL │ │ │ [3]│ → Symbol("baz") → NULL │ │ │... │ │ │ └────┘ │ │ │ │ Операции поиска: │ │ 1. Вычисление хэша (31 * n) │ │ 2. Операция деления с остатком (затратная) │ │ 3. Следование по указателям (промах кэша) │ │ 4. Сравнение строк (разыменование указателя) │ │ │ │ Производительность: 2400 тактов на операцию поиска │ └─────────────────────────────────────────────────────────────────┘ ┌─────────────────────────────────────────────────────────────────┐ │ ПОСЛЕ: Массив с линейным поиском │ ├─────────────────────────────────────────────────────────────────┤ │ │ │ Массив [макс. 256 символов на диапазон] │ │ ┌──────────────────────────────────────────┐ │ │ │ [0] Symbol { name: "foo", type, offset } │ │ │ │ [1] Symbol { name: "bar", type, offset } │ │ │ │ [2] Symbol { name: "baz", type, offset } │ │ │ │ [3] ... │ │ │ │ (расположены в памяти последовательно) │ │ │ └──────────────────────────────────────────┘ │ │ │ │ Операции поиска: │ │ 1. Последовательное сканирование (удобно для кэша) │ │ 2. Сравнение строк (встроенные данные, без указателя) │ │ │ │ Производительность: 380 тактов на операцию поиска │ │ (в 6,3 раза быстрее!) │ └─────────────────────────────────────────────────────────────────┘ Почему это работает: ✅ Малый диапазон (< 256 символов на функцию) ✅ Последовательный доступ (помогает prefetcher) ✅ Встроенные строки (нет следования по указателям) ✅ Нет оверхеда malloc/free ✅ Удобство для кэша (весь массив умещается в L1)
До (хэш-таблица с объединением в цепочку):
#define TABLE_SIZE 1024 typedef struct symbol { char *name; int type; int offset; struct symbol *next; } symbol_t; symbol_t *symbol_table[TABLE_SIZE]; symbol_t *lookup_symbol(const char *name) { int index = hash(name) % TABLE_SIZE; symbol_t *sym = symbol_table[index]; while (sym) { if (strcmp(sym->name, name) == 0) { return sym; } sym = sym->next; } return NULL; }
После (линейный поиск для малых диапазонов):
#define MAX_SYMBOLS 256 typedef struct { char name[32]; // Встроенный, не указатель int type; int offset; } symbol_t; symbol_t symbols[MAX_SYMBOLS]; int symbol_count = 0; symbol_t *lookup_symbol(const char *name) { // Линейный поиск (удобный для кэша) for (int i = 0; i < symbol_count; i++) { if (strcmp(symbols[i].name, name) == 0) { return &symbols[i]; } } return NULL; }
Изменения:
Удалена хэш-таблица (< 256 символов на диапазон)
Встроены имена (нет следования по указателям)
На основе массива (последовательный доступ)
Нет malloc/free
Результаты:
Ускорение операций поиска в 3 раза
В 10 раз меньше промахов кэша
Более простой код
Предсказуемая производительность
Выводы: при малых датасетах простые решения побеждают умные.
Подведём итог
Миф о O(1) разрушен. Хэш-таблица с 1024 бакетами и 500 символами должна быть быстрой, но 1,2 миллиона промахов кэша на 5 миллионов команд всё испортили. Из-за конфликтов кэша, вызванных таблицей на 8 КБ, каждая операция поиска приводила к промаху кэша. Заменив её линейным поиском по массиву из 500 элементов, мы повысили производительность в 3 раза. Константное время ничего не значит, если каждая операция промахивается мимо кэша.
Главные наблюдения:
Объединение в цепочку: ужасное поведение кэша (следование по указателям)
Открытая адресация: намного лучше (последовательное зондирование)
Важно качество хэш-функции (позволяет избежать кластеризации)
Коэффициент нагрузки влияет на производительность (для открытой адресации он не должен быть < 0,7)
Маленькие таблицы: линейный поиск часто оказывается быстрее
Удобная для кэша архитектура:
Используйте открытую адресацию (линейное зондирование или Robin Hood)
Плотно упаковывайте элементы (12-16 байт на элемент)
Размер, равный степени двойки (быстрое деление с остатком)
Разделение ключей и больших значений
Возможно, стоит использовать SIMD для зондирования
Встраиваемые системы:
Идеальное хэширование для известных ключей
Линейный поиск для малых таблиц (< 100 элементов)
Таблицы фиксированного размера (без изменения размера)
Встроенные ключи (позволяют избежать указателей)
Когда использовать хэш-таблицы:
Большие датасеты (> 100 элементов)
Необходимость O(1) для среднего случая
Хорошее распределение ключей
Допустимо нечастое изменение размеров
Когда НЕ использовать хэш-таблицы:
Маленькие датасеты (< 100 элементов) → используйте массив
Нужно гарантированное O(1) → используйте идеальное хэширование
Нужна отсортированная итерация → используйте дерево
Ограниченный бюджет памяти → используйте массив
Следующая глава: динамические массивы (векторы) сочетают в себе удобство для кэша с гибкостью динамического изменения размера. Мы узнаем, как реализовывать их эффективно, и поймём, когда изменение размера становится узким местом.
