Как решается хэш-коллизия в unordered_map?

Как решается хэш-коллизия в unordered_map

Хэш-коллизия — это ситуация, когда два разных ключа при хэшировании дают один и тот же индекс в хэш-таблице. В C++ стандартная библиотека решает эту проблему методом chaining (цепочек), который является одним из наиболее распространённых подходов.

Принцип работы chaining в unordered_map

unordered_map хранит элементы в виде массива бакетов (buckets), где каждый бакет содержит связный список пар ключ-значение:

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> map;
    map["apple"] = 1;
    map["apples"] = 2;  // может привести к коллизии
    map["orange"] = 3;
    
    // Внутренняя структура:
    // buckets[0] -> ("apple", 1) -> ("apples", 2)
    // buckets[1] -> ("orange", 3)
    // buckets[2] -> ...
}

Этапы разрешения коллизии

1. Вычисление хэша: При вставке или поиске ключа вычисляется хэш: hash(key) % num_buckets

2. Проверка цепочки: Если в соответствующем бакете уже есть элементы, алгоритм проходит по всей цепочке

3. Поиск совпадения: Сравниваются ключи через оператор == (по умолчанию) или пользовательский компаратор

4. Вставка или обновление: Если ключ найден — обновляется значение, иначе добавляется новый элемент в начало цепочки

Код хеш-функции и коллизий

#include <unordered_map>
#include <functional>

struct CustomHash {
    size_t operator()(const std::string& s) const {
        // Простой пример хэш-функции
        size_t hash = 0;
        for (char c : s) {
            hash = hash * 31 + static_cast<size_t>(c);
        }
        return hash;
    }
};

int main() {
    // unordered_map использует std::hash<> по умолчанию
    std::unordered_map<std::string, int> map1;
    
    // Можно передать пользовательскую функцию хэширования
    std::unordered_map<std::string, int, CustomHash> map2;
    
    // Проверить количество бакетов и их занятость
    std::cout << "Buckets: " << map1.bucket_count() << std::endl;
    std::cout << "Load factor: " << map1.load_factor() << std::endl;
}

Оптимизация через rehashing

Когда коэффициент загрузки (load_factor = size / bucket_count) превышает max_load_factor() (по умолчанию 1.0), происходит rehashing:

std::unordered_map<int, std::string> map;
map.max_load_factor(0.75);  // Устанавливаем порог
map.reserve(100);            // Резервируем место заранее

// При превышении load_factor:
// 1. Создаётся новая таблица большего размера
// 2. Все элементы переживируют в новую таблицу
// 3. Старая таблица удаляется

Сложность операций

• Лучший случай (нет коллизий): O(1) для поиска, вставки, удаления
• Худший случай (все элементы в одном бакете): O(n) для поиска
• Средний случай (хорошая хэш-функция): O(1) с амортизацией

Практические рекомендации

• Используйте std::unordered_map, когда порядок элементов неважен и нужна быстрая вставка/поиск
• Если критична производительность, избегайте коллизий через хорошую хэш-функцию
• Для пользовательских типов реализуйте специализированную хэш-функцию
• Мониторьте load_factor в критичных местах кода

struct MyData {
    int id;
    std::string name;
};

struct MyDataHash {
    size_t operator()(const MyData& d) const {
        return std::hash<int>()(d.id) ^ (std::hash<std::string>()(d.name) << 1);
    }
};

int main() {
    std::unordered_map<MyData, int, MyDataHash> map;
}

Метод chaining гарантирует корректность данных при любом количестве коллизий, но деградирует производительность при плохой хэш-функции.