How does std::unordered_map return correct value from a bucket

Question

I have a std::unordered_map<std::string, int> map;

Then inserting tons of elements into this but the string keys are all unique.

Is the following scenario possible and how is it handled?

map[x] = 5;
map[y] = 3;

Lets assume x and y are different strings but they produce the same hash, so 5 and 3 are placed in the same bucket.

When we try to retrieve the value with map[x] how does the map return the correct value 5? Hashing x will give the bucket with the two elements 5, 3 but I don't see how it gets the correct value without having the key itself to compare against.

What am I missing?

Answer 1

The full declaration of unordered_map looks like so:

template <
    class Key,
    class T,
    class Hash      = std::hash<Key>,
    class KeyEqual  = std::equal_to<Key>,
    class Allocator = std::allocator<std::pair<Key const, T>>
> class unordered_map;

Observe that it requires both a hash function and an equality comparer for the key type.

When searching for the element with a particular key, the container will first find the correct bucket using the hash function, then will walk the elements in that bucket, comparing the key of each element using the equality comparer.

Answer 2

The bucket is just that, a bucket. unordered_map is actually a template, taking, among other things, a key and value type, and a function that checks keys for equality (defaults to std::equal_to<KeyType>) It uses the equality comparison to find the element in the bucket that matches the value you're searching for.

hash tables in general degenerate to linear or log time if you're completely evil and feed them keys with significant numbers of collisions, in practice they're generally close to O(1).