How is the storage of elements inside std::unordered_map implemented when collisions occur?

In std::unordered_map, elements are stored in a hash table where keys are transformed into an index using a hash function. When collisions occur (when different keys have the same hash), chaining is used:

• Each cell of the table contains a linked list (or another container) of elements whose hash matches the cell's index.
• When adding an element with a collision, it is placed in the list of the corresponding cell.
• During search or deletion, the list in that cell is traversed to find the desired key.

Thus, std::unordered_map efficiently handles collisions, maintaining an amortized access time close to constant.

Example (simplified):

#include <unordered_map>
#include <string>

std::unordered_map<std::string, int> map;
map["apple"] = 5;
map["banana"] = 3;
// If "apple" and "banana" have the same hash,
// they will be stored in the same list in the corresponding cell.