blocks|key|1340430|text|C%2B%2B规范并没有明确说明您必须为STL容器使用什么算法。然而，它确实对它们的性能施加了某些约束，这排除了对map和其他关联容器使用哈希表的可能性。(它们通常是用红/黑树实现的。)这些约束要求这些容器比哈希表提供更好的最坏情况下的性能。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1340431|然而，许多人确实想要哈希表，所以基于哈希的STL关联容器多年来一直是一个常见的扩展。因此，他们在C%2B%2B标准的较新版本中添加了unordered_map等。|1340432|entityMap^0|1H|3|0|1Q|D|0^^$0|@$1|2|3|4|5|6|7|J|8|@$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|M|8|@$9|N|A|O|B|C]]|D|@]|E|$]]|$1|H|3|-4|5|6|7|P|8|@]|D|@]|E|$]]]|I|$]]

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 <code>map</code> 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 <code>unordered_map</code> and such to later versions of the C++ standard.

blocks|key|1125387|text|它们以非常不同的方式实现。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1125388|hash_map+(+TR1和Boost中的unordered_map；改为使用它们)使用哈希表，其中键被散列到表中的一个槽，值存储在与该键绑定的列表中。|offset|length|style|CODE|1125389|map被实现为平衡的二进制搜索树(通常是红/黑树)。|1125390|对于访问集合的已知元素，unordered_map应该会提供稍微好一点的性能，但map将具有其他有用的特征(例如，它以排序的顺序存储，这允许从头到尾进行遍历)。在insert和delete方面，unordered_map比map更快。|1125391|entityMap^0|0|0|8|M|D|0|0|3|0|C|D|14|3|2P|D|33|3|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@$D|P|E|Q|F|G]|$D|R|E|S|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|T|8|@$D|U|E|V|F|G]]|9|@]|A|$]]|$1|J|3|K|5|6|7|W|8|@$D|X|E|Y|F|G]|$D|Z|E|10|F|G]|$D|11|E|12|F|G]|$D|13|E|14|F|G]]|9|@]|A|$]]|$1|L|3|-4|5|6|7|15|8|@]|9|@]|A|$]]]|M|$]]

They are implemented in very different ways.

<code>hash_map</code> (<code>unordered_map</code> 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.

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

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

blocks|key|1340533|text|hash_map是许多库实现提供的通用扩展。这正是将其作为TR1的一部分添加到C%2B%2B标准中时将其重命名为unordered_map的原因。map通常使用像红黑树这样的平衡二叉树来实现(当然，实现方式各不相同)。hash_map和unordered_map通常使用哈希表实现。因此，该顺序不会被维持。unordered_map插入/删除/查询将是O(1)+(恒定时间)，其中map将是O(log+)，其中n是数据结构中的项数。所以unordered_map更快，如果你不关心项目的顺序，应该比map更好。有时，您希望维护顺序(按键排序)，为此，map将是一个选择。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1340534|entityMap^0|0|8|1G|D|2X|8|36|D|45|D|5Y|D|6T|3|7J|3|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]|$9|M|A|N|B|C]|$9|O|A|P|B|C]|$9|Q|A|R|B|C]|$9|S|A|T|B|C]|$9|U|A|V|B|C]|$9|W|A|X|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|Y|8|@]|D|@]|E|$]]]|G|$]]

<code>hash_map</code> was a common extension provided by many library implementations. That is exactly why it was renamed to <code>unordered_map</code> 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). <code>hash_map</code> and <code>unordered_map</code> are generally implemented with hash tables. Thus the order is not maintained. <code>unordered_map</code> 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 <code>unordered_map</code> is faster, and if you don't care about the order of the items should be preferred over <code>map</code>. Sometimes you want to maintain order (ordered by the key) and for that <code>map</code> would be the choice.

blocks|key|1340586|text|我不知道是什么原因，但是，hash_map需要超过20秒的时间来清除()15万个无符号整数键和浮点值。我只是在运行和读取别人的代码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1340587|这就是它包含hash_map的方式。|1340588|#include+"StdAfx.h"
#include+<hash_map>|code-block|syntax|javascript|1340589|我在这里读到了这个https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap|offset|length|1340590|说明clear()是O(N)的阶数。对我来说，这很奇怪，但事实就是这样。|1340591|entityMap|0|LINK|mutability|MUTABLE|url|https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap^0|0|0|0|9|1T|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@$K|10|L|11|1|12]]|A|$]]|$1|M|3|N|5|6|7|13|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|14|8|@]|9|@]|A|$]]]|P|$Q|$5|R|S|T|A|$U|V]]]]

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.

