Хэширование в unordered set работает следующим образом: 1

1. Хеш-функция принимает элемент и вычисляет хэш-код — целое число. 1 В идеале хеш-функция должна равномерно распределять хэш-коды в диапазоне возможных значений, чтобы снизить вероятность коллизий (когда несколько элементов сопоставляются с одним и тем же хэш-кодом). 1
2. Превращение хэш-кода в индекс корзины. 1 После вычисления хэш-кода его преобразуют в индекс корзины во внутренней структуре набора (обычно это массив корзин). 1 Количество корзин обычно больше, чем количество элементов, чтобы обеспечить эффективное распределение и обработку коллизий. 1
3. Обработка коллизий. 1 Коллизии возникают, когда несколько элементов производят одинаковый хэш-код и должны храниться в одной корзине. 1 Для разрешения коллизий используют, например, метод цепочек (когда внутри одной корзины все элементы выстраиваются в односвязный список) или открытое адресация (когда исследуются соседние корзины, чтобы найти свободный слот для сталкивающегося элемента). 3
4. Вставка и поиск элементов. 1 При вставке элемента в неупорядоченный набор применяется хеш-функция для вычисления хэш-кода. 1 Затем хэш-код используется для определения подходящей корзины для элемента. 1 Если корзина пустая, элемент помещается прямо в неё. 1 В случае коллизий используется метод разрешения коллизий. 1
5. Поиск элемента. 1 Во время поиска элемента вычисляется хэш-код для искомого элемента, и набор проверяет соответствующую корзину на наличие элемента. 1 Хэш-код позволяет быстро определить корзину для поиска, что значительно повышает эффективность операции поиска. 1