В случае коллизии при получении ключа в ассоциативных контейнерах C++ (например, std::unordered_map, std::unordered_set) происходит следующее:
- Вычисляется хеш ключа.
- По хешу определяется номер "корзины" (bucket), в которую потенциально должен попасть элемент.
- Если в этой корзине уже есть элементы с таким же хешем (т.е. произошла коллизия хешей), то контейнер начинает перебирать элементы внутри этой корзины.
- Для каждого элемента в корзине выполняется сравнение ключа искомого элемента с ключом текущего элемента с помощью оператора эквивалентности (
operator==).
- Если сравнение ключей дает положительный результат, то найден нужный элемент.
- Если после перебора всех элементов в корзине совпадения ключей не найдено, значит, элемент с таким ключом отсутствует в контейнере.
Существуют различные стратегии разрешения коллизий:
- Метод цепочек (Separate Chaining): В каждой корзине хранится список (например, односвязный список) элементов, имеющих одинаковый хеш. При коллизии новый элемент добавляется в этот список.
cpp
- Метод открытой адресации (Open Addressing): Все элементы хранятся непосредственно в хеш-таблице. При коллизии ищется следующая свободная ячейка в таблице с использованием определенной стратегии:
- Линейное зондирование (Linear Probing): Проверяются последовательно следующие ячейки (+1, +2, +3 ... от исходного индекса).
cpp
- Квадратичное зондирование (Quadratic Probing): Проверяются ячейки с квадратичным смещением (+1², +2², +3² ... от исходного индекса).
- Двойное хеширование (Double Hashing): Используется вторая хеш-функция для определения шага зондирования.
Стандартные контейнеры C++ (std::unordered_map, std::unordered_set) обычно реализуют метод цепочек. При большом количестве коллизий эффективность операций (поиск, вставка, удаление) может ухудшаться, приближаясь к линейной зависимости от количества элементов в самой "заполненной" корзине в худшем случае, но в среднем остается близкой к константе при хорошей хеш-функции.