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

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

Ответ зависит от ситуации:

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

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

unordered_map использует хеш-таблицу — массив "корзин" (buckets), где каждая корзина содержит список элементов:

// Внутренняя структура:
// Hash Table:
// [0] -> [bucket 0: {key1, val1} -> {key2, val2}]
// [1] -> [bucket 1: {key3, val3}]
// [2] -> [bucket 2: (empty)]
// [3] -> [bucket 3: {key4, val4} -> {key5, val5} -> {key6, val6}]
// ...

Процесс поиска элемента:

1. Вычислить хеш ключа: hash(key) — O(1)
2. Найти корзину: bucket_index = hash(key) % num_buckets — O(1)
3. Найти элемент в корзине — O(1) в среднем, O(n) в худшем

#include <unordered_map>

std::unordered_map<std::string, int> map;
map["apple"] = 10;
map["banana"] = 20;

// Чтение:
int value = map.at("apple");  // Сложность?

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

Если хеш-функция хороша и нет коллизий:

// Идеальный случай:
// Hash Table:
// [0] -> {apple, 10}
// [1] -> {banana, 20}
// [2] -> (empty)
// [3] -> {cherry, 30}

// Поиск "apple":
// 1. hash("apple") = 5 -> 5 % 4 = 1
// 2. bucket[1] содержит {apple, 10}
// 3. Сравнение: hash и key совпадают
// 4. Возврат значения
// Всего: 3 операции = O(1)

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

Если много коллизий (элементы с разными ключами хешируются в один bucket):

// Плохой случай (все элементы в одной корзине):
// Hash Table:
// [0] -> (empty)
// [1] -> (empty)
// [2] -> {key1, val1} -> {key2, val2} -> {key3, val3} -> ... -> {keyN, valN}
// [3] -> (empty)

// Поиск "keyN" (последний):
// 1. hash("keyN") -> хеш совпадает с остальными
// 2. bucket[2] содержит цепь из N элементов
// 3. Нужно сравнить N элементов
// 4. Возврат значения в конце
// Всего: N операций = O(n)

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

#include <unordered_map>
#include <chrono>

std::unordered_map<int, int> map;

// Лучший случай: хорошее распределение
for (int i = 0; i < 1000000; i++) {
    map[i] = i * 2;
}

auto start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < 1000000; i++) {
    int val = map.at(i);  // O(1) в среднем
}
auto end = std::chrono::high_resolution_clock::now();
std::cout << "Time: " 
    << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
    << "ms\n";
// Результат: ~50-100ms (быстро)

// Худший случай: плохая хеш-функция или коллизии
std::unordered_map<int, int> bad_map;
// Симулируем коллизии (все хешируются в одну корзину)
// Это редко происходит в реальном коде...

// Сравнение с std::map:
std::map<int, int> tree_map;
for (int i = 0; i < 1000000; i++) {
    tree_map[i] = i * 2;
}

start = std::chrono::high_resolution_clock::now();
for (int i = 0; i < 1000000; i++) {
    int val = tree_map.at(i);  // O(log n) всегда
}
end = std::chrono::high_resolution_clock::now();
std::cout << "Time: " 
    << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
    << "ms\n";
// Результат: ~150-300ms (медленнее, но гарантировано)

// unordered_map быстрее в среднем, но может быть медленнее в худшем

Load Factor и переработка

Производительность зависит от load factor (количество элементов / количество buckets):

std::unordered_map<int, int> map;

// По умолчанию max_load_factor() = 1.0
std::cout << map.max_load_factor() << "\n";  // Обычно ~1.0

// Когда load_factor превышает max, происходит rehashing
for (int i = 0; i < 10000; i++) {
    map[i] = i;  // При превышении load_factor:
                  // 1. Создаётся новая таблица с большим количеством buckets
                  // 2. Все элементы перехешируются (O(n))
                  // 3. Амортизированная сложность всё ещё O(1)
}

// Проверка load_factor:
std::cout << "Load factor: " << map.load_factor() << "\n";
std::cout << "Bucket count: " << map.bucket_count() << "\n";

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

#include <map>
#include <unordered_map>

std::map<int, int> tree_map;              // Гарантирует O(log n)
std::unordered_map<int, int> hash_map;    // Обычно O(1), иногда O(n)

// Используй unordered_map когда:
// - Важна скорость в среднем случае
// - Не нужен порядок элементов
// - Нет критических требований к худшему случаю

// Используй map когда:
// - Нужна гарантия O(log n)
// - Элементы должны быть отсортированы
// - Критичны худшие случаи (real-time системы)

Как улучшить производительность

1. Выбери хорошую хеш-функцию

// Плохая хеш-функция: коллизии
struct BadHash {
    size_t operator()(const std::string& s) const {
        return s.size();  // Много элементов одинакового размера?
    }
};

// Хорошая хеш-функция: хорошее распределение
struct GoodHash {
    size_t operator()(const std::string& s) const {
        size_t hash = 0;
        for (char c : s) {
            hash = hash * 31 + c;  // Распределяет хорошо
        }
        return hash;
    }
};

std::unordered_map<std::string, int, BadHash> bad;   // Медленнее
std::unordered_map<std::string, int, GoodHash> good; // Быстрее

2. Установи начальный размер

std::unordered_map<int, int> map;

// Если знаешь размер заранее, зарезервируй место
map.reserve(1000000);  // Избегай rehashing

for (int i = 0; i < 1000000; i++) {
    map[i] = i;  // Никаких дополнительных rehashing'ов
}

3. Выбери правильный контейнер

// Для малых данных: unordered_map иногда медленнее из-за оверхеда
std::unordered_map<int, int> small;  // может быть медленнее чем vector
std::vector<std::pair<int, int>> small_vec;  // может быть быстрее

// Для больших данных: unordered_map выигрывает
std::unordered_map<std::string, int> large;  // O(1) вместо O(log n)

Итог: Сложность чтения в std::unordered_map составляет O(1) в среднем случае благодаря хешированию. Однако в худшем случае это O(n), когда все элементы хешируются в один bucket (редко на практике). Используй unordered_map для быстрого доступа в среднем, но помни о потенциальных худших случаях в критичных системах. Для гарантированной производительности используй std::map с O(log n).