C++的STL库实现有两种字典结构,即map和unordered_map(也就是通俗意义上的hash map)。这两者虽然都称为Map,但其实它们的底层实现原理具有很大差距,因此它们的使用场景也不尽相同。
今天我们就来深入了解一下map和unordered_map区别,及其优缺点。
字典类型又被称为关联数组(associative array),关联数组和正常数组的使用方法是相似的,但其不同之处在于字典结构的下标不必是整数,而可以是任意类型。
map和unordered_map这两种字典结构,都是通过键值对(key-value)存储数据的,键(key)和值(value)的数据类型可以不同。但是字典中的key只能存在一个,即必须唯一(如果不唯一,则被称为multimap)。上述这点保证了值(value)可以直接通过键(key)来访问,这便是字典结构最为便捷之处。
- map: map内部实现了一个红黑树,该结构具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着map的一个元素,因此,对于map进行的查找,删除,添加等一系列的操作都相当于是对红黑树进行这样的操作,故红黑树的效率决定了map的效率。
- unordered_map: unordered_map内部实现了一个哈希表,因此其元素的排列顺序是杂乱的,无序的
①map的常见用法
#include <iostream>
#include <unordered_map>
#include <map>
#include <string>
using namespace std;
int main()
{
//注意:C++11才开始支持括号初始化
unordered_map<int, string> myMap={{ 5, "TOM" },{ 6, "JESON" }};//使用{}赋值
// map<int, string> myMap={{ 5, "张大" },{ 6, "李五" }};//使用{}赋值
myMap[2] = "Ming"; //使用[ ]进行单个插入,若已存在键值2,则赋值修改,若无则插入。
myMap.insert(pair<int, string>(3, "Lily"));//使用insert和pair插入
//遍历输出+迭代器的使用
auto iter = myMap.begin();//auto自动识别为迭代器类型unordered_map<int,string>::iterator
while (iter!= myMap.end())
{
cout << iter->first << "," << iter->second << endl;
++iter;
}
//查找元素并输出+迭代器的使用
auto iterator = myMap.find(2);//find()返回一个指向2的迭代器
if (iterator != myMap.end())
cout << endl<< iterator->first << "," << iterator->second << endl;
system("pause");
return 0;
}
使用unordered_map输出情况为:
3,Lily
2,Ming
5,TOM
6,JESON
2,Ming
若将unordered_map换成map输出情况为:
2,Ming
3,Lily
5,TOM
6,JESON
2,Ming
使用方法是最直观的区别,这两种结构虽然都在STL库中,但是所使用的头文件不同。
-
map:#include
-
unordered_map:#include <unordered_map>
数据结构其实是两种类型最为根本的区别,其他的不同都是这种区别产生的结果。
-
map是基于红黑树结构实现的。红黑树是一种平衡二叉查找树的变体结构,它的左右子树的高度差有可能会大于 1。所以红黑树不是严格意义上的平衡二叉树AVL,但对之进行平衡的代价相对于AVL较低, 其平均统计性能要强于AVL。红黑树具有自动排序的功能,因此它使得map也具有按键(key)排序的功能,因此在map中的元素排列都是有序的。在map中,红黑树的每个节点就代表一个元素,因此实现对map的增删改查,也就是相当于对红黑树的操作。对于这些操作的复杂度都为O(logn),复杂度即为红黑树的高度。
-
unordered_map是基于哈希表(也叫散列表)实现的。散列表是根据关键码值而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。散列表使得unordered_map的插入和查询速度接近于O(1)(在没有冲突的情况下),但是其内部元素的排列顺序是无序的。
在2中已经解释过了,现在单独列出该点不同之处。
-
map:基于红黑树,元素有序存储
-
unordered_map:基于散列表,元素无序存储
这点也已经在2中已经解释过了,现在单独列出该点不同。
-
map:基于红黑树,复杂度与树高相同,即O(logn)。
-
unordered_map:基于散列表,复杂度依赖于散列函数产生的冲突多少,但大多数情况下其复杂度接近于O(1)。
这点实际上也是由底层的数据结构决定的。
- 存储空间:unordered_map的散列空间会存在部分未被使用的位置,所以其内存效率不是100%的。而map的红黑树的内存效率接近于100%。
- 查找性能的稳定性:map的查找类似于平衡二叉树的查找,其性能十分稳定。例如在1M数据中查找一个元素,需要多少次比较呢?20次。map的查找次数几乎与存储数据的分布与大小无关。而unordered_map依赖于散列表,如果哈希函数映射的关键码出现的冲突过多,则最坏时间复杂度可以达到是O(n)。因此unordered_map的查找次数是与存储数据的分布与大小有密切关系的,它的效率是不稳定的。
-
- 优点:
- 有序性:map元素有序(这是map最大的优点,其元素的有序性在很多应用中都会简化很多的操作);
- 红黑树:其红黑树的结构使得map的很多操作都可在O(logn)下完成,因此效率非常的高;
- map的各项性能较为稳定,与元素插入顺序无关;,
- map支持范围查找。
- 缺点:
- 空间占用率高:即占用的空间大,因为红黑树的每一个节点需要保存其父节点位置、孩子节点位置及红/黑性质,因此每一个节点占用空间大。
- 查询平均时间不如unordered_map。
- 适用场景:
- 元素需要有序;
- 对于那些有顺序要求的问题,用map会更高效一些
- 对于单次查询时间较为敏感,必须保持查询性能的稳定性,比如实时应用等等。
- 优点:
-
- 优点:
- 哈希表:内部实现了哈希表,因此查询速度快,平均性能接近于常数时间O(1);
- 缺点:
- 元素无序;
- unordered_map相对于map空间占用更大,且其利用率不高;
- 查询性能不太稳定,哈希表的建立较为耗时,最坏时间复杂度可达到O(n)。
- 适用场景:
- 对于查找问题更擅长,若要求查找速率快,且对单次查询性能要求不敏感,则可选unordered_map。
- 优点:
最后一句话,总结一下它们的适用场景:
**在需要元素有序性或者对单次查询性能要求较为敏感时,请使用map,其余情况下应使用unordered_map。**因此,可理解为在需要使用字典结构进行算法编程的大部分情况下,都需要使用unordered_map
而不是map
。
map和unordered_map并无好坏之分,它们各自擅长的应用场景不通。它们之间的区别归根结底来源于使用的数据结构不同。
参考博文: