文档章节

map,hash_map和unordered_map 实现比较

r
 ranjiewen
发布于 2016/11/03 23:52
字数 2112
阅读 5
收藏 0

map介绍

Map是STL[1]的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据处理能力,由于这个特性,它完成有可能在我们处理一对一数据的时候,在编程上提供快速通道。这里说下map内部数据的组织,map内部自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在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时需要指定的参数。 

 

 unordered_map介绍

Unordered maps are associative containers that store elements formed by the combination of a key value and amapped value, and which allows for fast retrieval of individual elements based on their keys.

In an unordered_map, the key value is generally used to uniquely identify the element, while the mapped value is an object with the content associated to this key. Types of key and mapped value may differ.

Internally, the elements in the unordered_map are not sorted in any particular order with respect to either theirkey or mapped values, but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values (with a constant average time complexity on average).

unordered_map containers are faster than map containers to access individual elements by their key, although they are generally less efficient for range iteration through a subset of their elements.

Unordered maps implement the direct access operator (operator[]) which allows for direct access of themapped value using its key value as argument.

unordered_map与map的区别

boost::unordered_map, 它与 stl::map的区别就是,stl::map是按照operator<比较判断元素是否相同,以及比较元素的大小,然后选择合适的位置插入到树中。所以,如果对map进行遍历(中序遍历)的话,输出的结果是有序的。顺序就是按照operator< 定义的大小排序。
而boost::unordered_map是计算元素的Hash值,根据Hash值判断元素是否相同。所以,对unordered_map进行遍历,结果是无序的。
用法的区别就是,stl::map 的key需要定义operator< 。 而boost::unordered_map需要定义hash_value函数并且重载operator==。对于内置类型,如string,这些都不用操心。对于自定义的类型做key,就需要自己重载operator< 或者hash_value()了。 
最后,说,当不需要结果排好序时,最好用unordered_map。
其实,stl::map对于与java中的TreeMap,而boost::unordered_map对应于java中的HashMap。 

 

[cpp] view plain copy
 
/** 
比较map、hash_map和unordered_map的执行效率以及内存占用情况 
**/  
  
#include <sys/types.h>  
#include <unistd.h>  
#include <sys/time.h>   
#include <iostream>  
#include <fstream>  
#include <string>  
#include <map>  
#include <ext/hash_map>  
#include <tr1/unordered_map>  
  
using namespace std;  
  
using namespace __gnu_cxx;  
  
using namespace std::tr1;  
  
#define N 100000000  //分别测试N=100,000、N=1,000,000、N=10,000,000以及N=100,000,000  
  
//分别定义MapKey=map<int,int>、hash_map<int,int>、unordered_map<int,int>  
//typedef map<int,int> MapKey;          //采用map  
//typedef hash_map<int,int> MapKey;     //采用hash_map  
typedef unordered_map<int,int> MapKey;  //采用unordered_map  
  
  
  
int GetPidMem(pid_t pid,string& memsize)  
{  
    char filename[1024];  
      
    snprintf(filename,sizeof(filename),"/proc/%d/status",pid);  
      
    ifstream fin;  
      
    fin.open(filename,ios::in);  
    if (! fin.is_open())  
    {  
        cout<<"open "<<filename<<" error!"<<endl;  
        return (-1);  
    }  
      
    char buf[1024];  
    char size[100];  
    char unit[100];  
      
    while(fin.getline(buf,sizeof(buf)-1))  
    {  
        if (0 != strncmp(buf,"VmRSS:",6))  
            continue;  
          
        sscanf(buf+6,"%s%s",size,unit);  
          
        memsize = string(size)+string(unit);  
    }  
      
    fin.close();  
      
    return 0;  
}  
  
int main(int argc, char *argv[])  
{  
    struct timeval begin;  
      
    struct timeval end;  
          
    MapKey MyMap;  
      
    gettimeofday(&begin,NULL);  
      
    for(int i=0;i<N;++i)  
        MyMap.insert(make_pair(i,i));  
      
    gettimeofday(&end,NULL);  
      
    cout<<"insert N="<<N<<",cost="<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;  
      
    for(int i=0;i<N;++i)  
        MyMap.find(i);  
  
    gettimeofday(&end,NULL);  
      
    cout<<"insert and getall N="<<N<<",cost="<<end.tv_sec-begin.tv_sec + float(end.tv_usec-begin.tv_usec)/1000000<<" sec"<<endl;  
      
    string memsize;  
      
    GetPidMem(getpid(),memsize);  
      
    cout<<memsize<<endl;  
      
    return 0;  
}  

 

