Consider the following:
In C++, the std::unordered_map uses a hash function in the insertion process to determine where the new inserted element will be located.
However, the std::map does not use a hash function in the insertion process and determines the location of the new inserted element using the same method that is used to determine the location of the new inserted element in any binary search tree. By this, I mean the method by which the location of the new element is determined in any binary search tree is for example, if the element is greater than the current element then go right, or if it is less than the current element then go left.
Is my conclusion 100% accurate?
std::map has a type parameter Compare that is required to provide an ordering to the keys of the map, and also determine when keys are equivalent by the relation equiv(a, b) iff !comp(a, b) && !comp(b, a)
std::unordered_map has a type parameter Hash that is required to provide a hashing of the keys of the map. It also has a type parameter Equal that is required to determine equivalence between keys, in a manner consistent with Hash, i.e. hash(a) == hash(b) if equal(a, b).
These requirements, and the complexity requirements on certain member functions, mean that whilst there is theoretically room for implementations to do things with a different data structure, to be conforming std::map has to be a balanced binary tree, and std::unordered_map has to be a hash table with chaining