STL map, hash_map ， unordered_map区别、对比

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1338322

首先：

hash_map ， unordered_map比较

具体可见 stack overflow： Difference between hash_map and unordered_map?

由于在C++标准库中没有定义散列表hash_map，标准库的不同实现者将提供一个通常名为hash_map的非标准散列表。因为这些实现不是遵循标准编写的，所以它们在功能和性能保证上都有微妙的差别。

从C++11开始，哈希表实现已添加到C++标准库标准。决定对类使用备用名称，以防止与这些非标准实现的冲突，并防止在其代码中有hash_table的开发人员无意中使用新类。

所选择的备用名称是unordered_map，它更具描述性，因为它暗示了类的映射接口和其元素的无序性质。

可见hash_map ， unordered_map本质是一样的，只不过 unordered_map被纳入了C++标准库标准。

map vs unordered_map

比较好的对比见：stackoverflow：How to choose between map and unordered_map?

主要是，查询、插入、删除的时间复杂度三个方面：

unordered_map(等价于hash_map)和map类似，都是存储的key-value的值，可以通过key快速索引到value。不同的是unordered_map不会根据key的大小进行排序，

1. map 内部数据的组织，基于红黑树实现，红黑树具有自动排序的功能，因此map内部所有的数据，在任何时候，都是有序的。
2. unordered_map(hash_map) 基于哈希表，数据插入和查找的时间复杂度很低，几乎是常数时间，而代价是消耗比较多的内存。底层实现上，使用一个下标范围比较大的数组来存储元素，形成很多的桶，利用hash函数对key进行映射到不同区域进行保存。

可以见STL源码剖析：

STL源码剖析-hash_set / hash_multiset

STL源码剖析-hash_map / hash_multimap

STL源码剖析-hashtable