map底层、unorder_map底层，二者区别，为什么这样设计

阳光穿透心脏的1/2处 2022-08-28 13:52 233阅读 0赞

### 文章目录 ###

*  一、unorder\_map底层实现
 *  二、map与unorder\_map的相同点与不同点
 *   *   *  1.map的优点与缺点
         *   *  1.map优点
             *  2.map缺点
             *  3.map适用场景
         *  1.unordered\_map的优点与缺点
         *   *  1.unordered\_map的优点
             *  2.unordered\_map的缺点
             *  3.unordered\_map的适用场景
 *  三、什么时候需要用unorder\_map，什么时候需要用map

# 一、unorder\_map底层实现 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16]  
**unordered\_map底层是用开链法来解决哈希冲突的，用哈希桶实现的。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_16_color_FFFFFF_t_70_g_se_x_16]

template<typename K, typename V>  //每个节点的结构
    	struct HashNode
    	{ 
    		pair<K, V> _kv;
    		HashNode<K,V>* _next;
     
    		HashNode(pair<K,V> p)
    			:_next(NULL)
    			, _kv(p)
    		{ }
    	};
     
    	template<typename K, typename V, class HashFunc = _HashFunc<K>> //哈希表的结构，第三个参数是仿函数，为了实现可以存储string
    	class HashTable
    	{ 
    	protected:
    		vector<Node*> _table;
    		size_t _size;
    	};

*  用一个vector来作为一个指针数组来存储节点的指针，\_size来保存当前哈希表中的有效元素个数。
 *  由于是K/V结构，所以选择一个pair的结构来存储K/V。
 *  vector中的每一个元素都指向一个链表，所有节点中需要一个next域的指针来指向下一个节点（采用单链表表结构）。
 *  **采用模板来实现哈希表可以存储任意数据类型的目的。**
 *  **使用了仿函数技术（为了实现可以存储string）。**

# 二、map与unorder\_map的相同点与不同点 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_20_color_FFFFFF_t_70_g_se_x_16]

### 1.map的优点与缺点 ###

#### 1.map优点 ####

优点：map内部实现是红黑树，有序性是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作，其复杂度为logN。  
**有序性:**这是map结构最大的优点，其元素的有序性在很多应用中都会简化很多的操作  
红黑树，内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现，因此效率非常的高

#### 2.map缺点 ####

空间占用率高，因为每一个节点都需要额外保存父节点，孩子节点以及红/黑性质，使得每一个节点都占用大量的空间。  
**空间占用率高，因为map内部实现了红黑树，虽然提高了运行效率，但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质，使得每一个节点都占用大量的空间**

#### 3.map适用场景 ####

适用处：对于那些有顺序有序要求的问题，用map会更高效一些。  
**map一般就是用在数据量小于1000或者对内存使用要求比较高的情况下。因为hash table需要申请的空间比较大，而红黑树则是新增一个节点就申请一个节点的空间。**

### 1.unordered\_map的优点与缺点 ###

#### 1.unordered\_map的优点 ####

内部实现是哈希表，因此其查找速度非常的快，复杂度为O(1)。

#### 2.unordered\_map的缺点 ####

更改哈希表的大小，重构哈希表比较耗费时间。

#### 3.unordered\_map的适用场景 ####

对于查找无序的数据问题，unordered\_map会更加高效一些。  
**如果数据量大的话并且需要频繁查找的话，就可以使用hash table实现的map了。这个时候内存已经不是主要的问题所在，而是查找时间了，这种情况下hash table的查找速度是常数而红黑树是O(log(n))，对于后者1024个数据最坏情况下要10次比较，在频繁查找的情况下这种时间耗费是很大的。**

# 三、什么时候需要用unorder\_map，什么时候需要用map #

总 体来说，**hash\_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。**并不一定常数就比log(n)小， hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash\_map。**但若你对内存使用特别严格，希望 程序尽可能少消耗内存**，那么一定要小心，hash\_map可能会让你陷入尴尬，特别是当你的hash\_map对象特别多时，你就更无法控制了，而且 hash\_map的构造速度较慢。

**现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。**

内存占有率的问题就转化成**红黑树**VS **hash表** , 还是unorder\_map占用的内存要高。  
但是unordered\_map执行效率要比map高很多  
对于unordered\_map或unordered\_set容器，其遍历顺序与创建该容器时输入的顺序不一定相同，因为遍历是按照哈希表从前往后依次遍历的  
**map和unordered\_map的使用:**  
unordered\_map的用法和map是一样的，提供了 insert，size，count等操作，并且里面的元素也是以pair类型来存贮的。其底层实现是完全不同的，上方已经解释了，但是就外部使用来说却是一致的。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a1fddcd667344f2099843c30e63fd700.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/2e44a1cd636d4fd1a31d984cc466545c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/30f1709d9d67441e95f201324732cd6e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5qOu5piO5biu5aSn5LqO6buR6JmO5biu_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/076ffe1a56f2421a95ddaea720d800fb.png