STL—map、hash_map、unordered_map

时间:2020-12-21 18:51:07

1.基本定义


  map底层是用红黑树实现的,查找时间复杂度是O(log(n));

  hash_map底层是用hash表存储的,查询时间复杂度是O(1);

  unordered_map和hash_map基本一样,只是unordered_map已经加到C++11标准(编译时添加编译选项:--std=c++11),而hash_map未加入在C++11标准中。

  由于map使用红黑树实现,所以是有序存储的,因此map的key需要定义operator<,而hash_map和unordered_map是基于hash无序存储的,因此只需要重载operator==。

2.hash_map、unordered_map


  hash_map基于哈希表,因此数据插入和查找的时间复杂度几乎是常数时间,而代价是消耗比较多的内存。底层实现上,使用一个下标范围比较大的数组来存储元素,形成很多的桶,利用hash函数对key进行映射到不同区域进行保存。

    插入操作:使用key通过hash函数得到hash值 -> 得到桶号(hash值对桶数求模) -> 存放key和value在桶内

    取值过程:使用key通过hash函数得到hash值 -> 得到桶号(hash值对桶数求模) -> 比较桶内元素与key是否相等 -> 取出相等纪录的value

  因此hash_map和用户相关的是:hash函数和比较函数,这两个参数刚好是我们在使用hash_map时需要指定的参数。如果每个桶内部只有一个元素,那么查找的时候只有一次比较,因此查询时间复杂度是O(1)。

  在容器中不包含key值时,insert函数只要立刻插入新节点。但是当容器中元素增多,每个桶中的元素会增加,为了保证效率, hash_map会自动申请更大的内存,以生成更多的桶,因此在insert以后,以前的iterator有可能是不可用的。

  【1】hash_map桶的扩容机制

    扩容时需要满足两个条件:存放新值的时候当前hash_map所有元素的个数大于等于阈值;存放新值的时候当前存放数据发生hash碰撞。

    STL会默认指定初始桶大小为16,负载因子是0.75,因此阈值就是16*0.75 = 12,所以当新插入元素时,当前的元素个数超过12,并且发生了冲突,就会扩容hash桶。扩容的大小是给之前的数组翻倍。

    在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。 所以如果已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能,例如最多有1000个元素,则创建时:new HashMap(2048)(1024是不够的,要考虑负载因子:1024*0.75 = 768)。

    另外桶的大小为2的幂次方时,hash_map的效率最高。这是因为:正常的取index方法为hash%length,但是由于位运算比取余快,所以代码中实现为index = hash & (length - 1),所以只有length大小为2的次幂时:hash % length == hash & (length - 1)。

3.用法


  总体来说,hash_map 查找速度会比map快,属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小, 因为hash函数计算也需要耗时,如果在元素达到一定数量级时同时要考虑效率,此时应该使用hash_map。如果对内存使用特别严格,需要程序尽可能少消耗内存,那么应该是用map,因为hash_map占用内存较多。