CODEWITHSUNDEEP
c++unordered-map
Barış Uşaklı
Barış Uşaklı

Reputation: 13532

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

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?

Upvotes: 0

Views: 776

Answers (2)

Charlie
Charlie

Reputation: 1592

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).

Upvotes: 1

James McNellis
James McNellis

Reputation: 355387

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.

Upvotes: 3

Related Questions