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