map和hash_map都是C++里面提供的关联容器，它们都支持高性能的插入、删除、查找操作。map内部是基于红黑树来实现的，而hash_map是基于线性同余哈希+开链解决冲突 来实现的。
注意，hash_map并未纳入C++标准之中，因此不同厂商的STL库的hash_map的接口、性能保障可能会有出入。

在C++11中，hash_map被正式纳入到STL里面，但是换了个名字：unordered_map，取这个名字是因为hash_map不能提供元素的排序功能，而基于红黑树的map是可以通过不断地摘除最小元素来进行排序。

那么map和hash_map之间性能相差怎么样呢？我们来模拟一个场景：执行n次的随机插入、删除、find操作，统计他们的时长和内存使用情况。代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <map>
#include <utility>
#include <unordered_map>
#include <windows.h>
#include <Psapi.h>
#pragma comment(lib,"Psapi.lib")
using namespace std;
template <typename Map,typename Key,typename Value>
void insert(Map & map_obj, Key& k,Value & v)
	map_obj.insert(pair<Key,Value>(k,v));
template <typename Map,typename Key>
void erase(Map & map_obj, Key & key)
	map_obj.erase(key);
template <typename Map,typename Key>
void find(Map &map_obj, Key & k)
	map_obj.find(k);
int main()
	map<int, int> rb_maps;
	unordered_map<int, int> hash_maps;
	int n = 1e5;
	void* handle = GetCurrentProcess();
	PROCESS_MEMORY_COUNTERS pmc;
	GetProcessMemoryInfo(handle, &pmc, sizeof(pmc));//获取内存使用量
	int base_work_size = pmc.WorkingSetSize;
	srand(time(0));
	//rb_maps
	int start = clock();
	for (int i = 0; i < n; i++)
		int key = rand() % n;
		int value = rand() % n;
		switch (rand()%3)
		case 0:
			insert(rb_maps, key,value);
			break;
		case 1:
			erase(rb_maps, key);
			break;
		case 2:
			find(rb_maps, key);
			break;
	int end = clock();
	printf("rb_tree based map:%f\n", float(end - start)/CLOCKS_PER_SEC);
	GetProcessMemoryInfo(handle, &pmc, sizeof(pmc));//获取内存使用量
	int rb_work_size = pmc.WorkingSetSize-base_work_size;
	printf("memory used: %d bytes\n", rb_work_size);
	//hash_maps
	start = clock();
	for (int i = 0; i < n; i++)
		int key = rand() % n;
		int value = rand() % n;
		switch (rand() % 3)
		case 0:
			insert(hash_maps, key, value);
			break;
		case 1:
			erase(hash_maps, key);
			break;
		case 2:
			find(hash_maps, key);
			break;
	end = clock();
	printf("hash_table based map:%f\n", float(end - start)/CLOCKS_PER_SEC);
	GetProcessMemoryInfo(handle, &pmc, sizeof(pmc));
	int hash_work_size = pmc.WorkingSetSize-rb_work_size-base_work_size;
	printf("memory used: %d bytes\n", hash_work_size);
	system("pause");
以下列出了当n取不同值时候的差异：
 
插入、删除、查找 三种操作混合
 
n
map(时间)
hash_map(时间)
map(内存)
hash_map(内存)

       107
115.0739s
77.593s
1，515，520bytes
1，691，648bytes
可以看出，在时间上，hash_map优于map；
 但是hash_map却比map更耗空间。
 
对比插入操作
 
n
map(时间)
hash_map(时间)
map(内存)
hash_map(内存)

#pragma comment(lib,"Psapi.lib")
using namespace std;
template <typename Map,typename Key,typename Value>
void insert(Map & map_obj, Key& k,Value & v)
	map_obj.insert(pair<Key,Value>(k,v));




    

template <typename Map,typename Key>
void erase(Map & map_obj, Key & key)
	map_obj.erase(key);
template <typename Map,typename Key>
void find(Map &map_obj, Key & k)
	map_obj.find(k);
