Как решается коллизия в std::unordered_map?

Разрешение коллизий в std::unordered_map

std::unordered_map в C++ использует chaining (раздельные цепочки) для разрешения коллизий. Когда два ключа имеют одинаковый хэш, они хранятся в одном bucket'е в виде связного списка.

Проблема: коллизии

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

map["Alice"] = 30;
map["Bob"] = 25;

// Если hash("Alice") == hash("Bob") → коллизия!

Решение: Chaining

std::unordered_map хранит для каждого bucket'а список элементов:

Buckets:
[0] → nullptr
[1] → (Alice, 30) → nullptr
[2] → (Bob, 25) → (David, 28) → nullptr  ← коллизия!
[3] → nullptr
...

Как это работает внутри

// Упрощённо, unordered_map выглядит так:
template<typename K, typename V>
class unordered_map {
private:
    // Вектор списков
    std::vector<std::list<std::pair<K, V>>> buckets;
    
public:
    V& operator[](const K& key) {
        // 1. Вычислить хэш
        size_t h = std::hash<K>{}(key);
        
        // 2. Найти bucket
        size_t idx = h % buckets.size();
        
        // 3. Найти элемент в цепочке
        for (auto& pair : buckets[idx]) {
            if (pair.first == key) {
                return pair.second;  // Нашли!
            }
        }
        
        // 4. Не нашли → добавить
        buckets[idx].push_back({key, V{}});
        return buckets[idx].back().second;
    }
};

Процесс разрешения коллизии при вставке

map["Alice"] = 30;

// Шаг 1: hash("Alice") = 123456
size_t hash_value = hash_function("Alice");  // 123456

// Шаг 2: bucket_index = 123456 % bucket_count
size_t index = hash_value % buckets.size();  // = 2

// Шаг 3: Проверить bucket[2]
if (bucket[2] пуст) {
    bucket[2].push_back({"Alice", 30});  // Вставить
} else {
    // Коллизия! Добавить в цепочку
    bucket[2].push_back({"Alice", 30});
}

Процесс разрешения коллизии при поиске

auto val = map["Alice"];  // Или map.find("Alice")

// Шаг 1: hash("Alice") = 123456
size_t hash_value = hash_function("Alice");

// Шаг 2: bucket_index = 123456 % bucket_count
size_t index = hash_value % buckets.size();

// Шаг 3: Перебрать элементы в bucket'е
for (auto& [key, value] : buckets[index]) {
    if (key == "Alice") {
        return value;  // Найден!
    }
}

// Не найден
return nullptr;

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

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> ages;
    
    // Вставка
    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;
    ages["David"] = 28;
    
    // Информация о bucket'ах
    std::cout << "Bucket count: " << ages.bucket_count() << std::endl;  // 16
    std::cout << "Load factor: " << ages.load_factor() << std::endl;    // ~0.25
    
    // Какой bucket для каждого ключа?
    for (auto& [key, value] : ages) {
        size_t bucket = ages.bucket(key);
        size_t chain_len = ages.bucket_size(bucket);
        std::cout << key << " → bucket " << bucket 
                  << " (chain length: " << chain_len << ")" << std::endl;
    }
    
    return 0;
}

// Вывод (примерно):
// Bucket count: 16
// Load factor: 0.25
// Alice → bucket 3 (chain length: 1)
// Bob → bucket 5 (chain length: 1)
// Charlie → bucket 2 (chain length: 1)
// David → bucket 5 (chain length: 2)  ← коллизия с Bob!

Сложность при коллизиях

// Лучший случай: нет коллизий
// find(key) = O(1)

// Худший случай: все в одном bucket'е
// find(key) = O(n)
// Это возможно если hash_function плохая

// Средний случай: α = n/m (load factor)
// find(key) = O(1 + α)  ≈ O(1)

Load Factor и Rehashing

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

// Load factor = количество элементов / количество bucket'ов
float alpha = map.size() / map.bucket_count();

std::cout << "Load factor: " << map.load_factor() << std::endl;
std::cout << "Max load factor: " << map.max_load_factor() << std::endl;  // 1.0

// Когда load_factor > max_load_factor → rehash
map.rehash(new_bucket_count);  // Явный rehash

Что происходит при rehash:

Бefore rehash (bucket_count = 8):
[0] → Alice
[1] →
[2] → Bob, David  ← коллизия
[3] →
...

After rehash (bucket_count = 16):
[0] → Alice
[2] → Bob
[5] → David
...

Когда возникают коллизии

1. Плохая хэш-функция

struct BadHash {
    size_t operator()(const std::string& s) const {
        return 42;  // Всегда 42! Все элементы в одном bucket'е
    }
};

std::unordered_map<std::string, int, BadHash> map;
// find() будет O(n)!

2. Множество элементов в малом bucket_count

auto map = std::unordered_map<int, int>();
for (int i = 0; i < 1000; i++) {
    map[i] = i;
}

// Если bucket_count не растёт → много коллизий
std::cout << map.load_factor() << std::endl;  // Может быть > 1.0

Оптимизация: избежание коллизий

// 1. Убедиться что bucket_count достаточно большой
std::unordered_map<std::string, int> map(1000);  // Reserve space

// 2. Проверить что хэш-функция хорошая
std::cout << map.load_factor() << std::endl;  // < 0.75

// 3. Явный rehash если нужно
if (map.load_factor() > 0.75) {
    map.rehash(map.bucket_count() * 2);
}

// 4. Использовать reserve() для предсказания
map.reserve(10000);  // Подготовить на 10000 элементов

Сравнение с std::map

// std::unordered_map (chaining for collisions)
std::unordered_map<int, std::string> umap;
// find() = O(1 + α) в среднем, O(n) в худшем

// std::map (никаких коллизий, красно-чёрное дерево)
std::map<int, std::string> map;
// find() = O(log n) всегда

// Когда использовать какой:
// unordered_map: когда нужно O(1) average case
// map: когда нужно O(log n) worst case гарантия

Итог

std::unordered_map разрешает коллизии через chaining:

1. Вычислить хэш ключа
2. Найти bucket по модулю хэша
3. Поискать в цепочке списка элементов в bucket'е
4. Добавить если не найдено

Средняя сложность: O(1) при load_factor < 0.75 Худшая сложность: O(n) если все в одном bucket'е

Сохранение хорошей load_factor через rehashing гарантирует O(1) производительность.