The Details

The unordered associative containers store their indices in buckets. In which bucket the index goes depends on the hash function, which maps the key to the index. If different keys are mapped to the same index, it’s called a collision. The hash function tries to avoid this.

Indices are typically stored in the bucket as a linked list. Since the access to the bucket is constant, the access to the linked list in the bucket is linear. The number of buckets is called capacity, the average number of elements for each bucket is called the load factor. In general, the C++ runtime generates new buckets if the load factor is greater than 1. This process is called rehashing and can also be triggered explicitly: