概述

unordered_map, hash_map, map

  1. unordered_map 和 map 类似, 都是存储 key-value, 可以通过 key 快速索引到value.按照查找效率排名: unordered_map > hash_map > map.

unordered_map 与 map 区别:

  1. unordered_map 内部元素是无序的,不会根据 key 的大小进行排序,存储时是根据 key 的hash 值判断元素是否相同.而 map 中的元素是按照二叉搜索树存储的,进行中序遍历会得到有序遍历.
  2. 需要引入的头文件不同:
    1. map: #include
    2. unordered_map: #include<unordered_map>
  3. 内部实现机理不同:
    1. map: map内部实现了一个红黑树(红黑树是非严格平衡二叉搜索树,而AVL是严格平衡二叉搜索树),红黑树具有自动排序的功能,因此map内部的所有元素都是有序的,红黑树的每一个节点都代表着 map 的一个元素.因此,对于 map 进行的查找,删除,添加等一系列的操作都相当于是对红黑树进行的操作. map 中的元素是按照二叉搜索树(又名二叉查找树,二叉排序树,特点就是左子树上所有节点的键值都小于根节点的键值,右子树所有节点的键值都大于根节点的键值)存储的,使用中序遍历可将键值按照从小到大遍历出来.
    2. unordered_map: unordered_map 内部实现了一个哈希表(也叫散列表,通过把关键码值映射到 Hash 表中一个位置来访问记录,查找的时间复杂度可达到 O(1),其在海量数据处理中有着广泛应用).因此,其元素的排列顺序是无序的.
  4. 优缺点以及适用处:
    1. map 优点: 
      1. 有序性,这是map结构最大的优点,其元素的有序性在很多应用中都会简化很多的操作.
      2. 红黑树,内部实现一个红黑树使得map的很多操作在lgn的时间复杂度下就可以实现,因此效率非常的高.
    2. 缺点: 空间占用率高,因为map内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点,孩子节点,使得每一个节点都占用大量的空间.
    3. 适用处: 对于那些有顺序要求的问题,用 map 会更高效一些.
  5. unordered_map:
    1. 优点: 因为内部实现了哈希表,因此其查找速度非常的快.
    2. 缺点: 哈希表的建立比较耗费时间.
    3. 适用处: 对于查找问题,unordered_map 会更加高效一些,因此遇到查找问题,常会考虑一下用 unordered_map.