Как хранятся объекты в std::unordered_map?

Как хранятся объекты в std::unordered_map?

Архитектура хранения

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

1. Метод цепочек (chaining) — наиболее распространенный
2. Открытая адресация (open addressing) — реже

Метод цепочек (Chaining) — стандартный подход

Human понимание: каждая ячейка хеш-таблицы содержит связный список элементов.

Хеш-таблица (buckets):
┌─────────┐
│Bucket 0 │ → [Key1, Val1] → [Key4, Val4] → nullptr
├─────────┤
│Bucket 1 │ → [Key2, Val2] → nullptr
├─────────┤
│Bucket 2 │ → nullptr
├─────────┤
│Bucket 3 │ → [Key3, Val3] → nullptr
└─────────┘

Процесс хранения:

std::unordered_map<std::string, int> map;
map["apple"] = 5;
map["banana"] = 3;
map["cherry"] = 8;

// Внутренне это выглядит примерно так:
struct Node {
    std::pair<const Key, Value> data;  // пара ключ-значение
    Node* next;  // указатель на следующий элемент в цепочке
};

struct Bucket {
    Node* head;  // начало цепочки
};

std::vector<Bucket> buckets(16);  // по умолчанию ~16 бакетов

Пример: пошаговое добавление элементов

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

// Шаг 1: Добавляем {1, "one"}
map[1] = "one";

// Процесс:
// 1. Вычисляем хеш: hash(1) = 12345
// 2. Вычисляем индекс: 12345 % 16 = 9 (предполагая 16 бакетов)
// 3. Добавляем в цепочку бакета 9:
//    buckets[9] → [1, "one"] → nullptr

// Шаг 2: Добавляем {18, "eighteen"}
map[18] = "eighteen";

// 1. hash(18) = 54321
// 2. Индекс: 54321 % 16 = 9 (коллизия!)
// 3. Добавляем в начало цепочки 9:
//    buckets[9] → [18, "eighteen"] → [1, "one"] → nullptr

Расположение в памяти

Важный момент: элементы std::unordered_map НЕ расположены последовательно в памяти.

std::unordered_map<int, std::string> map;
map[1] = "one";
map[2] = "two";
map[3] = "three";

// Физическое расположение в памяти:
// [Bucket array in heap] 
//     ↓
// [buckets[0]: nullptr]
// [buckets[1]: Node* → Node object → "two" string]
// [buckets[2]: Node* → Node object → "three" string]  
// [buckets[3]: Node* → Node object → "one" string]
// [buckets[4-15]: nullptr]
//
// [Отдельно в heap] 
// [Node1: pair<1, "one">, next=nullptr]
// [Node2: pair<2, "two">, next=nullptr]
// [Node3: pair<3, "three">, next=nullptr]

Доступ к элементам

std::unordered_map<std::string, int> map;
map["apple"] = 5;

// При доступе map["apple"]:
// 1. Вычисляется хеш: hash("apple")
// 2. Вычисляется индекс: hash("apple") % buckets.size()
// 3. Проходим по цепочке: если ключ совпадает, возвращаем значение
// 4. Если не найдено, либо выбрасываем исключение (at), 
//    либо создаем новый элемент (operator[])

Перестроение таблицы (rehashing)

Когда коэффициент нагрузки превышает максимум (обычно 1.0):

// Коэффициент нагрузки = количество элементов / количество бакетов
load_factor = size() / bucket_count();

if (load_factor > max_load_factor()) {
    // Перестроение:
    // 1. Создать новую таблицу большего размера (обычно в 2 раза)
    std::vector<Bucket> new_buckets(buckets.size() * 2);
    
    // 2. Перехешировать все элементы
    for (auto& bucket : buckets) {
        for (auto* node = bucket.head; node; node = node->next) {
            size_t new_index = hash(node->data.first) % new_buckets.size();
            // Добавить в new_buckets[new_index]
        }
    }
    
    // 3. Заменить старую таблицу новой
    buckets = std::move(new_buckets);
}

Пример внутренней структуры

template<typename Key, typename Value>
class UnorderedMap {
private:
    struct Node {
        std::pair<const Key, Value> data;
        Node* next;
    };
    
    std::vector<Node*> buckets;
    size_t element_count = 0;
    float max_lf = 1.0f;
    
public:
    Value& operator[](const Key& key) {
        size_t index = std::hash<Key>()(key) % buckets.size();
        
        // Поиск в цепочке
        for (Node* node = buckets[index]; node; node = node->next) {
            if (node->data.first == key) {
                return node->data.second;
            }
        }
        
        // Не найдено, добавляем новый элемент
        auto* new_node = new Node{{key, Value()}, buckets[index]};
        buckets[index] = new_node;  // вставляем в начало цепочки
        ++element_count;
        
        // Проверяем load_factor
        if (element_count / float(buckets.size()) > max_lf) {
            rehash(buckets.size() * 2);
        }
        
        return buckets[index]->data.second;
    }
};

Итераторы

Итераторы в unordered_map:

std::unordered_map<int, std::string> map;
map[1] = "one";
map[2] = "two";

// Итерирование НЕ в порядке ключей, а в порядке физического расположения
for (auto& [key, value] : map) {
    std::cout << key << ": " << value << "\n";
}
// Вывод может быть: 2: two, 1: one
// (в отличие от std::map, который упорядочен)

// Инвалидация итераторов при rehashing!
auto it = map.begin();
map[1000] = "thousand";  // может вызвать rehashing
// it может быть инвалидирован!

Сравнение с std::map

Практический пример

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> map;
    
    std::cout << "Initial bucket_count: " << map.bucket_count() << "\n";
    
    // Добавляем элементы
    for (int i = 0; i < 20; ++i) {
        map["key" + std::to_string(i)] = i;
        if (i == 10) {
            std::cout << "After 11 elements, bucket_count: " 
                      << map.bucket_count() 
                      << ", load_factor: " 
                      << map.load_factor() << "\n";
        }
    }
    
    std::cout << "Final bucket_count: " << map.bucket_count() << "\n";
    std::cout << "Final load_factor: " << map.load_factor() << "\n";
    
    // Проверка распределения
    std::cout << "\nБакеты с элементами:\n";
    for (size_t i = 0; i < map.bucket_count(); ++i) {
        std::cout << "Bucket " << i << ": " << map.bucket_size(i) << " элементов\n";
    }
    
    return 0;
}

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

1. Используй unordered_map когда: нужен быстрый поиск, порядок не важен
2. Используй map когда: нужен упорядоченный доступ, нужны диапазоны
3. Остерегайся rehashing: может инвалидировать итераторы
4. Выбор хеш-функции критичен: плохая функция приводит к коллизиям
5. Load factor имеет значение: слишком высокий — много коллизий

Заключение

std::unordered_map хранит элементы в виде хеш-таблицы с методом цепочек. Каждый элемент — это узел в динамически выделенной памяти, связанный со своей цепочкой в соответствующем бакете. Это обеспечивает среднюю сложность O(1) для поиска, но требует аккуратного обращения с итераторами при перестроении таблицы.