map vs. hash_map in C++

Question

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?

Solution 1

They are implemented in very different ways.

hash_map (unordered_map in TR1 and Boost; use those instead) use a hash table where the key is hashed to a slot in the table and the value is stored in a list tied to that key.

map is implemented as a balanced binary search tree (usually a red/black tree).

An unordered_map should give slightly better performance for accessing known elements of the collection, but a map will have additional useful characteristics (e.g. it is stored in sorted order, which allows traversal from start to finish). unordered_map will be faster on insert and delete than a map.

Solution 2

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.

Solution 3

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.

Solution 4

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?:

Solution 5

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.

View more solutions

Comments

[Terry Mahaffey]

It was actually added in TR1 (std::tr1::unordered_map), not C++0x

[KitsuneYMG]

I would point out that hashmap has a worst case access of O(N) when collisions are likely (bad hash fcn, loading factor too high, etc)

[KitsuneYMG]

I thought that the reason map is generally a balanced btree was due to using operator<() as the means of determining location.

[bk1e]

@kts: Do any STL implementations actually use a B-tree?

[Matthieu M.]

I don't fully agree with you regarding the performance. The performance is influenced by a number of parameters and I would scold any programmer using an unordered_map for a mere 10 entries because "It's faster". Worry about interface / functionality first, performance later.

[KitsuneYMG]

Technically all binary search trees are b-trees (a 1-2 tree). That being said, I don't know of any STL that uses anything other than red/black

[Joe]

Well, yes, it helps if you understand your problem. Up to certain orders of magnitude it is probably a wash performance-wise, but it is important to understand the performance characteristics of both containers as they do deviate in different ways as data volumes get larger.

[Erik Garrison]

Interestingly, I just swapped a std::map with a boost::unordered_map in an application in which I do a lot of random lookups, but also iterate over all the keys in the map. I saved a large amount of time in lookup, but gained it back via the iterations, so I switched back to map and am looking for other ways to improve application performance.

[Branko Dimitrijevic]

@bk1e "Proper" B-trees are exceptionally useful in databases, where you want "fat" tree nodes that align well with disk pages. OTOH, this is not so useful in the "flat" memory model used in "normal" programs - all STL implementations I know of use red-black trees.

[Clearer]

A good hashmap has an expected cost of O(1), it is not guaranteed to be so. Bad hashmaps might have an expected cost that's not O(1).

[sprite]

@ErikGarrison If you use random access and iteration a lot more than you insert and delete elements, you could have your objects in both a tree and a hash_map (by storing a pointer, or better yet a shared_ptr, to the same objects in both in case you were using actual instances). You will then have O(1) time access time through the hash_map and O(n) iteration time through the map. Of course, you have to remember to add and remove the pointers from both every time. You could easily write a custom container class that (probably template it as well) that would encapsulate this behavior for you.

[sprite]

@ErikGarrison Of course, if you try this method, you would be paying with a minor additional space. However, since you'd be using pointers, that shouldn't be too much. If you really want to, you can go overboard, and write your own implementation of an AVL and use the node pointer as your data type in the hash_map, this will give you O(1) time access to a node in the tree from which you'll be able to iterate linearly to wherever you need. Of course this would involve quite a bit of coding and I'm not sure it would pay off unless you need to iterate a lot from and to random access locations.