Какая структура данных у Bucket в std::unordered_map?

В типичной реализации std::unordered_map (хеш-таблица) бакет (bucket) представляет собой односвязный список (forward list) элементов, чьи ключи имеют одинаковый хеш (коллизия).

Структура (упрощенно):

// Упрощенное представление узла в списке бакета
struct HashNode {
    std::pair<const Key, Value> data; // Хранимая пара ключ-значение
    HashNode* next;                   // Указатель на следующий узел в цепочке
    // ... возможно, хранится и кэшированный хеш ключа
};

// Сама хеш-таблица содержит массив (вектор) указателей на такие списки
std::vector<HashNode*> buckets; // Индекс в векторе = номер бакета

Как это работает:

1. Хеш-функция преобразует ключ в число.
2. Это число отображается на индекс в массиве buckets (например, index = hash % bucket_count()).
3. Элемент добавляется в начало односвязного списка, на который указывает buckets[index].

Практические следствия для C++ разработчика:

• Вставка (insert, emplace): В среднем O(1), но в худшем случае (все элементы попали в один бакет) — O(n).
• Поиск (find): Средняя сложность O(1), худшая — O(n) по той же причине.
• Рехеширование: При превышении max_load_factor() (отношение size() к bucket_count()) таблица увеличивается, создается новый массив бакетов большего размера, и все элементы перераспределяются. Это дорогая операция O(n).
• Локализация данных: Плохая, так как узлы списка могут быть разбросаны по памяти.

Пример наблюдения за бакетами:

#include <unordered_map>
#include <iostream>

std::unordered_map<std::string, int> map;
// ... заполнение map

std::cout << "Количество бакетов: " << map.bucket_count() << 'n';
std::cout << "Коэффициент загрузки: " << map.load_factor() << 'n';

// Просмотр цепочки в конкретном бакете
for (size_t i = 0; i < map.bucket_count(); ++i) {
    std::cout << "Бакет #" << i << " содержит " << map.bucket_size(i) << " элементов.n";
}