В чем разница между сбалансированным деревом и std::unordered_map?

Сбалансированное дерево (std::map) vs std::unordered_map

Это две основные структуры данных в C++ для хранения ключ-значение пар. Они кардинально различаются по структуре и производительности.

std::map: Красно-чёрное дерево

Структура: Бинарное сбалансированное дерево поиска (Red-Black Tree)

std::map<std::string, int> data;
data["alice"] = 30;
data["bob"] = 25;
data["charlie"] = 35;
data["diana"] = 28;

// Внутренняя структура дерева (примерно):
//       bob(25)
//      /        \
//   alice(30)  charlie(35)
//            /
//         diana(28)

Характеристики:

• Упорядоченные элементы (по компаратору, по умолчанию по ключу)
• O(log n) поиск, вставка, удаление
• Дерево сбалансировано автоматически
• Итерация в отсортированном порядке
• Предсказуемая производительность (гарантированно O(log n))

std::map<int, std::string> m;
for (int i = 0; i < 1000; ++i) {
    m[rand()] = "data";  // O(log n)
}

// Итерация в отсортированном порядке
for (const auto& [key, value] : m) {
    std::cout << key << " -> " << value << std::endl;  // Отсортировано!
}

// Range queries
auto start = m.lower_bound(100);
auto end = m.upper_bound(500);
for (auto it = start; it != end; ++it) {
    // Обработать элементы в диапазоне [100, 500]
}

std::unordered_map: Хеш-таблица

Структура: Хеш-таблица (массив + списки коллизий или открытая адресация)

std::unordered_map<std::string, int> data;
data["alice"] = 30;
data["bob"] = 25;
data["charlie"] = 35;
data["diana"] = 28;

// Внутренняя структура (примерно):
// Bucket 0: []
// Bucket 1: [bob(25) -> alice(30)]
// Bucket 2: [diana(28)]
// Bucket 3: [charlie(35)]
// Bucket 4: []
// ...

Характеристики:

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

std::unordered_map<int, std::string> m;
for (int i = 0; i < 1000; ++i) {
    m[rand()] = "data";  // O(1) среднее
}

// Итерация в произвольном порядке
for (const auto& [key, value] : m) {
    std::cout << key << " -> " << value << std::endl;  // СЛУЧАЙНЫЙ порядок
}

Подробное сравнение

Производительность: Реальные бенчмарки

Тест 1: 100 тыс. поисков в контейнере из 10 тыс. элементов

// std::map: 100 млн. операций/сек
std::map<int, int> m;
for (int i = 0; i < 10000; ++i) m[i] = i * 2;

auto start = high_resolution_clock::now();
for (int i = 0; i < 100000; ++i) {
    auto it = m.find(rand() % 10000);  // O(log n)
}
auto elapsed = high_resolution_clock::now() - start;
// ~400-500 микросекунд

// std::unordered_map: 700+ млн. операций/сек
std::unordered_map<int, int> m;
for (int i = 0; i < 10000; ++i) m[i] = i * 2;

auto start = high_resolution_clock::now();
for (int i = 0; i < 100000; ++i) {
    auto it = m.find(rand() % 10000);  // O(1)
}
auto elapsed = high_resolution_clock::now() - start;
// ~50-80 микросекунд (6-10x выигрыш!)

Тест 2: Range query (по диапазону ключей)

std::map:

std::map<int, std::string> m = {{1, "a"}, {5, "b"}, {10, "c"}, {15, "d"}};

// Легко найти элементы в диапазоне [5, 15]
auto start = m.lower_bound(5);
auto end = m.upper_bound(15);
for (auto it = start; it != end; ++it) {
    std::cout << it->second << std::endl;  // b, c
}

std::unordered_map:

std::unordered_map<int, std::string> m = {{1, "a"}, {5, "b"}, {10, "c"}, {15, "d"}};

// Нужно проверить ВСЕ элементы (O(n))
std::vector<std::pair<int, std::string>> range_results;
for (const auto& [k, v] : m) {
    if (k >= 5 && k <= 15) {
        range_results.push_back({k, v});
    }
}
// Потом отсортировать, если нужен порядок
std::sort(range_results.begin(), range_results.end());

Операции, специфичные для std::map

std::map<int, std::string> m;
m[10] = "ten";
m[20] = "twenty";
m[30] = "thirty";

// lower_bound: первый элемент >= ключа
auto it1 = m.lower_bound(15);  // Указывает на 20

// upper_bound: первый элемент > ключа
auto it2 = m.upper_bound(20);  // Указывает на 30

// equal_range: диапазон элементов с ключом
auto range = m.equal_range(20);  // [20, 30)

// Итерация в обратном порядке
for (auto it = m.rbegin(); it != m.rend(); ++it) {
    std::cout << it->first << " -> " << it->second << std::endl;
}

Операции, специфичные для std::unordered_map

std::unordered_map<std::string, int> m;
m["alice"] = 30;
m["bob"] = 25;

// count: быстрая проверка существования
if (m.count("alice")) {
    std::cout << "alice found" << std::endl;  // O(1)
}

// Load factor: контроль производительности
std::cout << "Load factor: " << m.load_factor() << std::endl;

// Rehash: явное переаллоцирование buckets
m.rehash(1000);  // Если load_factor() > max_load_factor()

// Bucket interface
for (size_t i = 0; i < m.bucket_count(); ++i) {
    for (auto it = m.begin(i); it != m.end(i); ++it) {
        std::cout << it->first << " -> " << it->second << std::endl;
    }
}

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

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

• ✓ Нужны элементы в отсортированном порядке
• ✓ Нужны range queries (lower_bound, upper_bound)
• ✓ Нужна обратная итерация
• ✓ Нужна предсказуемая производительность O(log n)
• ✓ Маленький размер данных
• ✓ Работаешь с нестабильной хеш-функцией

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

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

Проблемы std::unordered_map

Хеш-коллизии и худший случай:

std::unordered_map<int, int> m;

// Плохой случай: коллизии
for (int i = 0; i < 100000; ++i) {
    m[i % 1000] = i;  // Много коллизий!
    // Операции становятся O(n) вместо O(1)
}

DoS атака через хеш-функцию:

// Атакующий может отправить ключи, генерирующие коллизии
// Это замедлит поиск до O(n)
std::unordered_map<std::string, int> m;

// Если хеш-функция слабая, злоумышленник может отправить
// специально подобранные строки
for (const auto& key : attacker_provided_keys) {
    m[key];  // Может быть O(n) для каждого ключа!
}

Гибридный подход

// Сначала используй unordered_map для быстрого поиска
std::unordered_map<int, Data> cache;

// Затем копируй в map для итерации в порядке
std::map<int, Data> sorted_view;
for (const auto& [k, v] : cache) {
    sorted_view[k] = v;
}

// Или используй vector + sort для большого набора
std::vector<std::pair<int, Data>> items;
for (const auto& [k, v] : cache) {
    items.push_back({k, v});
}
std::sort(items.begin(), items.end());

Резюме

std::map (Дерево):

• Упорядоченные данные
• O(log n) гарантированно
• Range queries
• Стабильная производительность

std::unordered_map (Хеш):

• Неупорядоченные данные
• O(1) среднее, O(n) худшее
• Нет range queries
• Может быть до 10x быстрее при правильном использовании

Выбирай в зависимости от требований: нужна ли упорядоченность и предсказуемость или максимальная производительность поиска?