int main()
	map<int, int> rb_maps;
	unordered_map<int, int> hash_maps;
	int n = 1e7;
	for (int i = 0; i < n; i++)
		int key = rand() % n;
		int value = rand() % n;
		insert(rb_maps, key, value);
		insert(hash_maps, key, value);
	void* handle = GetCurrentProcess();
	PROCESS_MEMORY_COUNTERS pmc;
	GetProcessMemoryInfo(handle, &pmc, sizeof(pmc));//获取内存使用量
	int base_work_size = pmc.WorkingSetSize;
	srand(time(0));
	//rb_maps
	int start = clock();
	for (int i = 0; i < n; i++)
		int key = rand() % n;
		int value = rand() % n;
		switch (2)
		case 0:
			insert(rb_maps, key,value);
			break;
		case 1:
			erase(rb_maps, key);
			break;
		case 2:
			find(rb_maps, key);
			break;
	int end = clock();
	printf("rb_tree based map:%f\n", float(end - start)/CLOCKS_PER_SEC);
	GetProcessMemoryInfo(handle, &pmc, sizeof(pmc));//获取内存使用量
	int rb_work_size = pmc.WorkingSetSize-base_work_size;
	printf("memory used: %d bytes\n", rb_work_size);
	//hash_maps
	start = clock();
	for (int i = 0; i < n; i++)
		int key = rand() % n;
		int value = rand() % n;
		switch (2)
		case 0:
			insert(hash_maps, key, value);
			break;
		case 1:
			erase(hash_maps, key);
			break;
		case 2:
			find(hash_maps, key);
			break;
	end = clock();
	printf("hash_table based map:%f\n", float(end - start)/CLOCKS_PER_SEC);
	GetProcessMemoryInfo(handle, &pmc, sizeof(pmc));
	int hash_work_size = pmc.WorkingSetSize-rb_work_size-base_work_size;
	printf("memory used: %d bytes\n", hash_work_size);
	system("pause");
n
map(时间)
hash_map(时间)
map(内存)
hash_map(内存)

       107
72.33s
23.3s
2，945，024bytes
2，887，680bytes
key不随机
 
上面都还只是key是很随机的情况，如果key是递增或递减或怎么样呢？我们还是考察n=1e5,1e6时插入、删除、查找操作一起来。
 实验代码：
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <map>
#include <utility>
#include <unordered_map>
#include <windows.h>
#include <Psapi.h>
#pragma comment(lib,"Psapi.lib")
using namespace std;
template <typename Map,typename Key,typename Value>
void insert(Map & map_obj, Key& k,Value & v)
	map_obj.insert(pair<Key,Value>(k,v));
template <typename Map,typename Key>
void erase(Map & map_obj, Key & key)
	map_obj.erase(key);
template <typename Map,typename Key>
void find(Map &map_obj, Key & k)
	map_obj.find(k);
int main()
	map<int, int> rb_maps;
	unordered_map<int, int> hash_maps;
	int n = 1e6;
	void* handle = GetCurrentProcess();
	PROCESS_MEMORY_COUNTERS pmc;
	GetProcessMemoryInfo(handle, &pmc, sizeof(pmc));//获取内存使用量
	int base_work_size = pmc.WorkingSetSize;
	srand(time(0));
	//rb_maps
	int start = clock();
	for (int i = 0; i < n; i++)
		int key = i;
		int value = rand() % n;
		switch (rand()%3)
		case 0:
			insert(rb_maps, key,value);
			break;
		case 1:
			erase(rb_maps, key);
			break;
		case 2:
			find(rb_maps, key);
			break;
	int end = clock();
	printf("rb_tree based map:%f\n", float(end - start)/CLOCKS_PER_SEC);
	GetProcessMemoryInfo(handle, &pmc, sizeof(pmc));//获取内存使用量
	int rb_work_size = pmc.WorkingSetSize-base_work_size;
	printf("memory used: %d bytes\n", rb_work_size);
	//hash_maps
	start = clock();
	for (int i = 0; i < n; i++)
		int key = i;
		int value = rand() % n;
		switch (rand()%3)
		case 0:
			insert(hash_maps, key, value);
			break;
		case 1:
			erase(hash_maps, key);
			break;
		case 2:
			find(hash_maps, key);
			break;
	end = clock();
	printf("hash_table based map:%f\n", float(end - start)/CLOCKS_PER_SEC);
	GetProcessMemoryInfo(handle, &pmc, sizeof(pmc));
	int hash_work_size = pmc.WorkingSetSize-rb_work_size-base_work_size;
	printf("memory used: %d bytes\n", hash_work_size);
	system("pause");
n
map(时间)
hash_map(时间)
map(内存)
hash_map(内存)

       106
18.06s
8.97s
29，356，032 bytes
30，892，032bytes
可以看出，key不随机后，map是受蛮大的影响，而hash_map受影响较小。这是因为hash_map在实现的时候就不依赖key的随机，它自己会对key进行一次线性同余的hash,这种哈希函数的hash结果是随机的。
 
