Когда выгоднее использовать std::unordered_map?

std::unordered_map vs std::map: Когда и почему

std::unordered_map — это хеш-таблица, которая обеспечивает O(1) среднее время поиска вместо O(log n) у std::map (красно-чёрное дерево). Но это не всегда выгоднее!

Отличия: Структура данных

std::map:

• Красно-чёрное сбалансированное дерево
• Упорядоченные элементы (по компаратору)
• O(log n) поиск, вставка, удаление
• Предсказуемая производительность
• Больше операций с памятью

std::unordered_map:

• Хеш-таблица (массив + списки коллизий или открытая адресация)
• Неупорядоченные элементы
• O(1) среднее, O(n) худшее (при плохих хешах)
• Непредсказуемая производительность
• Меньше операций с памятью

Когда выгоднее std::unordered_map

1. Большое количество случайных поисков (100K+)

// Много поисков по ключу
std::unordered_map<int, std::string> cache;
for (int i = 0; i < 1000000; ++i) {
    auto it = cache.find(rand() % 100000);  // O(1) vs O(log n)
    if (it != cache.end()) {
        process(it->second);
    }
}

Бенчмарк:

• std::map: ~100 млн операций/сек
• std::unordered_map: ~500+ млн операций/сек (5x выигрыш!)

2. Кеширование и memoization

class MemoizedFib {
private:
    std::unordered_map<long long, long long> cache;

public:
    long long fib(long long n) {
        if (n <= 1) return n;
        
        auto it = cache.find(n);
        if (it != cache.end()) return it->second;  // O(1)
        
        long long result = fib(n-1) + fib(n-2);
        cache[n] = result;
        return result;
    }
};

3. Подсчёт частотности элементов

std::unordered_map<std::string, int> word_frequency;
for (const auto& word : document) {
    word_frequency[word]++;  // O(1) вставка/поиск
}

// vs std::map: O(log n) на каждой операции

4. Проверка принадлежности к множеству (100K+ элементов)

std::unordered_set<std::string> blacklist;
for (const auto& user : users) {
    if (blacklist.count(user.id)) {  // O(1) vs O(log n)
        process_ban(user);
    }
}

5. Таблицы символов в интерпретаторах/компиляторах

struct Variable {
    std::string name;
    Type type;
    Value value;
};

std::unordered_map<std::string, Variable> symbol_table;
// Тысячи поисков при компиляции/интерпретации

Когда выгоднее std::map

1. Нужен порядок элементов

// Отчёт в отсортированном порядке по ID
std::map<int, Report> reports;  // Автоматически отсортирована
for (const auto& [id, report] : reports) {
    print(report);  // Гарантированный порядок
}

// С unordered_map нужна дополнительная сортировка

2. Нужны операции диапазона (range queries)

// Все записи между временем T1 и T2
std::map<time_t, Log> logs;
auto start = logs.lower_bound(t1);
auto end = logs.upper_bound(t2);
for (auto it = start; it != end; ++it) {
    process(it->second);
}

// unordered_map не поддерживает это эффективно

3. Маленькие наборы данных (< 1000 элементов)

// При малом размере overhead хеширования > выигрыш
std::map<std::string, int> config;  // Конфиг с 20-50 параметрами
for (const auto& [key, value] : config) {
    apply_setting(key, value);
}

4. Плохая функция хеша или частые коллизии

// Если ключи генерируют плохие хеши
// (например, последовательные ID с модулем)
std::unordered_map<int, Data> bad_case;
for (int i = 0; i < 100000; ++i) {
    bad_case[i % 1000] = data;  // Много коллизий -> O(n)
}
// map будет быстрее!

5. Предсказуемость критична (real-time системы)

// Система с жёсткими ограничениями по времени
// map: гарантированно O(log n)
// unordered_map: может быть O(n) при коллизиях
std::map<int, RealTimeEvent> events;  // Выбираем стабильность

Практические сравнения

#include <benchmark/benchmark.h>
#include <map>
#include <unordered_map>

static void BenchmarkMapLookup(benchmark::State& state) {
    std::map<int, int> m;
    for (int i = 0; i < 10000; ++i) m[i] = i * 2;
    
    for (auto _ : state) {
        for (int i = 0; i < 10000; ++i) {
            benchmark::DoNotOptimize(m.at(i));  // O(log n)
        }
    }
}
BENCHMARK(BenchmarkMapLookup);

static void BenchmarkUnorderedMapLookup(benchmark::State& state) {
    std::unordered_map<int, int> m;
    for (int i = 0; i < 10000; ++i) m[i] = i * 2;
    
    for (auto _ : state) {
        for (int i = 0; i < 10000; ++i) {
            benchmark::DoNotOptimize(m.at(i));  // O(1)
        }
    }
}
BENCHMARK(BenchmarkUnorderedMapLookup);

Результаты (примерно):

• map lookup: ~250ns per operation
• unordered_map lookup: ~40ns per operation

Выбор: Решающие факторы

Оптимизация unordered_map

// Выбор хорошей функции хеша
struct CustomHash {
    size_t operator()(const std::string& s) const {
        // Используй хорошую функцию хеша (murmur3, xxhash)
        return std::hash<std::string>{}(s);  // По умолчанию плохая!
    }
};

std::unordered_map<std::string, int, CustomHash> m;

// Резервируй место заранее
m.reserve(expected_size);  // Избегай rehashing

// Контролируй load factor
if (m.load_factor() > 0.75) {
    m.rehash(m.size() * 2);  // Явный rehash
}

Рекомендация

Используй std::unordered_map когда:

• Нужны частые случайные поиски (100K+ операций)
• Производительность поиска критична
• Порядок элементов не важен
• Хеш-функция хороша и коллизии редки

Используй std::map когда:

• Нужен упорядоченный доступ
• Нужны range queries
• Маленький размер данных
• Нужна предсказуемая производительность
• Хеш-функция может быть плохой

Практический совет: Начни с std::map для безопасности, потом профилируй и переходи на unordered_map, если bottleneck в поисках.