CODEWITHSUNDEEP
c++hash
Jacob G
Jacob G

Reputation: 306

How does unordered_map use its hash internally?

How does unordered_map use the hash function internally to access a bucket that belongs to a key?

std::hash returns a size_t type, that may be larger than the number of the buckets that exist in the container. How is the returned hash value mapped to a bucket index?

Does a typical unordered_map implementation perform a modulo of the returned hash by size() or by max_size(), or does something more complicated happen?

Upvotes: 3

Views: 897

Answers (1)

Mike Seymour
Mike Seymour

Reputation: 254711

Does a typical unordered_map implementation perform a modulo of the returned hash by size() or by max_size(), or does something more complicated happen?

Almost. The modulo would be bucket_count(), since that's the number of buckets in the hash table.

The standard doesn't require this to be done with a modulo operation, just that the bucket() function maps key values to the range [0,bucket_count) in some way, and that keys with equivalent hashes map to the same bucket. The modulus of the hash is the most straightforward way to do that.

Upvotes: 5

Related Questions