STL map, hash_map ， unordered_map区别、对比

约定不等于承诺〃 2022-05-21 06:15 229阅读 0赞

首先：

### `hash_map` ， `unordered_map`比较 ###

具体可见 [stack overflow： Difference between hash\_map and 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?][stackoverflow_How to choose between map and unordered_map]

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

![这里写图片描述][70]

`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_set _ hash_multiset]  
[STL源码剖析-hash\_map / hash\_multimap][STL_-hash_map _ hash_multimap]  
[STL源码剖析-hashtable][STL_-hashtable]

[stack overflow_ Difference between hash_map and unordered_map]: https://stackoverflow.com/a/1646288/6329006
[stackoverflow_How to choose between map and unordered_map]: https://stackoverflow.com/a/13799886/6329006
[70]: /images/20220521/a9dfadf9c9a344afbc1e17725e4758e0.png
[STL_-hash_set _ hash_multiset]: https://blog.csdn.net/haluoluo211/article/details/80877374
[STL_-hash_map _ hash_multimap]: https://blog.csdn.net/haluoluo211/article/details/80877395
[STL_-hashtable]: https://blog.csdn.net/haluoluo211/article/details/80877353