CODEWITHSUNDEEP
c++c++11stl
Tim Kuipers
Tim Kuipers

Reputation: 1764

Do all elements in a bucket of an unordered_map have the same hash?

Are all keys in a std::unordered_map guaranteed to have the same hash? Or can keys with different hashes reside within the same bucket?

Does being in the same bucket imply having the same hash?

Upvotes: 2

Views: 1182

Answers (2)

Jonathan Wakely
Jonathan Wakely

Reputation: 171501

Does being in the same bucket imply having the same hash?

No.

A hash code is a 32-bit or 64-bit number, so could take a vast number of values, but an unordered container doesn't have billions of buckets. It will have N buckets and map the billions of possible codes to one of those N buckets.

Typically it will use the modulus operator (%) to reduce the hash code to a smaller value which is used as an index into an array of buckets.

So if there are 13 buckets then every element in a bucket will have the same hash code modulo 13, but not necessarily the same hash code.

The load_factor and max_load_factor members can be used to query and control the "load factor" which describes the average number of elements per bucket. A higher load factor means that elements with different hash codes are more likely to end up in the same bucket (because there are fewer buckets that the hash%N values are distributed across).

Upvotes: 8

ALEXANDER KONSTANTINOV
ALEXANDER KONSTANTINOV

Reputation: 913

No, it's not guaranteed anywhere.

Unordered_map has function bucket_size, which returns the number of elements in specific bucket:

http://www.cplusplus.com/reference/unordered_map/unordered_map/bucket_size/

This function can return value greater than one, it means that different elements can go to same bucket.

Upvotes: 0

Related Questions