What happens in the event of a collision when…

In case of a collision when obtaining a key in associative containers of C++ (for example, std::unordered_map, std::unordered_set), the following occurs:

The hash of the key is computed.
The number of the "bucket" where the element should potentially go is determined based on the hash.
If there are already elements with the same hash in this bucket (i.e., a hash collision has occurred), the container starts iterating through the elements within this bucket.
For each element in the bucket, the key of the sought element is compared with the current element's key using the equality operator (operator==).
If the key comparison yields a positive result, the desired element is found.
If after checking all elements in the bucket no match is found, it means the element with such a key is absent in the container.

There are various collision resolution strategies:

Separate Chaining: Each bucket stores a list (e.g., a singly linked list) of elements with the same hash. When a collision occurs, the new element is added to this list.

// Example schematic implementation of separate chaining
struct Node {
    Key key;
    Value value;
    Node* next;
};

struct Bucket {
    Node* head = nullptr; // List of elements in the bucket
};

Bucket buckets[NUM_BUCKETS];

// When inserting/searching an element with a collision
// Iterate through the list: head -> node1 -> node2 -> ...

Open Addressing: All elements are stored directly in the hash table. When a collision occurs, the next free cell in the table is searched using a specific strategy:
- Linear Probing: Sequentially check the following cells (+1, +2, +3 ... from the original index).
```
// Example schematic implementation of linear probing
struct Slot {
    Key key;
    Value value;
    bool occupied = false;
    bool deleted = false; // For correct search after deletion
};

Slot table[TABLE_SIZE];

// When inserting/searching, if table[hash] is occupied
// Check table[(hash + 1) % TABLE_SIZE], table[(hash + 2) % TABLE_SIZE], ...
```
- Quadratic Probing: Cells are checked with quadratic displacement (+1², +2², +3² ... from the original index).
- Double Hashing: A second hash function is used to determine the probing step.

Standard C++ containers (std::unordered_map, std::unordered_set) typically implement separate chaining. When there are many collisions, the efficiency of operations (search, insert, delete) can deteriorate, approaching linear dependence on the number of elements in the "filled" bucket in the worst case, but on average, it remains close to constant with a good hash function.

What happens in the event of a collision when obtaining a key for a container in C++?