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

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

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

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