Что происходит в случае коллизии при получении ключа для контейнера в C++?

В случае коллизии при получении ключа в ассоциативных контейнерах C++ (например, std::unordered_map, std::unordered_set) происходит следующее:

1. Вычисляется хеш ключа.
2. По хешу определяется номер "корзины" (bucket), в которую потенциально должен попасть элемент.
3. Если в этой корзине уже есть элементы с таким же хешем (т.е. произошла коллизия хешей), то контейнер начинает перебирать элементы внутри этой корзины.
4. Для каждого элемента в корзине выполняется сравнение ключа искомого элемента с ключом текущего элемента с помощью оператора эквивалентности (operator==).
5. Если сравнение ключей дает положительный результат, то найден нужный элемент.
6. Если после перебора всех элементов в корзине совпадения ключей не найдено, значит, элемент с таким ключом отсутствует в контейнере.

Существуют различные стратегии разрешения коллизий:

• Метод цепочек (Separate Chaining): В каждой корзине хранится список (например, односвязный список) элементов, имеющих одинаковый хеш. При коллизии новый элемент добавляется в этот список.

  // Пример схематичной реализации метода цепочек
  struct Node {
      Key key;
      Value value;
      Node* next;
  };
  
  struct Bucket {
      Node* head = nullptr; // Список элементов в корзине
  };
  
  Bucket buckets[NUM_BUCKETS];
  
  // При вставке/поиске элемента с коллизией
  // Перебираем список: head -> node1 -> node2 -> ...
  

• Метод открытой адресации (Open Addressing): Все элементы хранятся непосредственно в хеш-таблице. При коллизии ищется следующая свободная ячейка в таблице с использованием определенной стратегии:
  • Линейное зондирование (Linear Probing): Проверяются последовательно следующие ячейки (+1, +2, +3 ... от исходного индекса).

    // Пример схематичной реализации линейного зондирования
    struct Slot {
        Key key;
        Value value;
        bool occupied = false;
        bool deleted = false; // Для корректного поиска после удаления
    };
    
    Slot table[TABLE_SIZE];
    
    // При вставке/поиске, если table[hash] занято
    // Проверяем table[(hash + 1) % TABLE_SIZE], table[(hash + 2) % TABLE_SIZE], ...
    

  • Квадратичное зондирование (Quadratic Probing): Проверяются ячейки с квадратичным смещением (+1², +2², +3² ... от исходного индекса).
  • Двойное хеширование (Double Hashing): Используется вторая хеш-функция для определения шага зондирования.

Стандартные контейнеры C++ (std::unordered_map, std::unordered_set) обычно реализуют метод цепочек. При большом количестве коллизий эффективность операций (поиск, вставка, удаление) может ухудшаться, приближаясь к линейной зависимости от количества элементов в самой "заполненной" корзине в худшем случае, но в среднем остается близкой к константе при хорошей хеш-функции.