运行结果

记录数N=100000时,结果如下:

Map类型

插入耗时,单位秒

插入加遍历耗时,单位秒

内存占用情况

map

0.110705

0.171859

5,780kB

hash_map

0.079074

0.091751

5,760kB

unordered_map

0.041311

0.050298

5,216kB

 

记录数N=1000000时,结果如下:

Map类型

插入耗时,单位秒

插入加遍历耗时,单位秒

内存占用情况

map

1.22678

1.95435

47,960kB

hash_map

0.684772

0.814646

44,632kB

unordered_map

0.311155

0.386898

40,604kB

 

记录数N=10000000时,结果如下:

Map类型

插入耗时,单位秒

插入加遍历耗时,单位秒

内存占用情况

map

14.9517

23.9928

469,844kB

hash_map

5.93318

7.18117

411,904kB

unordered_map

3.64201

4.43355

453,920kB

 

记录数N=100000000时,结果如下:

Map类型

插入耗时,单位秒

插入加遍历耗时,单位秒

内存占用情况

map

167.941

251.591

4,688,692kB

hash_map

46.3518

57.6972

3,912,632kB

unordered_map

28.359

35.122

4,3012,56kB

 

结果分析

运行效率方面:unordered_map最高,hash_map其次,而map效率最低

占用内存方面:hash_map内存占用最低,unordered_map其次,而map占用最高

 

stl::map

 

[cpp]  view plain  copy
 
  1. #include<string>  
  2. #include<iostream>  
  3. #include<map>  
  4.   
  5. using namespace std;  
  6.   
  7. struct person  
  8. {  
  9.     string name;  
  10.     int age;  
  11.   
  12.     person(string name, int age)  
  13.     {  
  14.         this->name =  name;  
  15.         this->age = age;  
  16.     }  
  17.   
  18.     bool operator < (const person& p) const  
  19.     {  
  20.         return this->age < p.age;  
  21.     }  
  22. };  
  23.   
  24. map<person,int> m;  
  25. int main()  
  26. {  
  27.     person p1("Tom1",20);  
  28.     person p2("Tom2",22);  
  29.     person p3("Tom3",22);  
  30.     person p4("Tom4",23);  
  31.     person p5("Tom5",24);  
  32.     m.insert(make_pair(p3, 100));  
  33.     m.insert(make_pair(p4, 100));  
  34.     m.insert(make_pair(p5, 100));  
  35.     m.insert(make_pair(p1, 100));  
  36.     m.insert(make_pair(p2, 100));  
  37.       
  38.     for(map<person, int>::iterator iter = m.begin(); iter != m.end(); iter++)  
  39.     {  
  40.         cout<<iter->first.name<<"\t"<<iter->first.age<<endl;  
  41.     }  
  42.       
  43.     return 0;  
  44. }  

 

output:

Tom1    20
Tom3    22
Tom4    23
Tom5    24

 

operator<的重载一定要定义成const。因为map内部实现时调用operator<的函数好像是const。

由于operator<比较的只是age,所以因为Tom2和Tom3的age相同,所以最终结果里面只有Tom3,没有Tom2

 

boost::unordered_map

 

