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

unordered_map в C++ реализован как хеш-таблица.

Принцип работы:

1. Хеширование: Ключ преобразуется в целое число — хеш-код — с помощью хеш-функции.
2. Индексация: Хеш-код используется для определения индекса (корзины или бакета) в массиве указателей или списков.
3. Хранение: В каждой корзине хранятся пары ключ-значение.

Особенности:

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

Пример структуры (упрощенно):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Для связного списка в корзине
};

struct Bucket {
  Node* head; // Указатель на начало списка
};

Bucket* buckets; // Массив корзин
size_t num_buckets;

Процесс добавления элемента:

1. Вычисляется хеш-код ключа.
2. Определяется индекс корзины: bucket_index = hash(key) % num_buckets.
3. Пара ключ-значение добавляется в список элементов в этой корзине. Если ключ уже существует, значение обновляется.

Процесс поиска элемента:

1. Вычисляется хеш-код ключа.
2. Определяется индекс корзины.
3. Проходится по списку элементов в этой корзине, сравнивая ключи с искомым ключом с помощью оператора ==.

Рехеширование происходит, когда количество элементов по отношению к количеству корзин превышает заданный порог (load factor). При рехешировании создается новый, более крупный массив корзин, и все элементы из старых корзин перехешируются и перемещаются в новые.