Как работает механизм разрешения коллизий в std::map?

В std::unordered_map для разрешения коллизий используется метод цепочек: внутри одной корзины все элементы выстраиваются в односвязный список. 2

Для каждого ключа определена хеш-функция, по которой вычисляется номер корзины (bucket), в которую должен попасть ключ. 2 Случай, когда два разных ключа оказываются в одной корзине, называется коллизией. 2

Если при вставке очередного элемента среднее число элементов в корзинах превышает определённый порог, число корзин автоматически увеличивается и происходит рехэширование. 2 При этом увеличивается число сегментов, пересчитываются все хэши элементов, выделяется память для таблицы и элементы вставляются заново. 1

Это дорогостоящая по времени и памяти операция, поэтому приходится искать компромисс между числом коллизий и частотой рехэширования. 1