C++ 中的 map 与 hash_map

map vs. hash_map in C++

提问by skydoor

I have a question with hash_mapand mapin C++. I understand that mapis in STL, but hash_mapis not a standard. What's the difference between the two?

我有一个问题hash_map，并map在C ++中。我知道这map是在 STL 中，但hash_map不是标准。两者有什么区别？

回答by Joe

They are implemented in very different ways.

它们以非常不同的方式实现。

hash_map(unordered_mapin 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.

hash_map（unordered_map在 TR1 和 Boost 中；使用它们代替）使用哈希表，其中键被散列到表中的一个槽中，值存储在与该键相关的列表中。

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

map被实现为平衡二叉搜索树（通常是红/黑树）。

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

Anunordered_map应该为访问集合的已知元素提供稍微更好的性能，但 amap将具有额外的有用特性（例如，它以排序顺序存储，允许从头到尾遍历）。 unordered_map插入和删除会比 a 更快map。

回答by janglin

hash_mapwas a common extension provided by many library implementations. That is exactly why it was renamed to unordered_mapwhen 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_mapand unordered_mapare generally implemented with hash tables. Thus the order is not maintained. unordered_mapinsert/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_mapis 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 mapwould be the choice.

hash_map是许多库实现提供的通用扩展。这正是它在unordered_map作为 TR1 的一部分添加到 C++ 标准时被重命名的原因。map 通常使用平衡二叉树（如红黑树）来实现（当然实现方式各不相同）。 hash_map并且unordered_map通常使用哈希表来实现。因此，不维护订单。 unordered_map插入/删除/查询将是 O(1)（恒定时间），其中 map 将是 O(log n)，其中 n 是数据结构中的项目数。所以unordered_map更快，如果你不关心项目的顺序应该优先于map. 有时您想维护订单（按键排序），这map将是您的选择。

回答by R Samuel Klatchko

Some of the key differences are in the complexity requirements.

一些主要区别在于复杂性要求。

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

• An unordered_maprequires 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 Tabledata structure.

• Amap需要O(log(N))时间进行插入和查找操作，因为它是作为红黑树数据结构实现的。

• Anunordered_map要求O(1)插入和查找的“平均”时间为 ，但允许最坏情况时间为O(N)。这是因为它是使用哈希表数据结构实现的。

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

因此，通常unordered_map会更快，但根据您存储的键和散列函数，可能会变得更糟。

回答by Warren Young

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 mapand 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.

C++ 规范并没有确切说明您必须为 STL 容器使用什么算法。然而，它确实对它们的性能施加了某些限制，这排除了将哈希表用于map其他关联容器。（它们最常使用红/黑树实现。）这些约束要求这些容器具有比哈希表可以提供的更好的最坏情况性能。

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_mapand such to later versions of the C++ standard.

然而，许多人确实想要哈希表，因此基于哈希的 STL 关联容器多年来一直是一个常见的扩展。因此，他们unordered_map在 C++ 标准的后续版本中添加了诸如此类的内容。

回答by Jayhello

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

map是从balanced binary search tree（通常是 a rb_tree）实现的，因为所有成员都已balanced binary search tree排序，因此 map 也是如此；

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

hash_map是从hashtable.Since 中的所有成员实现的，hashtable因此未对中的成员进行hash_map(unordered_map)排序。

hash_mapis 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.

hash_map不是 c++ 标准库，但现在它重命名为unordered_map（你可以认为它重命名）并成为 c++ 标准库，因为 c++11 看到这个问题hash_map 和 unordered_map 之间的区别？了解更多详情。

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 treefunction.

下面的代码只是为了表明， map 只是 an 的包装器balanced binary search tree，几乎所有它的功能都只是调用该balanced binary search tree函数。

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：

hash_mapis implemented from hashtablewhose structure is somewhat like this:

hash_map是从其hashtable结构实现的，有点像这样：

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

在下面的代码中，我将给出 的主要部分hashtable，然后给出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'sonly member is rb_tree, the hash_map'sonly member is hashtable. It's main code as below:

就像map'sonly member is 一样rb_tree，hash_map's唯一的 member is hashtable。它的主要代码如下：

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.

下图显示了当 hash_map 有 53 个桶并插入一些值时，它的内部结构。

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

下图显示了 map 和 hash_map(unordered_map) 之间的一些区别，图片来自如何在 map 和 unordered_map 之间进行选择？：

回答by BoBoDev

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.

我不知道是什么给出了，但是 hash_map 需要超过 20 秒来 clear() 150K 无符号整数键和浮点值。我只是在跑步和阅读别人的代码。

This is how it includes hash_map.

这就是它包含 hash_map 的方式。

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

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

我在这里读到这个 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.

说 clear() 是 O(N) 的顺序。对我来说，这很奇怪，但是，事情就是这样。