Как устроена хеш-таблица в unordered_map?

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

Ключевые шаги при работе с unordered_map:

1. Вычисление хеша: Для каждого ключа вычисляется хеш с помощью хеш-функции (std::hash по умолчанию или пользовательская).
2. Определение корзины: Хеш-код преобразуется в индекс корзины с помощью операции по модулю: индекс_корзины = хеш_код % количество_корзин.
3. Поиск/вставка/удаление элемента:
   • Поиск: Происходит последовательный перебор элементов в связном списке соответствующей корзины. Сравнение ключей выполняется с помощью оператора равенства (==).
   • Вставка: Новый элемент добавляется в конец связного списка соответствующей корзины. Если ключ уже существует, то (по умолчанию) элемент не вставляется или обновляется (в зависимости от операции).
   • Удаление: Элемент удаляется из связного списка соответствующей корзины после его обнаружения.
4. Разрешение коллизий: Если разные ключи имеют одинаковый хеш или попадают в одну и ту же корзину, это называется хеш-коллизией. unordered_map разрешает коллизии методом цепочек: все элементы, хеши которых указывают на одну и ту же корзину, хранятся в списке этой корзины.
5. Рехеширование: Для поддержания эффективной работы (снижения вероятности коллизий и уменьшения длины списков), unordered_map автоматически увеличивает количество корзин и перераспределяет элементы в них (выполняет рехеширование), когда коэффициент загрузки (отношение количества элементов к количеству корзин) превышает определенный порог.

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> ages;

    // Вставка элементов
    ages["Alice"] = 30; // Хеш "Alice" -> индекс корзины -> добавление в список корзины
    ages["Bob"] = 25;   // Хеш "Bob" -> индекс корзины -> добавление в список корзины

    // Поиск элемента
    if (ages.count("Alice")) { // Вычисление хеша "Alice", поиск в соответствующей корзине
        std::cout << "Alice is " << ages["Alice"] << " years old." << std::endl;
    }

    // Коэффициент загрузки
    std::cout << "Load factor: " << ages.load_factor() << std::endl;

    // Удаление элемента
    ages.erase("Bob"); // Вычисление хеша "Bob", поиск и удаление из соответствующей корзины

    return 0;
}

Важные аспекты:

• Хеш-функция: Должна быть эффективной и распределять ключи равномерно для минимизации коллизий. Хорошая хеш-функция критична для производительности.
• Оператор равенства: Используется для окончательной проверки, действительно ли найденный в корзине элемент соответствует искомому ключу (поскольку разные ключи могут иметь одинаковый хеш).
• Коэффициент загрузки: Влияет на производительность. Высокий коэффициент загрузки увеличивает вероятность коллизий и замедляет операции.
• Производительность: В среднем, основные операции (вставка, поиск, удаление) имеют временную сложность O(1). В худшем случае (например, при плохой хеш-функции и большом количестве коллизий) сложность может деградировать до O(n), где n — количество элементов.