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

Структура данных Bucket в std::unordered_map

std::unordered_map использует хеш-таблицу с разрешением коллизий через chaining (цепочка). Понимание структуры bucket'ов критично для оптимизации производительности.

Общая архитектура

Концепция хеш-таблицы

std::unordered_map состоит из:

1. Массива bucket'ов (хеш-таблицы)
2. Цепочек элементов в каждом bucket'е (для разрешения коллизий)

Хеш-таблица (массив bucket'ов):

[0] -> [key1, val1] -> [key2, val2] -> [key3, val3]
[1] -> nullptr (пусто)
[2] -> [key4, val4]
[3] -> nullptr
...
[N-1] -> [key5, val5] -> [key6, val6]

Структура одного Bucket'а

В реализации libstdc++

Каждый bucket обычно содержит:

template<typename Value>
struct hash_node {
    Value value;              // std::pair<const Key, Value>
    hash_node* next;         // указатель на следующий узел в цепочке
};

// Массив bucket'ов
std::vector<hash_node*> buckets;

Визуальное представление

Bucket[0]:  nullptr
Bucket[1]:  ┌──────────────────┐
            │ key:5, val:"Bob" │
            │ next ──┐         │
            └────────┼─────────┘
                     |
                     v
                 ┌──────────────────┐
                 │key:15, val:"Tom"│
                 │ next ──> nullptr │
                 └──────────────────┘

Bucket[2]:  ┌──────────────────┐
            │key:3, val:"Ann" │
            │ next ──> nullptr │
            └──────────────────┘

Bucket[3]:  nullptr

Как работает вставка

std::unordered_map<int, std::string> map;

// Вставляем {3, "Alice"}
int key = 3;
std::string value = "Alice";

// Шаг 1: вычислить хеш
size_t hash = std::hash<int>()(key);  // hash = 12345

// Шаг 2: получить индекс bucket'а
size_t bucket_index = hash % num_buckets;  // 12345 % 8 = 5

// Шаг 3: вставить узел в начало цепочки bucket'а[5]
node* new_node = new hash_node{key, value, nullptr};
new_node->next = buckets[5];
buckets[5] = new_node;

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

Коллизия: Когда два разных ключа дают одинаковый хеш.

std::unordered_map<int, std::string> map;

map[5] = "Bob";     // hash(5) = 101, bucket[101 % 8] = 5
map[13] = "Alice";  // hash(13) = 109, bucket[109 % 8] = 5 (коллизия!)
map[21] = "Tom";    // hash(21) = 117, bucket[117 % 8] = 5 (коллизия!)

// Один bucket содержит цепочку:
Bucket[5]: [21, "Tom"] -> [13, "Alice"] -> [5, "Bob"] -> nullptr

Поиск при коллизии

// Поиск ключа 13 в bucket[5]
auto it = map.find(13);

// Процесс:
// 1. hash(13) = 109
// 2. bucket_index = 109 % 8 = 5
// 3. Начинаем с buckets[5]
// 4. Сравниваем 13 с 21 - не равно
// 5. Идём к следующему узлу
// 6. Сравниваем 13 с 13 - найдено!

Load Factor и Rehashing

Load Factor = size / num_buckets

Это средняя длина цепочки в bucket'е. При превышении порога (обычно 1.0) выполняется rehashing.

std::unordered_map<int, int> map;

// Начальное: num_buckets = 16, size = 0, load_factor = 0
for (int i = 0; i < 20; i++) {
    map[i] = i * 2;
    // load_factor растёт: 0, 1/16, 2/16, ..., 20/16 = 1.25
    // При load_factor > 1.0 выполняется rehash
}

// После rehash: num_buckets = 32 (удвоилось)
// Все элементы переместились в новые bucket'ы

Процесс Rehashing

// Когда load_factor > max_load_factor():

// 1. Создаём новую таблицу большего размера
size_t new_bucket_count = num_buckets * 2;
std::vector<hash_node*> new_buckets(new_bucket_count, nullptr);

// 2. Переходим все элементы
for (size_t i = 0; i < old_buckets.size(); i++) {
    hash_node* node = old_buckets[i];
    while (node) {
        // Пересчитаем bucket index для новой таблицы
        size_t new_index = hash(node->key) % new_bucket_count;
        // Вставляем в новый bucket
        node->next = new_buckets[new_index];
        new_buckets[new_index] = node;
        node = node->next;
    }
}

// 3. Заменяем старую таблицу
buckets = new_buckets;

Время операций в зависимости от load_factor

Средний случай: O(1 + load_factor)

load_factor = 0.5:  O(1.5)  - быстро
load_factor = 1.0:  O(2.0)  - нормально
load_factor = 2.0:  O(3.0)  - медленно
load_factor = 10.0: O(11.0) - очень медленно

Худший случай: O(n)

Все элементы в одном bucket'е (из-за плохой хеш-функции):

struct BadHash {
    size_t operator()(int x) const {
        return 42;  // Все хеши одинаковые!
    }
};

std::unordered_map<int, int, BadHash> bad_map;
// Все элементы попадут в один bucket
// find(), insert(), erase() станут O(n)

Реальная структура в памяти

libstdc++ (более эффективная версия)

class hash_table {
private:
    std::vector<hash_node*> buckets;  // Массив указателей
    size_t element_count;             // Количество элементов
    float max_load_factor;            // Порог для rehash
    
public:
    // bucket_count(): возвращает num_buckets
    size_t bucket_count() const { return buckets.size(); }
    
    // size(): возвращает element_count
    size_t size() const { return element_count; }
    
    // load_factor(): size() / bucket_count()
    float load_factor() const { 
        return static_cast<float>(element_count) / buckets.size();
    }
};

Управление bucket'ами

std::unordered_map<int, int> map = {{1,10}, {2,20}, {3,30}};

// Получить информацию о bucket'ах
std::cout << map.bucket_count();      // Количество bucket'ов
std::cout << map.load_factor();       // load_factor
std::cout << map.max_load_factor();   // Порог для rehash (обычно 1.0)

// Узнать, в каком bucket'е находится элемент
auto hash_fn = map.hash_function();
size_t hash_value = hash_fn(1);
size_t bucket_idx = hash_value % map.bucket_count();
std::cout << "Key 1 in bucket " << bucket_idx;

// Управление нагрузкой
map.reserve(100);              // Зарезервировать место
map.max_load_factor(0.5);      // Уменьшить порог (чаще rehash)
map.rehash(200);               // Явно rehash с новым размером

Оптимизации

1. Reserve память заранее

std::unordered_map<int, int> map;
map.reserve(1000);  // Выделить место для ~1000 элементов

for (int i = 0; i < 1000; i++) {
    map[i] = i;  // Без rehashing
}

2. Хорошая хеш-функция

// Плохая: много коллизий
struct BadHash {
    size_t operator()(const std::string& s) const {
        return s[0];  // Только первый символ
    }
};

// Хорошая: использовать встроенную
std::unordered_map<std::string, int> map;  // Использует std::hash

3. Понимать trade-off'ы

• Низкий load_factor (много памяти, быстро) vs высокий (мало памяти, медленно)
• std::map (O(log n), предсказуемо) vs std::unordered_map (O(1) avg, но O(n) worst)