unordered_map в C++ реализован как хеш-таблица.
Принцип работы:
- Хеширование: Ключ преобразуется в целое число — хеш-код — с помощью хеш-функции.
- Индексация: Хеш-код используется для определения индекса (корзины или бакета) в массиве указателей или списков.
- Хранение: В каждой корзине хранятся пары ключ-значение.
Особенности:
- Корзины: Хеш-таблица состоит из массива корзин. Количество корзин может динамически изменяться (рехеширование) при достижении определенного коэффициента загрузки.
- Коллизии: Разные ключи могут давать одинаковый хеш-код. Это называется коллизией. Для разрешения коллизий в
unordered_map используется метод цепочек (chaining): элементы с одинаковым хешом добавляются в связанный список (или другую структуру данных) в соответствующей корзине.
- Хеш-функция и функция сравнения: Для правильной работы необходимы две вещи:
- Хорошая хеш-функция, которая равномерно распределяет ключи по корзинам, минимизируя коллизии.
- Функция эквивалентности (оператор
==), чтобы отличать ключи с одинаковым хеш-кодом в одной корзине.
- Производительность: В среднем, операции вставки, удаления и поиска имеют временную сложность O(1). В худшем случае (например, при большом количестве коллизий или плохо подобранной хеш-функции) производительность может деградировать до O(n), где n — количество элементов.
Пример структуры (упрощенно):
cpp
Процесс добавления элемента:
- Вычисляется хеш-код ключа.
- Определяется индекс корзины:
bucket_index = hash(key) % num_buckets.
- Пара ключ-значение добавляется в список элементов в этой корзине. Если ключ уже существует, значение обновляется.
Процесс поиска элемента:
- Вычисляется хеш-код ключа.
- Определяется индекс корзины.
- Проходится по списку элементов в этой корзине, сравнивая ключи с искомым ключом с помощью оператора
==.
Рехеширование происходит, когда количество элементов по отношению к количеству корзин превышает заданный порог (load factor). При рехешировании создается новый, более крупный массив корзин, и все элементы из старых корзин перехешируются и перемещаются в новые.