Why std::map is red black tree and not hash table ?

Question

This is very strange for me, i expected it to be a hash table.

I saw 3 reasons in the following answer (which maybe correct but i don't think that they are the real reason). Hash tables v self-balancing search trees

1. Although hash might be not a trivial operation. I think that for most of the types it is pretty simple.

2. when you use map you expect something that will give you amortized O(1) insert, delete, find , not log(n).

3. i agree that trees have better worst case performance.

I think that there is a bigger reason for that, but i can't figure it out. In c# for example Dictionary is a hash table.

Answer 1

It's largely a historical accident. The standard containers (along with iterators and algorithms) were one of the very last additions before the feature set of the standard was frozen. As it happened, they didn't have what they considered an adequate definition of a hash-based map at the time, and there wasn't time to add it before features were frozen, so the original specification included only a tree-based map.

C++ 11 added std::unordered_map (as well as std::unordered_set and multi versions of both), which is based on hashing though.

Answer 2

The reason is that map is explicitly called out as an ordered container. It keeps the elements sorted and allows you to iterate in sorted order in linear time. A hashtable couldn't fulfill those requirements.

In C++11 they added std::unordered_map which is a hashtable implementation.

Answer 3

A hash table requires an additional hash function. The current implementation of map which uses a tree can work without an extra hash function by using operator<. Additionally the map allows sorted access to elements, which may be beneficial for some applications. With C++ we now have the hash versions available in form of unordered_set.

Answer 4

Simple answer: because a hash table cannot satisfy the complexity requirements of iteration over a std::map.

Why does std::map hold these requirements? Unanswerable question. Historical factors contribute but, overall, that's just the way it is.

Hashes are available as std::unordered_map.

It doesn't really matter what the two are called, or what they're called in some other language.