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;
};
优点:map内部实现是红黑树,有序性是map结构最大的优点,其元素的有序性在很多应用中都会简化很多的操作,其复杂度为logN。
**有序性:**这是map结构最大的优点,其元素的有序性在很多应用中都会简化很多的操作
红黑树,内部实现一个红黑书使得map的很多操作在lgn的时间复杂度下就可以实现,因此效率非常的高
空间占用率高,因为每一个节点都需要额外保存父节点,孩子节点以及红/黑性质,使得每一个节点都占用大量的空间。
空间占用率高,因为map内部实现了红黑树,虽然提高了运行效率,但是因为每一个节点都需要额外保存父节点、孩子节点和红/黑性质,使得每一个节点都占用大量的空间
适用处:对于那些有顺序有序要求的问题,用map会更高效一些。
map一般就是用在数据量小于1000或者对内存使用要求比较高的情况下。因为hash table需要申请的空间比较大,而红黑树则是新增一个节点就申请一个节点的空间。
内部实现是哈希表,因此其查找速度非常的快,复杂度为O(1)。
更改哈希表的大小,重构哈希表比较耗费时间。
对于查找无序的数据问题,unordered_map会更加高效一些。
如果数据量大的话并且需要频繁查找的话,就可以使用hash table实现的map了。这个时候内存已经不是主要的问题所在,而是查找时间了,这种情况下hash table的查找速度是常数而红黑树是O(log(n)),对于后者1024个数据最坏情况下要10次比较,在频繁查找的情况下这种时间耗费是很大的。
总 体来说,**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类型来存贮的。其底层实现是完全不同的,上方已经解释了,但是就外部使用来说却是一致的。
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_44918090/article/details/120383491
内容来源于网络,如有侵权,请联系作者删除!