当数据量大了以后，hash_map在时间性能上是全面优于map的，在空间性能上会稍逊于map。
 对于非随机的key,hash_map在时间性能上更是优于map。
对于c++程序来说 map的使用无处不在。影响程序性能的瓶颈也往往是map的性能。尤其在大数据情况下，以及业务关联紧密而无法实现数据分发和并行处理的情况。map的性能就成了最关键的技术。
比如：ip表、mac表，电话号码表、身份证号码表的查询、等等。
stl库的map采用二分查找，性能最差。Google的哈希map性能和内存目前是最优的。
我在电信行业和信息安全行业里的工作经历发现，目前网络上的哈希算法都在查询速度上远远无法满足日趋增长的网络大数据要求。因此产生了自己写算法的想法。
现在我把自己的算法初稿发布出来，用我在一家信息安全的公司打工时的应用场景进行测试。就是病毒库特征码的检索。
                                    hash_map、unordered_map和map的效率、区别和分析一、前言二、三者的实现区别maphash_map和unordered_map三、三者查询效率高低时间效率三者使用选择例题：编译器报错解决方法
最近在做题的时候遇到了，就分享一下自己的心得。
hash_map、unordered_map和map的区别其实和hash_set、unordered_set和set的区别是一样的...
                                    测试结果 Release模式下：    查找效率：unordered_map ≈ hash_map > map
    std::map 的效率远小于 unordered_map 和 hash_map
Debug模式下：
1. 查找效率：hash_map > unordered_map > map
2. 随着容量的增加，hash_map, unordered_map的查找效率有所降低，但浮动不大毕竟是常量级别。map的效率直线下降....
详细数据见本文下方的 [测试过程记录](测试过程记录)
                                    实际上这个问题不光C++会遇到，其他所有语言的标准容器的实现及选择上都是要考虑的。做应用程序你可能觉得影响不大，但是写算法或者核心代码就要小心了。今天改进代码，顺便又来温习基础功课了。
　　还记得Herb Sutter那极有味道的《C++对话系列》么，在其中《产生真正的hash对象》这个故事里就讲了map的选择。顺便回顾一下，也讲一下我在实用中的理解。
　　选择map容器，是为了更...
上面可以看到Map接口的几个实现方式。简要说明：
TreeMap是基于树（红黑树）的实现方式，即添加到一个有序列表，在O(log n)的复杂度内通过key值找到value，优点是空间要求低，但在时间上不如HashMap。C++中Map的实现就是基于这种方式
HashMap是基于HashCode的实现方式，在查找上要比TreeMap速度快，添加时也没有任何顺序...
第一个可以称为关键字(key)，每个关键字只能在map中出现一次；
第二个可能称为该关键字的值(value)；
map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。Map主要用于资料一对一映射(one-to-one)的情況，map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在map内...
                                    一、Map成员上面可以看到Map接口的几个实现方式。简要说明：TreeMap是基于树（红黑树）的实现方式，即添加到一个有序列表，在O(log n)的复杂度内通过key值找到value，优点是空间要求低，但在时间上不如HashMap。C++中Map的实现就是基于这种方式HashMap是基于HashCode的实现方式，在查找上要比TreeMap速度快，添加时也没有任何顺序，但空间复杂度高。C++ un...
                                    http://www.cnblogs.com/zhjh256/p/6346501.html讲述了基本的map操作，在测试的时候，发现map的性能极为低下，与java相比相差了接近200倍。测试的逻辑如下：
    // map定义
    map&lt;int, FirstCPPCls*&gt; mapStudent;
    for (i=0;i&lt;10000;i++) {
                                    hash_map和map的区别在哪里？
构造函数。hash_map需要hash函数，等于函数；map只需要比较函数(小于函数).
存储结构。hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。
什么时候需要用hash_map，什么时候需要用map?
总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数..
简单对比map和unordered_map的性能。 
map内部是红黑树，在插入元素时会自动排序，而无序容器unordered_map内部是散列表，通过哈希而不是排序来快速操作元素，使得效率更高。当你不需要排序时选择unordered_map的效率更高。
#include &lt;iostream&gt;
#include &lt;string&gt;
#in...
                                    1、map简介
map是一类关联式容器。它的特点是增加和删除节点对迭代器的影响很小，除了那个操
作节点，对其他的节点都没有什么影响。对于迭代器来说，可以修改实值，而不能修改key。 
2、map的功能 
自动建立Key － value的对应。key 和 value可以是任意你需要的类型。 根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,0