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

x33g5p2x  于11个月前 转载在 其他  
字(1.9k)|赞(0)|评价(0)|浏览(166)

一、unorder_map底层实现

unordered_map底层是用开链法来解决哈希冲突的,用哈希桶实现的。

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的相同点与不同点

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类型来存贮的。其底层实现是完全不同的,上方已经解释了,但是就外部使用来说却是一致的。

相关文章