CODEWITHSUNDEEP
c++stlc++11
Bjarke H. Roune
Bjarke H. Roune

Reputation: 3727

Do values with same hash go in same bucket of std::unordered_map?

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

Bonus question: If same hash does not imply same bucket, then what is the purpose of being able to traverse buckets individually?

Upvotes: 6

Views: 1095

Answers (1)

rici
rici

Reputation: 241711

Objects with the same hash are put into the same bucket by unordered associative containers. Consequently, two equal objects must have the same hash.

23.2.5 paragraph 8:

The elements of an unordered associative container are organized into buckets. Keys with the same hash code appear in the same bucket.

Bonus question: Why might you want to traverse buckets individually?

Bonus answer: Because you want to process the container's contents in parallel. The bucket iterators are independent of each other, so each thread can process a bucket without co-ordination (provided no new entries are added to the container). And the buckets should be roughly the same size, so they provide a convenient parallelisation quantum.

Upvotes: 8

Related Questions