[c++] map vs. hash_map in C++

I have a question with hash_map and map in C++. I understand that map is in STL, but hash_map is not a standard. What's the difference between the two?

The C++ spec doesn't say exactly what algorithm you must use for the STL containers. It does, however, put certain constraints on their performance, which rules out the use of hash tables for map and other associative containers. (They're most commonly implemented with red/black trees.) These constraints require better worst-case performance for these containers than hash tables can deliver.

Many people really do want hash tables, however, so hash-based STL associative containers have been a common extension for years. Consequently, they added unordered_map and such to later versions of the C++ standard.

hash_map was a common extension provided by many library implementations. That is exactly why it was renamed to unordered_map when it was added to the C++ standard as part of TR1. map is generally implemented with a balanced binary tree like a red-black tree (implementations vary of course). hash_map and unordered_map are generally implemented with hash tables. Thus the order is not maintained. unordered_map insert/delete/query will be O(1) (constant time) where map will be O(log n) where n is the number of items in the data structure. So unordered_map is faster, and if you don't care about the order of the items should be preferred over map. Sometimes you want to maintain order (ordered by the key) and for that map would be the choice.

I don't know what gives, but, hash_map takes more than 20 seconds to clear() 150K unsigned integer keys and float values. I am just running and reading someone else's code.

This is how it includes hash_map.

#include "StdAfx.h"
#include <hash_map>

I read this here https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap

saying that clear() is order of O(N). That to me, is very strange, but, that's the way it is.

Some of the key differences are in the complexity requirements.

• A map requires O(log(N)) time for inserts and finds operations, as it's implemented as a Red-Black Tree data structure.

• An unordered_map requires an 'average' time of O(1) for inserts and finds, but is allowed to have a worst-case time of O(N). This is because it's implemented using Hash Table data structure.

So, usually, unordered_map will be faster, but depending on the keys and the hash function you store, can become much worse.

map is implemented from balanced binary search tree(usually a rb_tree), since all the member in balanced binary search tree is sorted so is map;

hash_map is implemented from hashtable.Since all the member in hashtable is unsorted so the members in hash_map(unordered_map) is not sorted.

hash_map is not a c++ standard library, but now it renamed to unordered_map(you can think of it renamed) and becomes c++ standard library since c++11 see this question Difference between hash_map and unordered_map? for more detail.

Below i will give some core interface from source code of how the two type map is implemented.

map:

The below code is just to show that, map is just a wrapper of an balanced binary search tree, almost all it's function is just invoke the balanced binary search tree function.

template <typename Key, typename Value, class Compare = std::less<Key>>
class map{
    // used for rb_tree to sort
    typedef Key    key_type;

    // rb_tree node value
    typedef std::pair<key_type, value_type> value_type;

    typedef Compare key_compare;

    // as to map, Key is used for sort, Value used for store value
    typedef rb_tree<key_type, value_type, key_compare> rep_type;

    // the only member value of map (it's  rb_tree)
    rep_type t;
};

// one construct function
template<typename InputIterator>
map(InputIterator first, InputIterator last):t(Compare()){
        // use rb_tree to insert value(just insert unique value)
        t.insert_unique(first, last);
}

// insert function, just use tb_tree insert_unique function
//and only insert unique value
//rb_tree insertion time is : log(n)+rebalance
// so map's  insertion time is also : log(n)+rebalance 
typedef typename rep_type::const_iterator iterator;
std::pair<iterator, bool> insert(const value_type& v){
    return t.insert_unique(v);
};

hash_map:

hash_map is implemented from hashtable whose structure is somewhat like this:

In the below code, i will give the main part of hashtable, and then gives hash_map.

// used for node list
template<typename T>
struct __hashtable_node{
    T val;
    __hashtable_node* next;
};

template<typename Key, typename Value, typename HashFun>
class hashtable{
    public:
        typedef size_t   size_type;
        typedef HashFun  hasher;
        typedef Value    value_type;
        typedef Key      key_type;
    public:
        typedef __hashtable_node<value_type> node;

        // member data is buckets array(node* array)
        std::vector<node*> buckets;
        size_type num_elements;

        public:
            // insert only unique value
            std::pair<iterator, bool> insert_unique(const value_type& obj);

};

Like map's only member is rb_tree, the hash_map's only member is hashtable. It's main code as below:

template<typename Key, typename Value, class HashFun = std::hash<Key>>
class hash_map{
    private:
        typedef hashtable<Key, Value, HashFun> ht;

        // member data is hash_table
        ht rep;

    public:
        // 100 buckets by default
        // it may not be 100(in this just for simplify)
        hash_map():rep(100){};

        // like the above map's insert function just invoke rb_tree unique function
        // hash_map, insert function just invoke hashtable's unique insert function
        std::pair<iterator, bool> insert(const Value& v){
                return t.insert_unique(v);
        };

};

Below image shows when a hash_map have 53 buckets, and insert some values, it's internal structure.

The below image shows some difference between map and hash_map(unordered_map), the image comes from How to choose between map and unordered_map?: