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

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

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

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

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

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