Reputation: 1764
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
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
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