What strategies are used to handle hash collisions in an unordered_map container?

In an unordered_map container, chaining is usually used to handle hash collisions. This means that all elements with the same hash index are stored in a linked list or another data structure within a single bucket.

When a collision occurs, the new element is added to the list of the corresponding bucket. During search, the elements in this bucket are traversed to find the desired key.

Thus, the main strategies are:

• Chaining — storing collisions in lists within each bucket.
• In some implementations, other structures such as balanced trees may be used for buckets to speed up search when there are many collisions.

This is roughly how the standard unordered_map implementation in C++ is structured.