<pre><code>#include "StdAfx.h"
#include &lt;hash_map&gt;
</code></pre>

I read this here
<a href="https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap" rel="nofollow noreferrer">https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap</a>

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

blocks|key|1125681|text|map是从balanced+binary+search+tree(通常是rb_tree)实现的，因为balanced+binary+search+tree中的所有成员都是排序的，映射也是排序的；|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1125682|hash_map是从hashtable.Since实现的，hashtable中的所有成员都是未排序的，因此hash_map(unordered_map)中的成员也没有排序。|1125683|hash_map不是一个c%2B%2B标准库，但现在它重命名为unordered_map(您可以将其重命名)，并成为c%2B%2B标准库，因为c%2B%2B11请参阅此问题Difference+between+hash_map+and+unordered_map?以获取更多详细信息。|1125684|下面我将从源代码中给出两种类型映射如何实现的一些核心接口。|1125685|映射：|1125686|下面的代码只是为了说明，map只是一个balanced+binary+search+tree的包装器，它的几乎所有功能都只是调用balanced+binary+search+tree函数。|1125687|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)%2Brebalance
//+so+map's++insertion+time+is+also+:+log(n)%2Brebalance+
typedef+typename+rep_type::const_iterator+iterator;
std::pair<iterator,+bool>+insert(const+value_type&+v){
++++return+t.insert_unique(v);
};|code-block|syntax|javascript|1125688|hash_map|1125689|hash_map是从hashtable实现的，它的结构有点像这样：|1125690|​|1125691|📷|atomic|1125692|1125693|在下面的代码中，我将给出hashtable的主要部分，然后给出hash_map。|1125694|//+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);

};|1125695|与map's一样，唯一的成员是rb_tree，唯一的hash_map's成员是hashtable。主要代码如下：|1125696|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);
++++++++};

};|1125697|下图显示了当一个hash_map有53个存储桶并插入一些值时，它的内部结构。|1125698|1125699|1125700|1125701|下图显示了来自How+to+choose+between+map+and+unordered_map?的map和hash_map(unordered_map)之间的一些差异|1125702|1125703|1125704|1125705|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/1646288/6329006|1|IMAGE|IMMUTABLE|imageUrl|https://ask.qcloudimg.com/http-save/yehe-900000/b7d4e9673da60f8826659dcfcbe3f506.png|imageAlt|2|https://ask.qcloudimg.com/http-save/yehe-900000/c519002b4c2e4b9b1ddc79666a1b07aa.png|3|https://stackoverflow.com/a/13799886/6329006|4|https://ask.qcloudimg.com/http-save/yehe-900000/2af0aba785963625f8f39bc9064bbb69.png^0|0|3|5|R|10|7|1E|R|0|0|8|A|9|T|9|1H|N|0|0|8|R|D|22|1A|0|0|0|0|J|R|1S|R|0|0|0|8|0|0|8|A|9|0|0|0|1|1|0|0|C|9|V|8|0|0|1|5|F|7|Q|A|13|9|0|0|0|0|0|1|2|0|0|7|18|3|0|0|0|1|4|0|0^^$0|@$1|2|3|4|5|6|7|26|8|@$9|27|A|28|B|C]|$9|29|A|2A|B|C]|$9|2B|A|2C|B|C]|$9|2D|A|2E|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|2F|8|@$9|2G|A|2H|B|C]|$9|2I|A|2J|B|C]|$9|2K|A|2L|B|C]|$9|2M|A|2N|B|C]]|D|@]|E|$]]|$1|H|3|I|5|6|7|2O|8|@$9|2P|A|2Q|B|C]|$9|2R|A|2S|B|C]]|D|@$9|2T|A|2U|1|2V]]|E|$]]|$1|J|3|K|5|6|7|2W|8|@]|D|@]|E|$]]|$1|L|3|M|5|6|7|2X|8|@]|D|@]|E|$]]|$1|N|3|O|5|6|7|2Y|8|@$9|2Z|A|30|B|C]|$9|31|A|32|B|C]]|D|@]|E|$]]|$1|P|3|Q|5|R|7|33|8|@]|D|@]|E|$S|T]]|$1|U|3|V|5|6|7|34|8|@$9|35|A|36|B|C]]|D|@]|E|$]]|$1|W|3|X|5|6|7|37|8|@$9|38|A|39|B|C]|$9|3A|A|3B|B|C]]|D|@]|E|$]]|$1|Y|3|Z|5|6|7|3C|8|@]|D|@]|E|$]]|$1|10|3|11|5|12|7|3D|8|@]|D|@$9|3E|A|3F|1|3G]]|E|$]]|$1|13|3|Z|5|6|7|3H|8|@]|D|@]|E|$]]|$1|14|3|15|5|6|7|3I|8|@$9|3J|A|3K|B|C]|$9|3L|A|3M|B|C]]|D|@]|E|$]]|$1|16|3|17|5|R|7|3N|8|@]|D|@]|E|$S|T]]|$1|18|3|19|5|6|7|3O|8|@$9|3P|A|3Q|B|C]|$9|3R|A|3S|B|C]|$9|3T|A|3U|B|C]|$9|3V|A|3W|B|C]]|D|@]|E|$]]|$1|1A|3|1B|5|R|7|3X|8|@]|D|@]|E|$S|T]]|$1|1C|3|1D|5|6|7|3Y|8|@]|D|@]|E|$]]|$1|1E|3|Z|5|6|7|3Z|8|@]|D|@]|E|$]]|$1|1F|3|11|5|12|7|40|8|@]|D|@$9|41|A|42|1|43]]|E|$]]|$1|1G|3|Z|5|6|7|44|8|@]|D|@]|E|$]]|$1|1H|3|1I|5|6|7|45|8|@]|D|@$9|46|A|47|1|48]]|E|$]]|$1|1J|3|Z|5|6|7|49|8|@]|D|@]|E|$]]|$1|1K|3|11|5|12|7|4A|8|@]|D|@$9|4B|A|4C|1|4D]]|E|$]]|$1|1L|3|Z|5|6|7|4E|8|@]|D|@]|E|$]]|$1|1M|3|-4|5|6|7|4F|8|@]|D|@]|E|$]]]|1N|$1O|$5|1P|1Q|1R|E|$1S|1T]]|1U|$5|1V|1Q|1W|E|$1X|1Y|1Z|-4]]|20|$5|1V|1Q|1W|E|$1X|21|1Z|-4]]|22|$5|1P|1Q|1R|E|$1S|23]]|24|$5|1V|1Q|1W|E|$1X|25|1Z|-4]]]]

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

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

