How are collisions handled when using std::unordered_map?

In std::unordered_map, collision handling is done using chaining. This means that all elements with the same hash index (bucket) are stored in a linked list or another structure within that bucket.

When inserting or searching for an element, the hash of the key is first computed, then the corresponding bucket is determined. If there are already elements in the bucket, a sequential search is performed to find the desired key. This allows efficient handling of collisions without losing elements.

Example:

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> map;
    map[1] = "one";
    map[2] = "two";
    // If 1 and 2 fall into the same bucket (collision), they will be stored in a chain
    std::cout << map[1] << ", " << map[2] << std::endl;
    return 0;
}