0

I know that the C++ standard library includes the ordered and the unordered map (std::map and std::unordered_map) containers, but why is there no hashmap available on C++? I was asked this questions on one of my coding interviews and I did not have an answer. Even google did not give me a satisfactory answer and just gave me ways to use unordered map and set to solve hashmap questions.

4
  • 6
    Precisely which properties of a hashmap do you want that are not satisfied by one of the STL containers? Feb 7 at 18:59
  • 1
    What question exactly does this SO question leave open?
    – Doc Brown
    Feb 7 at 19:31
  • 3
    The std::unordered_map is a hash table! In contrast, std::map corresponds to Java's TreeMap. The Java standard library has two hash tables (HashMap and Hashtable). The Hashtable class should be treated as a historical artefact though. It's built-in synchronization is undesirable in most contexts. If you want a synchronized hash table in C++ you'd guard accesses with a std::mutex, or (more reasonably) use a third party library.
    – amon
    Feb 7 at 19:53
  • 2
    The only real difference here is that C++'s naming centers around utility (it's a map, is it ordered or not?), whereas Java's naming centers around implementation (a HashMap is hash-based, so you're left to infer that it's unordered)
    – Alexander
    Feb 7 at 21:15

1 Answer 1

5

In short

An interview question like "why isn't there a HashMap in C++" should be immediately answered with "Because there is std::unordered_map".

Some more arguments

According to the Java documentation, a HashMap<K,V> is:

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

The idea is to use the hash code of the key instead of keeping the set of keys sorted. As explained here the default computation is object.hashCode() but it may be worth to override is for a better distribution and hence a better performance.

In C++, the closest type is a std::unordered_map<K,V>. It also works with a hash code and provides a very similar functionality with similar performances. The main difference is that there is no default hash code for custom types. So you'd often need to define a hash code class that can be provided as a strategy to the map (or you'll have to specialize the std::hash<K>). If you're not familiar with hash codes, this is a little bit cumbersome, so std::map is used more frequently.

1
  • Conversely, std::unordered_map can sometimes be a better choice with types that aren't suited to std::map (because they can't be totally ordered). Feb 10 at 14:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.