C++ Binary Search Tree vs Hashmap – Historical Reasons and Simplicity

algorithmscdata structures

Looking at the two data structures and algorithms to handle them, a hashmap is not really any more complicated than a binary search tree and possibly less complicated. And the hashmap has the advantage of constant time access of a key. So why did we get a std::map very early on in the history of the standard library but for std::unordered_map which is a hashmap we had to wait for C++11 ?

Best Answer

Implementing a hashmap is much more complicated, not in actual implementation but in the possible variants you have to pick from:

  • open addressing vs. separate chaining,
    • whether the nodes in separate chaining holds one or more items,
  • the hash function,
  • growth factor,
  • whether to keep key and value together,

All of those affect performance in a way where it's not easy to say which one is better in general.

Compared to that the red-black tree is much simpler to create a prototype for that people won't bikeshed endlessly about.

Related Topic