Структуры данных: Хэш-таблицы и управление конфликтами кэша

Миф про 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;
} entryt;
#define TABLESIZE 1024
entryt table[TABLESIZE];
int hash(const char key) {
    unsigned int h = 0;
    while (key) {
        h = h  31 + key++;
    }
    return h % TABLESIZE;
}
void insert(const char key, int value) {
    int index = hash(key);
    entryt entry = malloc(sizeof(entryt));
    entry->key = strdup(key);
    entry->value = value;
    table[index] = entry;
}
int lookup(const char key) {
    int index = hash(key);
    entryt entry = table[index];
    if (entry && strcmp(entry->key, key) == 0) {
        return entry->value;
    }
    return -1;  // Не найдено
}

Это хэш-таблица с прямым сопоставлением (одна запись на бакет). Она не обрабатывает коллизии.

Разрешение коллизий

Если два ключа хэшируются в один индекс, возникает коллизия. Существует две основные стратегии:

Объединение в цепочку (связанный список для каждого бакета):

typedef struct entry {
    char key;
    int value;
    struct entry next;
} entryt;
entryt table[TABLESIZE];
void insert(const char key, int value) {
    int index = hash(key);
    
    entryt entry = malloc(sizeof(entryt));
    entry->key = strdup(key);
    entry->value = value;
    entry->next = table[index];
    table[index] = entry;
}
int lookup(const char key) {
    int index = hash(key);
    entryt entry = table[index];
    
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
    return -1;  // Не найдено
}

Открытая адресация (зондирование следующего пустого слота):

typedef struct {
    char key;
    int value;
    int occupied;
} entryt;
entryt table[TABLESIZE];
void insert(const char key, int value) {
    int index = hash(key);
    
    // Линейное зондирование
    while (table[index].occupied) {
        index = (index + 1) % TABLESIZE;
    }
    
    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) % TABLESIZE;
    }
    return -1;  // Не найдено
}

Как сравнение этих решений выглядит в учебниках:

• Объединение в цепочку: справляется с любым коэффициентом нагрузки, но требует дополнительной памяти (указатели)
• Открытая адресация: дополнительная память не требуется, но деградирует при высоких коэффициентах нагрузки

С точки зрения кэша:

• Объединение в цепочку: ужасно (следование по указателям, разбросанные по памяти распределения)
• Открытая адресация: лучше (последовательное зондирование, на основе массива)

Проблема конфликтов кэша

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

Объединение в цепочку (наихудший случай):