<code>hash_map</code> is not a c++ standard library, but now it renamed to <code>unordered_map</code>(you can think of it renamed) and becomes c++ standard library since c++11 see this question <a href="https://stackoverflow.com/a/1646288/6329006">Difference between hash_map and unordered_map?</a> for more detail. 

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

<h3>map:</h3>

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

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

 // rb_tree node value
 typedef std::pair&lt;key_type, value_type&gt; value_type;

 typedef Compare key_compare;

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

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

// one construct function
template&lt;typename InputIterator&gt;
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&lt;iterator, bool&gt; insert(const value_type&amp; v){
 return t.insert_unique(v);
};
</code></pre>

<h3><code>hash_map</code>:</h3>

<code>hash_map</code> is implemented from <code>hashtable</code> whose structure is somewhat like this:

<a href="https://i.stack.imgur.com/4iKV0.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/4iKV0.png" alt="enter image description here"></a>

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

<pre><code>// used for node list
template&lt;typename T&gt;
struct __hashtable_node{
 T val;
 __hashtable_node* next;
};

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

 // member data is buckets array(node* array)
 std::vector&lt;node*&gt; buckets;
 size_type num_elements;

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

};
</code></pre>

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

<pre><code>template&lt;typename Key, typename Value, class HashFun = std::hash&lt;Key&gt;&gt;
class hash_map{
 private:
 typedef hashtable&lt;Key, Value, HashFun&gt; 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&lt;iterator, bool&gt; insert(const Value&amp; v){
 return t.insert_unique(v);
 };

};
</code></pre>

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

<a href="https://i.stack.imgur.com/8tvEu.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/8tvEu.png" alt="enter image description here"></a>

The below image shows some difference between map and hash_map(unordered_map), the image comes from <a href="https://stackoverflow.com/a/13799886/6329006">How to choose between map and unordered_map?</a>:

<a href="https://i.stack.imgur.com/XWzYW.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/XWzYW.png" alt="enter image description here"></a>

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

map vs. hash_map in C++

数据结构

容器

我有个问题要问C++的hash_map和map。我知道map是用标准语言编写的，但是hash_map不是标准。这两者有什么不同？

问C++中的map与hash_map
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问C++中的map与hash_mapEN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问C++中的map与hash_map
EN