Какой контейнер лежит в основе unordered_map?

Внутреннее устройство unordered_map

Основной контейнер - хеш-таблица

В основе std::unordered_map лежит хеш-таблица (hash table), состоящая из массива бакетов (buckets), каждый из которых содержит цепочку элементов (linked list). Это техника называется separate chaining или open hashing.

Архитектура хеш-таблицы

struct Bucket {
    std::list<std::pair<Key, Value>> chain;  // Цепочка коллизий
};

class HashTable {
private:
    std::vector<Bucket> buckets;
    size_t bucket_count;
    std::hash<Key> hasher;
    std::equal_to<Key> equal;
};

Как работает поиск элемента

1. Вычисление хеша: hash_value = hasher(key)
2. Вычисление индекса бакета: bucket_index = hash_value % bucket_count
3. Поиск в цепочке: перебор всех элементов в связном списке бакета
4. Сравнение ключей: использование функции равенства equal

// Пример поиска
iterator find(const Key& key) const {
    size_t hash_value = hasher(key);
    size_t bucket_idx = hash_value % buckets.size();
    
    for (auto& pair : buckets[bucket_idx].chain) {
        if (equal(pair.first, key)) {
            return iterator_to(pair);
        }
    }
    return end();
}

Коллизии и их разрешение

Когда два разных ключа имеют одинаковый хеш-код, возникает коллизия. Метод separate chaining разрешает это, храня несколько элементов в одной цепочке связного списка:

// Два ключа с одинаковым хешем в одном бакете
map["key1"] = value1;  // hash % buckets.size() = 5
map["key2"] = value2;  // hash % buckets.size() = 5 (коллизия!)

// Оба хранятся в buckets[5] как связный список
buckets[5].chain: [key1 -> value1] -> [key2 -> value2]

Операции вставки и удаления

Вставка:

1. Вычисляется хеш и индекс бакета
2. Проверяется, нет ли уже такого ключа в цепочке
3. Если нет - добавляется новая пара в конец списка
4. При необходимости выполняется rehashing (переxеширование)

Удаление:

1. Находится нужный элемент в цепочке
2. Удаляется из связного списка

Коэффициент заполнения (load factor)

Ооочень важный параметр - отношение количества элементов к количеству бакетов:

load_factor = size() / bucket_count()

// Стандартная реализация обычно:
// - max_load_factor() = 1.0 (не более одного элемента на бакет в среднем)
// - При превышении выполняется rehashing

При увеличении load_factor сверх max_load_factor выполняется rehashing - перестройка всей таблицы с большим числом бакетов:

void rehash(size_t new_bucket_count) {
    std::vector<Bucket> new_buckets(new_bucket_count);
    
    // Переместить все элементы в новую таблицу
    for (auto& old_bucket : buckets) {
        for (auto& pair : old_bucket.chain) {
            size_t new_idx = hasher(pair.first) % new_bucket_count;
            new_buckets[new_idx].chain.push_back(pair);
        }
    }
    
    buckets = std::move(new_buckets);
}

Временная сложность

Худший случай наступает при плохом хеш-функции, когда все элементы попадают в одну цепочку.

Преимущества и недостатки

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

• Средняя временная сложность O(1) для основных операций
• Хорошая cache locality при правильном выборе bucket_count
• Простая реализация

Недостатки:

• Худший случай O(n)
• Требует хорошей хеш-функции
• Дополнительная память на управление связными списками
• Коллизии снижают производительность

Практические рекомендации

• Использовать собственную хеш-функцию для сложных типов данных
• Мониторить load_factor в performance-критичном коде
• Для малых объемов данных map может быть быстрее из-за cache-friendliness
• Вызывать reserve() если известен примерный размер заранее