精华内容
下载资源
问答
  • C++ unordered_maphash_map的用法

    千次阅读 2019-09-16 20:50:47
    1、C++ STL中哈希表 hash_map从头到尾详细介绍 2、C++ unordered_map unordered_maphash_map的替代名称 最初的 C++ 标准库中没有类似 hash_map 的实现,但不同实现者自己提供了非标准的 hash_map。 因为这些实现...

    1、C++ STL中哈希表 hash_map从头到尾详细介绍
    2、C++ unordered_map

    unordered_map是hash_map的替代名称

    最初的 C++ 标准库中没有类似 hash_map 的实现,但不同实现者自己提供了非标准的 hash_map。 因为这些实现不是遵循标准编写的,所以它们在功能和性能保证方面都有细微差别。

    从 C++ 11 开始,hash_map 实现已被添加到标准库中。但为了防止与已开发的代码存在冲突,决定使用替代名称 unordered_map。这个名字其实更具描述性,因为它暗示了该类元素的无序性。

    hash_map原理

    hash_map基于hash table(哈希表)。 哈希表最大的优点,就是把数据的存储和查找消耗的时间大大降低,几乎可以看成是常数时间;而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下,用空间换时间的做法是值得的。另外,编码比较容易也是它的特点之一。

    其基本原理是:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标,hash值)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方,称为桶。

    但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了“冲突”,换句话说,就是把不同的元素分在了相同的“类”之中。 总的来说,“直接定址”与“解决冲突”是哈希表的两大特点。

    hash_map,首先分配一大片内存,形成许多桶。是利用hash函数,对key进行映射到不同区域(桶)进行保存。其插入过程是:

    1、得到key
    2、通过hash函数得到hash值
    3、得到桶号(一般都为hash值对桶数求模)
    4、存放key和value在桶内。

    其取值过程是:
    1、得到key
    2、通过hash函数得到hash值
    3、得到桶号(一般都为hash值对桶数求模)
    4、比较桶的内部元素是否与key相等,若都不相等,则没有找到。
    5、取出相等的记录的value。
    hash_map中直接地址用hash函数生成,解决冲突,用比较函数解决。这里可以看出,如果每个桶内部只有一个元素,那么查找的时候只有一次比较。当许多桶内没有值时,许多查询就会更快了(指查不到的时候).

    由此可见,要实现哈希表, 和用户相关的是:hash函数和比较函数。这两个参数刚好是我们在使用hash_map时需要指定的参数。在没有指定hash函数和比较函数的时候,会有一个缺省的函数。

    例子

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 [ n/2 ] 的元素。

    你可以假设数组是非空的,并且给定的数组总是存在众数。

    #include <stdlib.h>
    #include <vector>
    #include <unordered_map>
    class MaxFrequencyNum {
    public:
    	int majorityElement(std::vector<int>& nums) {
    		std::unordered_map<int, int> hash;
    		std::unordered_map<int, int>::iterator it;
    		int res = 0;
    		int len = nums.size();
    		for (int i = 0; i<len; i++) {
    			it = hash.find(nums[i]);
    			if (it == hash.end())
    				hash[nums[i]] = 1; //hash.insert({nums[i],1});
    			else {
    				hash[nums[i]]++;
    			}
    			if (hash[nums[i]] > len / 2) {
    				res = nums[i];
    				break;
    			}
    		}
    		return res;
    	}
    };
    
    展开全文
  • map unordered_map hash_map的查找性能测试

    千次阅读 2019-10-30 00:55:05
    结论如下: ... hash_map 2. 容量为100的时候,查找效率:map = unordered_map > hash_map 3. 容量为1000的时候,查找效率:unordered_map > hash_map > 4倍map 4. 容量为1万的时候,查...

    结论如下:

    Release模式下:

    1. 容量为10的时候,查找效率:map > unordered_map > hash_map

    2. 容量为100的时候,查找效率:map = unordered_map > hash_map

    3. 容量为1000的时候,查找效率:unordered_map > hash_map > 4倍map

    4. 容量为1万的时候,查找效率:hash_map > unordered_map > 4倍map

    5. 容量为10万的时候,查找效率:hash_map > unordered_map > 4倍map

    6. 容量为100万的时候,查找效率:hash_map > unordered_map > 1.6倍map

    7. 容量为1000万的时候,查找效率:hash_map > unordered_map > 1.4倍map

    8. 容量为1亿的时候,程序崩溃了,哈哈哈哈哈哈,如果你知道原因请告诉我

    9. debug模式下和release模式下,差距非常大,几百倍的差距。。。。。

    Debug模式下:

    1. 查找效率:hash_map > unordered_map > map

    2. 随着容量的增加,hash_map, unordered_map的查找效率有所降低,但浮动不大毕竟是常量级别。map的效率直线下降。。。

    3. 容量为一千万的时候,程序同样崩溃

    实验结果如下图:

    Release模式                                                                                Debug模式(注意:相比Release模式还降低了10倍的查询量)

        

     

    代码如下:

    #include<iostream>
    #include<map>
    #include<hash_map>
    #include<unordered_map>
    #include<boost/progress.hpp>
    
    using namespace std;
    using namespace boost;
    
    // 测试函数,
    // size        :    map的实际大小
    // times    :    查找的轮次,每一轮次都从0查找到size-1
    void test(int size, int times)
    {
        cout << "size=" << size << "; times=" << times << endl;
    
        map<int, int>                m;
        unordered_map<int, int>        um;
        hash_map<int, int>            hm;
    
        // 初始化
        for (int i = 0; i<size; i++)
        {
            m[i] = i;
            um[i] = i;
            hm[i] = i;
        }
    
        // map的查找
        {
            int count = 0;
            progress_timer t; // progress_timer变量会在创建时计时,析构时自动打印出耗时,所以不会受到前面初始化的影响,下同,不再解释
            for (int i = 0; i<times; i++)
            {
                for (int j = 0; j<size; j++)
                {
                    if (m.find(j) != m.end())
                    {
                        count++;
                    }
                }
            }
            cout << "count:" << count <<", map:";
        }
    
    
        // unordered_map的查找
        {
            int count = 0;
            progress_timer t;
            for (int i = 0; i<times; i++)
            {
                for (int j = 0; j<size; j++)
                {
                    if (um.find(j) != um.end())
                    {
                        count++;
                    }
                }
            }
            cout << "count:" << count << ", unordered_map:";
        }
    
        // hash_map的查找
        {
            int count = 0;
            progress_timer t;
            for (int i = 0; i<times; i++)
            {
                for (int j = 0; j<size; j++)
                {
                    if (hm.find(j) != hm.end())
                    {
                        count++;
                    }
                }
            }
            cout << "count:" << count << ", hash_map:";
        }
    }
    
    int main()
    {
        test(10,10000000);        // 容量:10        查找:1千万轮次
    
        test(100, 1000000);        // 容量:100        查找:1百万轮次
    
        test(1000, 100000);        // 容量:1000        查找:10万轮次
    
        test(10000, 10000);        // 容量:10000    查找:1万轮次
    
        test(100000, 1000);        // 容量:100000    查找:1000轮次
    
        test(1000000, 100);        // 容量:1000000    查找:100轮次
    
        test(10000000, 10);        // 容量:10000000    查找:10轮次
    
        getchar();
        return 0;
    }

     

    展开全文
  • #include #include #include using namespace std; using namespace stdext; typedef std::hash_map _hash_map;...typedef std::pair _hash_map_pair;...typedef std::hash_map::iterator _hash_map_iterato
    #include <windows.h>
    #include <hash_map>
    #include <map>
    
    using namespace std;
    using namespace stdext;
    
    typedef std::hash_map<int, string>				_hash_map;
    typedef std::pair<int, string>					_hash_map_pair;
    typedef std::hash_map<int, string>::iterator	_hash_map_iterator;
    
    typedef std::map<int, string>					_map;
    typedef std::map<int, string>::iterator			_map_iterator;
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	//_hash_map tmpMap;
    
    	//tmpMap[1] = string("1");
    	//tmpMap[1] = string("2");
    	//tmpMap[1] = string("3");
    
    	//tmpMap.insert(_pair(1, string("1")));
    	//tmpMap.insert(_pair(1, string("2")));
    	//tmpMap.insert(_pair(1, string("3")));
    
    	//
    	_map tmpMap;
    
    	tmpMap.insert(_hash_map_pair(1, string("1")));
    	tmpMap.insert(_hash_map_pair(1, string("2")));
    	tmpMap.insert(_hash_map_pair(2, string("3")));
    
    	system("pause");
    	return 0;
    }


    2015-2-13 15:32:47更新:

    	std::map<int, int> tmpMap;
    	std::map<int, int>::iterator b;
    	tmpMap[1] = 1;
    	b = tmpMap.begin();
    	printf("map size is %d, first pair key-value is %d-%d.\n", tmpMap.size(), b->first, b->second);
    	tmpMap[1] = 2;
    	b = tmpMap.begin();
    	printf("map size is %d, first pair key-value is %d-%d.\n", tmpMap.size(), b->first, b->second);
    
    以上代码的打印结果为:

    map size is 1, first pair key-value is 1-1.
    map size is 1, first pair key-value is 1-2.
    请按任意键继续. . .

    可以发现,在std::map的使用的时候,如果用下标的形式操作一组key-value,如果这组不存在,则进行插入操作,如果存在,则会更新。

    展开全文
  • hash_map、unordered_mapmap的效率、区别和分析一、前言二、三者的实现区别maphash_map和unordered_map三、三者查询效率高低时间效率三者使用选择例题:编译器报错解决方法 一、前言 最近在做题的时候遇到了,就...

    一、前言

    最近在做题的时候遇到了,就分享一下自己的心得。
    hash_map、unordered_map和map的区别其实和hash_set、unordered_set和set的区别是一样的,本博客就只讲map了。

    二、三者的实现区别

    map

    红黑树实现(二叉查找树的一种)可以实现数据log n级的插入、查找效率。

    hash_map和unordered_map

    这里为什么将二者一起说呢?因为hash_map和unordered_map都是用哈希表实现的,它们有什么区别吗?其实区别不大,但是推荐使用unordered_map,因为unordered_map在C++11就被录入标准库了,而hash并没有进入标准库。

    说到这那到底hash_set与unordered_set哪个更好呢?实际上unordered_set在C++11的时候被引入标准库了,而hash_set并没有,所以建议还是使用unordered_set比较好,这就好比一个是官方认证的,一个是民间流传的。在编译器中,Visual Studio(当然需要支持C++11的版本)库中两个数据结构都有定义,而在gcc/g++中并不支持hash_set。
    ————————————————
    原文链接:https://blog.csdn.net/FX677588/article/details/76400389

    三、三者查询效率高低

    相信很多人觉得log n的map查询复杂度已经可以了,确实log 是比较理想的时间复杂度,但是hash_map和unordered_map可以更快!因为它们都是用哈希表实现的,具体实现方式可以不用详细了解,我们都知道在哈希函数散列的过程中可能会遇到冲突,所以:

    时间效率

    hash_map和unordered_map的一次查询/插入时间为:
    无冲突时:O(1) 有冲突时最坏为O(n)。

    时间复杂度为常数级,一般更倾向于左边

    map的平均时间复杂度为:log n

    1.以上讨论的都是查询时间,它们的差距主要是因为它们实现的数据结构的差别,前者是哈希表,查询/插入时间几乎为常数;而红黑树的查询、插入时间都是log级别的。

    2.如果是遍历(用迭代器),我觉得时间复杂度区别不大,基于哈希表的hash_map和unordered_map的begin()的查找最优是O(1)最坏是O(n),遍历时间是O(n),总时间是O(2n);而基于红黑树的map的遍历是logn(迭代器++是中序遍历),总时间复杂度为O(logn+n);这些分析都是基于对map有操作的情况下的即map.begin()可能随着map.erase(iter)或是map.add(key, value)操作而发生改变,所以综上它们的遍历时间都可以看做O(n)线性时间。

    3.但是基于哈希表结构的容器构造速度慢,占用的空间也比大。

    其实具体选择哪个容器还得综合考虑三个因素:查找速度, 数据量, 内存使用。

    如果想详细了解三者更详细的时间效率对比:
    https://blog.csdn.net/stpeace/article/details/81283650

    在较大量的数据测试下,我们知道
    时间效率:unordered_map最好,hash_map其次,而map效率最差。

    三者使用选择

    由上面的分析我们知道hash_map和unordered_map应该选择录入标准库的unordered_map。

    那unordered_map和map如何选择呢?
    从上面的分析我们知道unordered_map时间更快,当然选择unordered_map了,可以这么选,但对于单次log级(map) 可能小于常数级(unordered_map),所以稳定性是map比较好,但是对于有些题目要求的查询次数比较频繁时,我们应该unordered_map优先。

    不懂?看下面2020 蓝桥杯大学 B 组省赛模拟赛(一) F:寻找重复项

    例题:

    在这里插入图片描述
    样例输入:

    2 2 9
    

    输出:

    4
    

    有人会说用一个标记数组来查询某数是否出现只需要O(1)不香吗
    还要hash_map、unordered_map和map吗?

    你再仔细看看数据范围109数组开不了这么大,所以不香了。
    而且有时候我们查询的可能不是一个整数,所以map还是很香的嘛。
    下面的代码我们都会:

    #include<iostream>
    #include<cstdio> 
    #include<cmath>
    #include<map> 
    #define ll long long int
    using namespace std;
    map<ll,int> book;
    int main(void)
    {
    	int i=0;
    	ll s=1ll;
    	ll a,b,c;
    	scanf("%lld %lld %lld",&a,&b,&c);
    	
    	while(true)
    	{
    		book[s]=1;
    		s=(s*a%c+s%b%c)%c;
    		i++;
    		if(book[s]) break;
    		if(i>2000000) break;
    	}
    	if(i>2000000) printf("-1\n");
    	else printf("%d\n",i);
    	return 0;
    }
    

    超时了?!
    我们可以在上面的代码看到,我们每计算一个值就要查询一次这个值是否存在,查询次数频繁。
    我们就放弃map改用unordered_map。
    unordered_map实现代码:

    #include<iostream>
    #include<cstdio> 
    #include<cmath>
    #include<unordered_map> 
    #define ll long long int
    using namespace std;
    unordered_map<ll,int> book;
    int main(void)
    {
    	int i=0;
    	ll s=1ll;
    	ll a,b,c;
    	scanf("%lld %lld %lld",&a,&b,&c);
    	
    	while(true)
    	{
    		book[s]=1;
    		s=(s*a%c+s%b%c)%c;
    		i++;
    		if(book[s]) break;
    		if(i>2000000) break;
    	}
    	if(i>2000000) printf("-1\n");
    	else printf("%d\n",i);
    	return 0;
    }
    

    其实map一般够的,map不行再改用unordered_map。

    编译器报错解决方法

    由于unordered_map是c++11里的,很多编译器还是使用的比较老的版本比如C++98,我们拿devc++为例,我们如何让它支持c++11呢?
    在编译时假如-std=c++11,具体请点击链接

    其实目前蓝桥杯不支持c++11,故加了上面的蓝桥杯还是不让用的

    展开全文
  • hash_map是C++非标准STL,因为标准化的推进,hash_map属于非标准容器,未来将要用unordered_map替代。 建议我们使用unorder_map替代hash_map 解决办法 (1)使用<unorder_map>替换<hash_map> 或者 (2)...
  • 这个列表由我写的一个 perl 程序抓取 time_hash_map 的结果生成。time_hash_map 是 google 自己实现的 hash table 中的一个性能测试程序,我在其中加入了针对 gold_hash_map 的测试,没有其它任何改动。链接中那个...
  • 首先: ...由于在C++标准库中没有定义散列表hash_map,标准库的不同实现者将提供一个通常名为hash_map的非标准散列表。因为这些实现不是遵循标准编写的,所以它们在功能和性能保证上都有微妙的差别...
  • hash_table是STL中hash_maphash_set 的内部数据结构,hash_table的插入 / 删除 / 查找的时间复杂度都为O(1), 是查找速度最快的一种数据结构,但是hash_table中的数据是无序的,一般也只有在数据不需要排序, 只...
  • C++:maphash_map、unordered_map

    千次阅读 2019-07-10 20:39:12
    面试经常被问的问题之一,便是maphash_map的区别,以及什么时候用map什么时候用hash_map。另外也了解到还有C++11的unordered_map,所以这里一并介绍三个了。用法就不介绍了,主要介绍区别。 1. 三者的区别 map...
  • 1. unordered_map, hash_map, map 概述C++中,map(来自于 STL) ,底层实现采用红黑树。hash_map(有很多种实现,底层实现均采用hashtable。目前普遍使用的来自 SGI 的 STL),还未成为C++标准,不过,在可预见的将来,...
  • hash_map的简单应用

    2017-01-05 19:20:45
    hash_map
  • map 学习(下)——C++ 中的 hash_map, unordered_map 总结 C++ 中关于 hash_map 与 unordered_map 的相关内容与优劣势比较。
  • C++ 中的 hash_map, unordered_map

    千次阅读 2018-06-22 10:41:33
    转载自:https://blog.csdn.net/ajianyingxiaoqinghan/article/details/78542932一、hash_map参考《C++ STL中哈希表 hash_map介绍》即可。博主写的很详细。注: hash_map 不是标准的。笔者写该文档时本来想尝试些一...
  • hash_map是C++非标准STL,因为标准化的推进,hash_map属于非标准容器,未来将要用unordered_map替代之。建议我们使用unorder_map替代hash_map,解决办法 (1)使用<unorder_map>替换<hash_map> 或者 (2...
  • STL源码剖析——hash_maphash_multimap

    千次阅读 2016-06-18 09:26:20
    SGI STL中的map底层以红黑树实现,hash_maphash table实现。 hash_map不允许插入重新键值,hash_multimap允许插入重复键值。这两者的关系就像map和multimap的关系。底层的hash table提供的大部分的操作,hash_map...
  • 一、hash_map、unordered_map 这两个的内部结构都是采用哈希表来实现。区别在哪里?unordered_map在C++11的时候被引入标准库了,而hash_map没有,所以建议还是使用unordered_map比较好。 哈希表的好处是什么?查询...
  • 2012年1月8日 | by zieckey | 标签: hash_mapmap, STL, unordered_map, 关联容器, 性能比较, 用法示例 作者: zieckey 发表时间: 2012年1月8日 本文链接: ...
  • C++ maphash_map的性能对比

    千次阅读 2019-12-23 11:14:07
    maphash_map都是C++里面提供的关联容器,它们都支持高性能的插入、删除、查找操作。map内部是基于红黑树来实现的,而hash_map是基于线性同余哈希+开链解决冲突 来实现的。 注意,hash_map并未纳入C++标准之中,...
  • 类似于标准的map以rb_tree为底层实现,hash_map以hashtable为底层实现,hash_map的底层操作也是由hashtabe提供。 运用map,为的是能够快速的根据key搜索元素。这一点无论其底层是rb_tree或是hashtable,都可以...
  • hash_map

    千次阅读 2011-12-01 16:17:35
    hash表有两点要考虑: 1,寻址:定义hash函数,即对key做运算的一个函数,返回对应的key+value的存放位置。这一点要求定义一个hash函数 ...SGI STL中hash_map的声明: template , class _EqualKey =
  • 转自... 本文第一部分、从set/map谈到hashtable/hash_map/hash_set,简要介绍下set/map/multiset/multimap,及hash_set/hash_map/hash_multiset/hash_multimap之区别(万丈高楼平地起,基础最重
  • hash_map/unordered_map原理和使用整理

    千次阅读 2016-07-06 01:23:22
    版权声明:本文为博主原创文章... ...运行效率方面:unordered_map最高,hash_map其次,而map效率最低单提供了有序的序列。...占用内存方面:hash_map内存占用最低,unordered_map其次(数量少时优于hash_map),而ma
  • 当在Linux下cpp文件包含hash_maphash_set时,会出现"‘hash_map’ was not declared in this scope"问题。 #include #include #include using namespace std; int main(void) { hash_map hmap; hmap[1] = ...
  • map、set、multimap、multiset、hash_map、hah_set、hash_multimap、hash_multiset
  • hash_mapmap的区别

    2015-09-02 17:30:35
    这里列几个常见问题,应该对你理解和使用hash_map比较有帮助。 4.1 hash_mapmap的区别在哪里? 构造函数。hash_map需要hash函数,等于函数;map只需要比较函数(小于函数).存储结构。hash_map采用hash表存储,map...
  • stl中maphash_map,unordered_map的区别

    千次阅读 2018-09-29 10:04:20
    1. map存储结构是红黑树,所以需要定义比较函数(less),查找效率为O(logN). 2. unordered_map存储结构是数组,需要定义hash函数...3. unordered_map就是hash_map. 4. insert、find、[]等方法形式上一致。  ...
  • hash_map,map,unordered_map效率

    千次阅读 2016-04-30 11:18:28
    利用unordered_map代替hash_map 实验环境 操作系统 fedora9编译器版本 gcc4.3 实验方式 各种map使用插入和查找,比较速度和相关性能 代码 参考代码下面测试说明了速度之间的比较: map类型 插入速度 ...
  • 利用unordered_map代替hash_map 实验环境 操作系统 fedora9编译器版本 gcc4.3 实验方式 各种map使用插入和查找,比较速度和相关性能 下面测试说明了速度之间的比较: map类型 ...
  • 1 白话hash_map/unordered_map 本篇博文,我们来了解另外两个基于key-value的新结构hash_map和unorderd_map。两者都属于基于哈希表(hash table)构建的数据结构,都是存储的key-value的值,可以通过key快速索引到...
  • 最近在使用hash_map 的时候发现不能自定义hash 函数,只要这样的话,就会出问题,hash_map*, int, hash*>, eqstr> day ;但是如果这样的话就不会有问题了,还望大神求解呀 hash_map*, int> days; #include #include...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 264,625
精华内容 105,850
关键字:

hash_map