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.
1 Answer
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.
answered Feb 7, 2022 at 19:48
-
Conversely,
std::unordered_mapcan sometimes be a better choice with types that aren't suited tostd::map(because they can't be totally ordered). Feb 10, 2022 at 14:50
std::unordered_mapis a hash table! In contrast,std::mapcorresponds 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 astd::mutex, or (more reasonably) use a third party library.