C++中map、hash_map、unordered_map、unordered_set通俗辨析

爱被打了一巴掌 2022-08-22 05:53 124阅读 0赞

http://blog.csdn.net/u013195320/article/details/23046305

标题中提到的四种容器，对于概念不清的人来说，经常容易弄混淆。这里我不去把库里面复杂的原码拿出剖析，这个如果有兴趣其实完全可以查C++Reference,网上的原码是最权威和细致的了，而且我觉得有耐心直接认真看原码的人，也不需要我这篇速记博文了，所以我这里还是讲的通俗一些，把它们区分的七七八八。

一、hash\_map、unordered\_map

这两个的内部结构都是采用哈希表来实现。区别在哪里？unordered\_map在C++11的时候被引入标准库了，而hash\_map没有，所以建议还是使用unordered\_map比较好。

哈希表的好处是什么？查询平均时间是O(1)。顾名思义，unordered，就是无序了，数据是按散列函数插入到槽里面去的，数据之间无顺序可言，但是有些时候我只要访问而不需要顺序，因此可以选择哈希表。举个最好的例子，就是我的LeetCode的博文里------Longest Consecutive Sequence这一题，我的方法二就是用的unordered\_map来实现“空间弥补时间”这样的做法。

二、unordered\_map与map

虽然都是map，但是内部结构大大的不同哎，map的内部结构是R-B-tree来实现的，所以保证了一个稳定的动态操作时间，查询、插入、删除都是O（logN），最坏和平均都是。而unordered\_map如前所述，是哈希表。顺便提一下，哈希表的查询时间虽然是O（1），但是并不是unordered\_map查询时间一定比map短，因为实际情况中还要考虑到数据量，而且unordered\_map的hash函数的构造速度也没那么快，所以不能一概而论，应该具体情况具体分析。

三、unordered\_map与unordered\_set

后者就是在哈希表插入value，而这个value就是它自己的key，而不是像之前的unordered\_map那样有键-值对，这里单纯就是为了方便查询这些值。我在Longest Consecutive Sequence这一题，我的方法一就是用了unordered\_set，同样是一个将空间弥补时间的方法。再举个大家好懂的例子，给你A,B两组数，由整数组成，然后把B中在A中出现的数字取出来，要求用线性时间完成。很明显，这道题应该将A的数放到一个表格，然后线性扫描B，发现存在的就取出。可是A的范围太大，你不可能做一个包含所有整数的表，因为这个域太大了，所以我们就用unordered\_set来存放A的数，具体实现库函数已经帮你搞定了，如果对于具体怎么去散列的同学又兴趣可以查看《算法导论》的第11章或者《数据结构与算法分析》的第五章，如果要看《算法导论》的同学我给个建议，完全散列你第一遍的时候可以暂时跳过不看，确实有点复杂。