[cpp]  view plain  copy
 
  1. #include<string>  
  2. #include<iostream>  
  3.   
  4. #include<boost/unordered_map.hpp>  
  5.   
  6. using namespace std;  
  7.   
  8. struct person  
  9. {  
  10.     string name;  
  11.     int age;  
  12.   
  13.     person(string name, int age)  
  14.     {  
  15.         this->name =  name;  
  16.         this->age = age;  
  17.     }  
  18.   
  19.     bool operator== (const person& p) const  
  20.     {  
  21.         return name==p.name && age==p.age;  
  22.     }  
  23. };  
  24.   
  25. size_t hash_value(const person& p)  
  26. {  
  27.     size_t seed = 0;  
  28.     boost::hash_combine(seed, boost::hash_value(p.name));  
  29.     boost::hash_combine(seed, boost::hash_value(p.age));  
  30.     return seed;  
  31. }  
  32.   
  33. int main()  
  34. {  
  35.     typedef boost::unordered_map<person,int> umap;  
  36.     umap m;  
  37.     person p1("Tom1",20);  
  38.     person p2("Tom2",22);  
  39.     person p3("Tom3",22);  
  40.     person p4("Tom4",23);  
  41.     person p5("Tom5",24);  
  42.     m.insert(umap::value_type(p3, 100));  
  43.     m.insert(umap::value_type(p4, 100));  
  44.     m.insert(umap::value_type(p5, 100));  
  45.     m.insert(umap::value_type(p1, 100));  
  46.     m.insert(umap::value_type(p2, 100));  
  47.       
  48.     for(umap::iterator iter = m.begin(); iter != m.end(); iter++)  
  49.     {  
  50.         cout<<iter->first.name<<"\t"<<iter->first.age<<endl;  
  51.     }  
  52.       
  53.     return 0;  
  54. }  


输出

 

Tom1    20
Tom5    24
Tom4    23
Tom2    22
Tom3    22

 

必须要自定义operator==和hash_value。 重载operator==是因为,如果两个元素的hash_value的值相同,并不能断定这两个元素就相同,必须再调用operator==。 当然,如果hash_value的值不同,就不需要调用operator==了。

本文转载自:http://www.cnblogs.com/ranjiewen/p/5328137.html

r
粉丝 1
博文 203
码字总数 28
作品 0
武汉
程序员
私信 提问
C++中的哈希容器unordered_map

随着C++0x标准的确立,C++的标准库中也终于有了hash table这个东西。 很久以来,STL中都只提供<map>作为存放对应关系的容器,内部通常用红黑树实现,据说原因是二叉平衡树(如红黑树)的各种...

曾劲松
2016/06/15
88
0
C++中的哈希容器unordered_map

随着C++0x标准的确立,C++的标准库中也终于有了hash table这个东西。 很久以来,STL中都只提供<map>作为存放对应关系的容器,内部通常用红黑树实现,据说原因是二叉平衡树(如红黑树)的各种...

曾劲松
2016/06/15
136
0
map和unordered_map

map 是有序的 内部通常是红黑树实现 unorderedmap 是无序的 内部是hash 所以unorderedmap 的插入查找删除速度比map快几倍,对数据的顺序没有要求时尽量用unorderedmap Note: erase的时候 为...

梦想游戏人
2016/04/06
285
0
C++ map和unordered_map自定义key

一、map 1)最简单的方法就是实现该自定义类型的<操作符,代码如下: 之后就可以使用Foo作为map的key了: 2)定义一个比较操作符,使用它作为map的模板参数,代码如下: 这时候可以使用Foo2作...

吃一堑消化不良
2016/10/12
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

Docker 可视化管理 portainer

官网安装指南: https://portainer.readthedocs.io/en/latest/deployment.html docker-compose.yml 位置,下载地址:https://downloads.portainer.io/docker-compose.yml...

Moks角木
33分钟前
3
0
Spring Security 实战干货:必须掌握的一些内置 Filter

1. 前言 上一文我们使用 Spring Security 实现了各种登录聚合的场面。其中我们是通过在 UsernamePasswordAuthenticationFilter 之前一个自定义的过滤器实现的。我怎么知道自定义过滤器要加在...

码农小胖哥
36分钟前
6
0
常见分布式事务解决方案

1 微服务的发展 微服务倡导将复杂的单体应用拆分为若干个功能简单、松耦合的服务,这样可以降低开发难度、增强扩展性、便于敏捷开发。当前被越来越多的开发者推崇,很多互联网行业巨头、开源...

asdf08442a
37分钟前
3
0
influxdb continuous queries(cq)从入门到放弃

从前一篇influxdb的文章prometheus基于influxdb的监控数据持久化存储方案完成之后,就一直在折腾influxdb发布测试和生产环境的问题,经过接近2个月的验证,最终发现使用influxdb自带cq的方案...

狗陈
48分钟前
7
0
7.线程通信

在现实生活中,如果一个人团队正在共同完成任务,那么他们之间应该有通信,以便正确完成任务。 同样的比喻也适用于线程。 在编程中,要减少处理器的理想时间,我们创建了多个线程,并为每个线...

Eappo_Geng
54分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部