Values โ€‹โ€‹with the same hash go in the same bucket std :: unordered_map?

If two keys for std :: unordered_map have the same hash value, is the standard guaranteed that they will go into the same bucket? We assume that the keys are not equal according to the template equality predicate; they have only the same hash function value.

Bonus question: if the same hash does not imply the same bucket, then what is the purpose of individually moving buckets?

+6
source share
1 answer

Objects with the same hash are placed in the same bucket in unordered associative containers. Therefore, two equal objects must have the same hash.

23.2.5 clause 8:

Unordered associative container elements are organized in buckets. Keys with the same hash code appear in the same bucket.

Bonus question: why can you move the buckets individually?

Bonus answer: because you want to process the contents of the container in parallel. The bucket iterators are independent of each other, so each thread can process the bucket without coordination (provided that no new entries are added to the container). And the buckets should be about the same size, so they provide a convenient parallelization quantum.

+8
source

Source: https://habr.com/ru/post/927773/


All Articles