Does it make sense to use std::unordered_map<int, int> instead of std::map<int, int>?

Question

Should std::unordered_map<int, int> be faster than std::map`? I don't care about order, just fast lookup, so I thought I should use a hashtable. But then I thought maybe it'll try to additionally hash my keys or something like that (which I don't need)?

And a related question: I need to retrieve an int value by int key. Should I use unordered_map<int, int> or unordered_set<pair<int, int> > (in which case I'd need to implement hash function for my pair properly)?

Solution

The difference between a map<T,K> and an unordered_map<T,K> is that the first implementation relies on a tree while the second relies on an hashmap.

This means that complexities for basic operations (get and set) are logarithmic for a map and constant for an unordered_map.

There are other aspects in any case: an unordered_map may need a rehash when its load factor is reached (and this requires time and can be unpredictable) while a normal map doesn't involve such problems. In addition the unordered_map implementation could use separated chaining with buckets so if it happens to have many collisions, complexity becomes constant+linear for retrieval of the key.

I'd suggest you to benchmark both structures with some data with a pattern similar to the one you need, that will make your choice.

You don't need to define your own hash<int> for the unordered_map as it's already implemented.

Comments

[Violet Giraffe]

The point is, I'm already supplying the hashmap with hash values (my keys are hashes). Does it make sense?

[Jack]

No, you are not exactly supplying your hashmap with hash values, unless its capacity is 2<<(sizeof(int)*8) so that every int value can be mapped to its own cell, but in this case an int[2<<(sizeof(int)*8] array would suffice. And problems will be related to caching of the data, not to data structure perfomance anymore.

[rwong]

@VioletGiraffe : if desired, you can supply your own hash functions to unordered_map. Be sure to understand the pitfalls and caveats before doing so, however.