Какая сложность вставки в std::unordered_map?

Какая сложность вставки в std::unordered_map?

Краткий ответ

Сложность вставки в std::unordered_map:

• Средний случай (average case): O(1) — аморфизированная константная сложность
• Худший случай (worst case): O(n) — когда все элементы хешируются в один бакет (коллизии)

Как работает unordered_map

std::unordered_map использует hash table (таблица хеширования):

// Внутренняя структура (упрощённо)
std::vector<std::vector<std::pair<Key, Value>>> buckets;

Процесс вставки:

1. Вычисляется хеш ключа: hash_value = hash_function(key)
2. Определяется индекс бакета: bucket_index = hash_value % buckets.size()
3. Вставляется пара (key, value) в соответствующий бакет

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> map;
    
    // Вставка в среднем O(1)
    map["alice"] = 25;
    map["bob"] = 30;
    map["charlie"] = 35;
    
    std::cout << "Size: " << map.size() << "\n";
    std::cout << "Buckets: " << map.bucket_count() << "\n";
    std::cout << "Load factor: " << map.load_factor() << "\n";
    
    return 0;
}

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

Когда хеш-функция хорошая и нет коллизий:

Вставка "alice"
hash("alice") = 12345
bucket_index = 12345 % 8 = 1
buckets[1] → [("alice", 25)]  ← O(1) операция

Вставка "bob"
hash("bob") = 54321
bucket_index = 54321 % 8 = 1
buckets[1] → [("alice", 25), ("bob", 30)]  ← O(1) к концу вектора

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

Плохая хеш-функция создаёт все коллизии:

// Плохая хеш-функция
struct BadHash {
    size_t operator()(const std::string& s) const {
        return 0;  // Всегда возвращает 0!
    }
};

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

// Все вставки идут в один бакет!
map["a"] = 1;    // O(1)
map["b"] = 2;    // O(1) 
map["c"] = 3;    // O(1)
...
map["z"] = 26;   // O(26) = O(n)!

// Поиск элемента: O(n) в худшем случае
auto it = map.find("z");  // Нужно искать в списке из 26 элементов

Переаллокация и load factor

std::unordered_map<int, int> map;

std::cout << "Initial buckets: " << map.bucket_count() << "\n";
std::cout << "Max load factor: " << map.max_load_factor() << "\n";

for (int i = 0; i < 100; i++) {
    int old_buckets = map.bucket_count();
    map[i] = i;
    
    if (map.bucket_count() > old_buckets) {
        std::cout << "Rehash! New bucket count: " << map.bucket_count() << "\n";
    }
}

// Вывод (примерно):
// Initial buckets: 0
// Rehash! New bucket count: 1
// Rehash! New bucket count: 2
// Rehash! New bucket count: 4
// Rehash! New bucket count: 8
// ... и так далее

Rehash происходит, когда load_factor превысит max_load_factor (обычно 1.0)

// Load factor = количество элементов / количество бакетов
// Когда load_factor > 1.0, происходит rehash на 2x больше бакетов

Стоимость rehash: O(n) — нужно пересчитать хеш для каждого элемента и переместить его в новый бакет.

Сравнение с другими контейнерами

Контейнер          | Вставка (сред.)  | Вставка (худш.)  | Поиск (сред.)  | Поиск (худш.)
───────────────────┼──────────────────┼──────────────────┼────────────────┼─────────────
unordered_map      | O(1)             | O(n)             | O(1)           | O(n)
map (RB-tree)      | O(log n)         | O(log n)         | O(log n)       | O(log n)
vector             | O(n)             | O(n)             | O(n)           | O(n)
deque              | O(n)             | O(n)             | O(n)           | O(n)

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

1. Хороший сценарий (средний случай)

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

// Вставка 1000000 элементов с хорошей хеш-функцией
for (int i = 0; i < 1000000; i++) {
    map[i] = std::to_string(i);  // O(1) в среднем
}

// Поиск: O(1) в среднем
auto it = map.find(500000);

2. Плохой сценарий (худший случай)

// Если используются строки с плохой хешировкой
std::unordered_map<std::string, int> map;

for (const auto& key : my_keys) {
    map[key] = some_value;  // Может быть O(n) в худшем случае
}

3. Управление load factor

std::unordered_map<int, int> map;

// Заранее выделяем место для 1000 элементов
map.reserve(1000);

// Теперь вставки будут близки к O(1)
for (int i = 0; i < 1000; i++) {
    map[i] = i;  // Без rehash'ей
}

Когда использовать unordered_map vs map

Используй unordered_map если:

• Нужна O(1) вставка/поиск в среднем
• Не важен порядок элементов
• Ты уверен в качестве хеш-функции

Используй map если:

• Нужна гарантированная O(log n) сложность
• Нужен отсортированный порядок
• Нужен поиск по диапазону (lower_bound, upper_bound)
• Критичен худший случай

Выводы

• unordered_map вставка: O(1) в среднем, O(n) в худшем
• Rehash: происходит при load_factor > max_load_factor, стоит O(n)
• Используй reserve() если знаешь примерный размер
• Худший случай возможен только при плохой хеш-функции или adversarial input
• map безопаснее если критичен гарантированный худший случай