C++ map和hash_map的性能对比

Bertha 。 2023-06-24 11:29 18阅读 0赞

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取不同值时候的差异：

# 插入、删除、查找 三种操作混合 #

<table> 
 <thead> 
 <tr> 
 <th>n</th> 
 <th>map(时间)</th> 
 <th>hash_map(时间)</th> 
 <th>map(内存)</th> 
 <th>hash_map(内存)</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> 1 0 5 10^5 105</td> 
 <td>1.028s</td> 
 <td>0.8s</td> 
 <td>1，351，680 bytes</td> 
 <td>1，265，664 bytes</td> 
 </tr> 
 <tr> 
 <td> 1 0 6 10^6 106</td> 
 <td>11.439s</td> 
 <td>7.893s</td> 
 <td>1，564，672bytes</td> 
 <td>1，695，744bytes</td> 
 </tr> 
 <tr> 
 <td> 1 0 7 10^7 107</td> 
 <td>115.0739s</td> 
 <td>77.593s</td> 
 <td>1，515，520bytes</td> 
 <td>1，691，648bytes</td> 
 </tr> 
 </tbody> 
</table>

可以看出，在时间上，hash\_map优于map；  
但是hash\_map却比map更耗空间。

# 对比插入操作 #

<table> 
 <thead> 
 <tr> 
 <th>n</th> 
 <th>map(时间)</th> 
 <th>hash_map(时间)</th> 
 <th>map(内存)</th> 
 <th>hash_map(内存)</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> 1 0 5 10^5 105</td> 
 <td>1.086s</td> 
 <td>1.276s</td> 
 <td>2，850，816 bytes</td> 
 <td>2，764，800 bytes</td> 
 </tr> 
 <tr> 
 <td> 1 0 6 10^6 106</td> 
 <td>11.208s</td> 
 <td>10.06s</td> 
 <td>2，985，984bytes</td> 
 <td>2，887，680bytes</td> 
 </tr> 
 <tr> 
 <td> 1 0 7 10^7 107</td> 
 <td>110.33s</td> 
 <td>78.3s</td> 
 <td>2，945，024bytes</td> 
 <td>2，887，680bytes</td> 
 </tr> 
 </tbody> 
</table>

可以看出，如果只是插入操作，在时间上hash\_map优于map。  
而且是hash\_map依然比map更耗空间。  
但是可以看到一个很有意思的地方：n= 1 0 6 10^6 106 和 n = 1 0 7 10^7 107，hash\_map使用的空间的相同的。

# 对比查找操作 #

先插入，后查找。

#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 = 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");
 }

结果：

<table> 
 <thead> 
 <tr> 
 <th>n</th> 
 <th>map(时间)</th> 
 <th>hash_map(时间)</th> 
 <th>map(内存)</th> 
 <th>hash_map(内存)</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> 1 0 5 10^5 105</td> 
 <td>0.746s</td> 
 <td>0.209s</td> 
 <td>102，400 bytes</td> 
 <td>4,096 bytes</td> 
 </tr> 
 <tr> 
 <td> 1 0 6 10^6 106</td> 
 <td>7.183s</td> 
 <td>2.210s</td> 
 <td>102，400bytes</td> 
 <td>4，096bytes</td> 
 </tr> 
 <tr> 
 <td> 1 0 7 10^7 107</td> 
 <td>72.33s</td> 
 <td>23.3s</td> 
 <td>2，945，024bytes</td> 
 <td>2，887，680bytes</td> 
 </tr> 
 </tbody> 
</table>

# 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");
 }

递增：

<table> 
 <thead> 
 <tr> 
 <th>n</th> 
 <th>map(时间)</th> 
 <th>hash_map(时间)</th> 
 <th>map(内存)</th> 
 <th>hash_map(内存)</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> 1 0 5 10^5 105</td> 
 <td>1.504s</td> 
 <td>0.965s</td> 
 <td>3，035，136bytes</td> 
 <td>3，416，064 bytes</td> 
 </tr> 
 <tr> 
 <td> 1 0 6 10^6 106</td> 
 <td>17.9s</td> 
 <td>8.87s</td> 
 <td>29，356，032 bytes</td> 
 <td>30，892，032bytes</td> 
 </tr> 
 </tbody> 
</table>

递减:

<table> 
 <thead> 
 <tr> 
 <th>n</th> 
 <th>map(时间)</th> 
 <th>hash_map(时间)</th> 
 <th>map(内存)</th> 
 <th>hash_map(内存)</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> 1 0 5 10^5 105</td> 
 <td>1.501s</td> 
 <td>0.965s</td> 
 <td>3，035，136bytes</td> 
 <td>3，416，064 bytes</td> 
 </tr> 
 <tr> 
 <td> 1 0 6 10^6 106</td> 
 <td>18.06s</td> 
 <td>8.97s</td> 
 <td>29，356，032 bytes</td> 
 <td>30，892，032bytes</td> 
 </tr> 
 </tbody> 
</table>

可以看出，key不随机后，map是受蛮大的影响，而hash\_map受影响较小。这是因为hash\_map在实现的时候就不依赖key的随机，它自己会对key进行一次线性同余的hash,这种哈希函数的hash结果是随机的。

# 结论 #

当数据量大了以后，hash\_map在时间性能上是全面优于map的，在空间性能上会稍逊于map。  
对于非随机的key,hash\_map在时间性能上更是优于map。