int lookup(const char key) {
    int index = hash(key);           // 1. Вычисление хэша
    entryt 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 badhash(const char key) {
    return key[0] % TABLESIZE;  // Использует только первый символ!
}

Результат: у всех ключей, начинающихся с «a», возникают коллизии, как и у всех ключей, начинающихся с «b», и так далее.

Более качественная хэш-функция (FNV-1a):

uint32t fnv1ahash(const char key) {
    uint32t hash = 2166136261u;
    while (key) {
        hash ^= (uint8t)key++;
        hash = 16777619u;
    }
    return hash;
}

Ещё более качественная (для integer, идентификационный хэш):

uint32t inthash(uint32t key) {
    // Для последовательных integer, идеальная идентификация
    return key;
}

Для указателей (умножение на нечётное число):

uint32t ptrhash(void ptr) {
    uintptrt p = (uintptrt)ptr;
    // Указатели часто выровнены, так что выполняем сдвиг и умножение
    return (uint32t)((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 resizetable(void) {
    int oldsize = tablesize;
    entryt oldtable = table;
tablesize = 2;
    table = calloc(tablesize, sizeof(entryt));
// Рехэширование всех элементов
    for (int i = 0; i < oldsize; i++) {
        if (oldtable[i].occupied) {
            insert(oldtable[i].key, oldtable[i].value);
        }
    }
free(oldtable);
}
void insert(const char key, int value) {
    if (count >= tablesize * 0.7) {
        resizetable();
    }
// ... обычная вставка ...
}

Затраты: изменение размера за O(n), но амортизированное O(1) при удвоении размера.

Структура хэш-таблицы, удобная для кэша

Вот, как выглядит удобная для кэша структура хэш-таблицы:
1. Использование открытой адресации (линейное зондирование)
2. Плотная упаковка элементов

typedef struct {
    uint32t hash;   // Сохраняем хэш, чтобы избежать повторного вычисления
    uint32t key;    // Предполагаем, что используются ключи integer
    uint32t value;
} entryt;  // 12 байт, в линию кэша умещается 5 элементов

3. Использование размера, равного степени двойки (быстрое деление с остатком)

#define TABLESIZE 2048
#define MASK (TABLESIZE - 1)

int index = hash & MASK;  // Быстро!

4. Разделение ключей и значений (если значения большие)

typedef struct {
    uint32t keys[TABLESIZE];
    uint32t hashes[TABLESIZE];
    valuet values[TABLESIZE];  // Указатели на большие значения
} hashtablet;

Зондирование затрагивает только ключи и хэши, не касаясь больших значений.

5. Использование SIMD для зондирования

// Проверяем по 8 элементов за раз при помощи AVX2
m256i target = mm256set1epi32(hash);
_m256i entries = mm256loadusi256((m256i*)&table[index]);
m256i cmp = mm256cmpeqepi32(target, entries);
int mask = mm256movemaskepi8(cmp);
if (mask) {
    int pos = _builtinctz(mask) / 4;
    return table[index + pos].value;
}

Хэширование Robin Hood

Хэширование Robin Hood — это вариант линейного зондирования, снижающий разброс длительности зондирования.

Принцип

: если при вставке расстояние зондирования уже существующего элемента меньше, чем у вставляемого, меняем их местами и продолжаем вставлять перемещённый элемент.

Пример

Исходное состояние:

┌─────┬──────────┬──────────┐
│ [0] │ Пусто    │ dist: -  │
│ [1] │ key1     │ dist: 0  │
│ [2] │ key2     │ dist: 1  │
│ [3] │ key3     │ dist: 2  │
│ [4] │ Пусто    │ dist: -  │
└─────┴──────────┴──────────┘

Вставка key4:

┌─────┬──────────┬──────────┐
│ [0] │ Пусто    │ dist: -  │
│ [1] │ key1     │ dist: 0  │
│ [2] │ key2     │ dist: 1  │
│ [3] │ key4     │ dist: 2  │ ← Вставлено обменом
│ [4] │ key3     │ dist: 2  │ ← Удалён, вставлен повторно
└─────┴──────────┴──────────┘

Результат: более равномерные расстояния зондирования (max=2 вместо потенциально неограниченного)

void insert(uint32t key, uint32t value) {
    uint32t hash = hashfunc(key);
    int index = hash & MASK;
    int probedist = 0;
entryt entry = {hash, key, value};

while (1) {
    if (!table[index].occupied) {
        table[index] = entry;
        table[index].occupied = 1;
        return;
    }
int existingdist = (index - table[index].hash) & MASK;
    if (probedist > existingdist) {
        // Обмен местами: было решено зондировать дальше, чем имеющийся элемент
        entryt temp = table[index];
        table[index] = entry;
        entry = temp;
        probedist = existingdist;
    }
index = (index + 1) & MASK;
    probedist++;
}

Преимущества

• более равномерные длины зондирования
• улучшенная производительность в наихудшем случае

Бенчмарк

• Линейное зондирование: В среднем: 1,5 проверки, Max: 12 проверок
• Хэширование Robin Hood: В среднем: 1,5 проверки, Max: 4 проверки

Улучшение для наихудшего случая

(важно для систем реального времени).

Маленькие хэш-таблицы: просто используйте массивы

В случае маленьких таблиц (< 100 элементов) линейный поиск по массиву часто оказывается быстрее, чем хэширование.

Почему?

• Затраты на вычисление хэшей
• Затраты на операции деления с остатком
• Потенциальные промахи кэша

Бенчмарк

(50 элементов):

• Хэш-таблица (открытая адресация): 850 тактов на операцию поиска
• Линейный поиск (массив): 420 тактов на операцию поиска

Для маленьких таблиц линейный поиск в 2 раза быстрее.

Рекомендация

: используйте линейный поиск для < 50-100 элементов, хэш-таблицу для большего количества.

Встраиваемые системы: идеальное хэширование

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

Пример

: парсер команд с 16 командами

const char commands[] = {
    "read", "write", "reset", "status",
    "start", "stop", "config", "debug",
    // ... всего 16
};
// Идеальная хэш-функция (генерируемая gperf или вручную)
int commandhash(const char cmd) {
    // Тщательно подобрана так, чтобы обеспечить ноль коллизий
    return (cmd[0]  3 + cmd[1]  7) & 15;
}
void (*handlers[16])(void) = {
    [commandhash("read")] = handleread,
    [commandhash("write")] = handlewrite,
    // ...
};
void dispatchcommand(const char cmd) {
    int index = commandhash(cmd);
    if (strcmp(commands[index], cmd) == 0) {
        handlers[index]();
    }
}

Преимущества

• Ноль коллизий (гарантировано O(1))
• Нет зондирования
• Минимальная память
• Быстрая (один хэш, одно сравнение)

Инструменты

: gperf генерирует идеальные хэш-функции из списков ключевых слов.

Пример из реального мира: оптимизация таблицы символов

Вернёмся к таблице символов компилятора. Вот, что было сделано:

ДО: Хэш-таблица с объединением в цепочку

#define TABLESIZE 1024
typedef struct symbol {
    char name;
    int type;
    int offset;
    struct symbol *next;
} symbolt;
symbolt symboltable[TABLESIZE];

ПОСЛЕ: Массив с линейным поиском

// Массив [макс. 256 символов на диапазон]
// Операции поиска:
// 1. Последовательное сканирование (удобно для кэша)
// 2. Сравнение строк (встроенные данные, без указателя)

Почему это работает:

• Малый диапазон (< 256 символов на функцию)


• Последовательный доступ (помогает prefetcher)


• Встроенные строки (нет следования по указателям)


• Нет оверхеда malloc/free


• Удобство для кэша (весь массив умещается в L1)

c
symbolt lookupSymbol(const char name) {
int index = hash(name) % TABLESIZE;
symbolt sym = symboltable[index];

while (sym) {
if (strcmp(sym->name, name) == 0) {
return sym;
}
sym = sym->next;
}
return NULL;
}

После

(линейный поиск для малых диапазонов):

c
#define MAXSYMBOLS 256

typedef struct {
char name[32]; // Встроенный, не указатель
int type;
int offset;
} symbolt;

symbolt symbols[MAXSYMBOLS];
int symbolcount = 0;

symbolt lookupSymbol(const char name) {
// Линейный поиск (удобный для кэша)
for (int i = 0; i < symbolcount; i++) {
if (strcmp(symbols[i].name, name) == 0) {
return &symbols[i];
}
}
return NULL;
}

Изменения:


была удалена хэш-таблица (< 256 символов на диапазон)

встроены имена (нет следования по указателям)

на основе массива (последовательный доступ)

нет malloc/free


Результаты:

ускорение операций поиска в 3 раза
в 10 раз меньше промахов кэша
более простой код
предсказуемая производительность

Главные наблюдения:

объединение в цепочку: ужасное поведение кэша (следование по указателям)
открытая адресация: намного лучше (последовательное зондирование)
важно качество хэш-функции (позволяет избежать кластеризации)
коэффициент нагрузки влияет на производительность (для открытой адресации он не должен быть < 0,7)
маленькие таблицы: линейный поиск часто оказывается быстрее

Удобная для кэша архитектура:

используйте открытую адресацию (линейное зондирование или Robin Hood)
плотно упаковывайте элементы (12-16 байт на элемент)
размер, равный степени двойки (быстрое деление с остатком)
разделение ключей и больших значений
возможно, стоит использовать SIMD для зондирования

Встраиваемые системы:

идеальное хэширование для известных ключей
линейный поиск для малых таблиц (< 100 элементов)
таблицы фиксированного размера (без изменения размера)
встроенные ключи (позволяют избежать указателей)

Когда использовать хэш-таблицы:

большие датасеты (> 100 элементов)
необходимость O(1) для среднего случая
хорошее распределение ключей
допустимо нечастое изменение размеров

Когда НЕ использовать хэш-таблицы:

маленькие датасеты (< 100 элементов) → используйте массив
нужно гарантированное O(1) → используйте идеальное хэширование
нужна отсортированная итерация → используйте дерево
ограниченный бюджет памяти → используйте массив