Какая сложность работы с unordered_map?

Асимптотическая сложность работы с std::unordered_map

Кратко

• Average case (средний случай): O(1) поиск, вставка, удаление
• Worst case (худший случай): O(n) при плохом распределении хешей

Детально: Как работает unordered_map

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

ключ → хеш-функция → индекс → значение

Таблица сложностей

Почему O(1) в среднем

Идеальный случай:

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

// Вставляем
map["apple"] = 5;   // hash("apple") → индекс 0 → вставляем
map["banana"] = 3;  // hash("banana") → индекс 5 → вставляем
map["cherry"] = 7;  // hash("cherry") → индекс 2 → вставляем

// Поиск
auto it = map.find("banana");  // hash("banana") → индекс 5 → O(1)

Если каждый ключ попадает в разный бакет — поиск происходит за один доступ к памяти.

Почему O(n) в худшем случае: Коллизии

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

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

// Худший случай: все ключи имеют один и тот же хеш
map[1] = "one";    // hash(1) → индекс 0, бакет = [1]
map[2] = "two";    // hash(2) → индекс 0 (коллизия!), бакет = [1, 2]
map[3] = "three";  // hash(3) → индекс 0 (коллизия!), бакет = [1, 2, 3]
map[4] = "four";   // hash(4) → индекс 0 (коллизия!), бакет = [1, 2, 3, 4]

// Поиск
auto it = map.find(4);  // Нужно проверить все элементы в бакете → O(n)

Реальный пример плохого случая

#include <unordered_map>
#include <iostream>
#include <chrono>

// Хеш-функция, которая всегда возвращает одно число
struct BadHash {
    size_t operator()(int x) const {
        return 0;  // ❌ Все ключи в одном бакете!
    }
};

int main() {
    std::unordered_map<int, int, BadHash> bad_map;
    
    // Вставляем 100000 элементов
    for (int i = 0; i < 100000; ++i) {
        bad_map[i] = i * 2;
    }
    
    // Поиск в худшем случае: O(n)
    auto start = std::chrono::high_resolution_clock::now();
    auto it = bad_map.find(99999);
    auto end = std::chrono::high_resolution_clock::now();
    
    std::cout << "Time: " << 
        std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() 
        << " μs\n";  // ~10000 μs (ОЧЕНЬ МЕДЛЕННО!)
    
    return 0;
}

Нормальный случай: хорошее распределение

#include <unordered_map>
#include <iostream>
#include <chrono>

int main() {
    std::unordered_map<int, int> good_map;
    
    for (int i = 0; i < 100000; ++i) {
        good_map[i] = i * 2;
    }
    
    // Поиск в среднем: O(1)
    auto start = std::chrono::high_resolution_clock::now();
    auto it = good_map.find(99999);
    auto end = std::chrono::high_resolution_clock::now();
    
    std::cout << "Time: " << 
        std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() 
        << " ns\n";  // ~100 ns (БЫСТРО!)
    
    return 0;
}

Load Factor и Rehashing

std::unordered_map автоматически расширяется при заполнении:

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

// При добавлении элементов
for (int i = 0; i < 1000000; ++i) {
    map["key" + std::to_string(i)] = i;
    
    // Когда load_factor() > max_load_factor() (по умолчанию 1.0)
    // происходит rehashing: создаётся новая таблица большего размера
    // Стоимость rehash: O(n) — нужно переиндексировать все элементы
    
    if (i % 10000 == 0) {
        std::cout << "Load factor: " << map.load_factor() << std::endl;
    }
}

Контроль rehashing

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

// Резервируем место для 1 миллиона элементов
map.reserve(1000000);  // Избегаем rehashing во время вставки

// Теперь вставки точно O(1) amortized
for (int i = 0; i < 1000000; ++i) {
    map["key" + std::to_string(i)] = i;
}

// Инфо о бакетах
std::cout << "Bucket count: " << map.bucket_count() << std::endl;
std::cout << "Max load factor: " << map.max_load_factor() << std::endl;
std::cout << "Current load factor: " << map.load_factor() << std::endl;

Сравнение: unordered_map vs map

Когда использовать какую:

// Быстрый поиск, порядок не важен → unordered_map
std::unordered_map<int, std::string> lookup;

// Нужен отсортированный порядок → map
std::map<int, std::string> sorted_data;

// Частые итерации и нужен порядок → map
for (const auto& [key, value] : sorted_data) {
    // Итерирует в порядке сортировки ключей
}

Как избежать худшего случая

1. Используй хорошую хеш-функцию

// Встроенная std::hash оптимизирована
std::unordered_map<std::string, int> map;  // ✅ Хороший выбор

2. Не полагайся на хеши для security

// ❌ Если противник может выбирать ключи, он вызовет O(n) поведение
// Это DoS атака (Algorithmic Complexity Attack)

3. Для требовательных к latency систем используй std::map

// map гарантирует O(log n) — более предсказуемо
// unordered_map может иметь отклонения

4. Измеряй load factor

if (map.load_factor() > 0.5) {
    // Много коллизий, рассмотри reserve или переход на map
}

Итоговые выводы

• unordered_map в среднем O(1) — самый быстрый для поиска
• Худший случай O(n) — при плохом распределении хешей
• Amortized O(1) — с учётом rehashing
• Используй .reserve() перед вставкой большого числа элементов
• Для критичных по latency систем → std::map (O(log n) гарантирован)
• std::hash обычно хороша — встроенная хеш-функция проверена
• DoS risk — если противник выбирает ключи, он может вызвать O(n)