map/unordered_map原理和使用整理_c++unorderedmap原理

作者：小桥流水78 | 2024-08-05 15:57:27

踩

c++unorderedmap原理

1.结论

新版的hash_map都是unordered_map了，这里只说unordered_map和map.

运行效率方面：unordered_map最高，而map效率较低但提供了稳定效率和有序的序列。

占用内存方面：map内存占用略低，unordered_map内存占用略高,而且是线性成比例的。

需要无序容器，快速查找删除，不担心略高的内存时用unordered_map；有序容器稳定查找删除效率，内存很在意时候用map。

2.原理

map的内部实现是二叉平衡树(红黑树)；hash_map内部是一个hash_table一般是由一个大vector，vector元素节点可挂接链表来解决冲突，来实现.

hash_map 其插入过程是：

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

其取值过程是:

得到key
通过hash函数得到hash值
得到桶号(一般都为hash值对桶数求模)
比较桶的内部元素是否与key相等，若都不相等，则没有找到。
取出相等的记录的value。

hash_map中直接地址用hash函数生成，解决冲突，用比较函数解决。

3.内存占用测试

测试代码：

测试条件window下，VS2015 C++。string为key, int 为value。

1.UnorderMap:


#include <unordered_map>  
#include <string>  
#include <iostream>
#include <windows.h>
#include <psapi.h>  
#pragma comment(lib,"psapi.lib") 
using namespace std;
using namespace stdext;
void showMemoryInfo(void)
{
	HANDLE handle = GetCurrentProcess();
	PROCESS_MEMORY_COUNTERS pmc;
	GetProcessMemoryInfo(handle, &pmc, sizeof(pmc));
	cout << "Memory Use:" << pmc.WorkingSetSize/1024.0f << "KB/" << pmc.PeakWorkingSetSize/1024.0f << "KB, Virtual Memory Use:" << pmc.PagefileUsage/1024.0f << "KB/" << pmc.PeakPagefileUsage/1024.0f << "KB" << endl;
}
 
//define the class  
/*-------------------------------------------*/
/*函数类
*作为hash_map的hash函数
*string没有默认的hash函数
*/
class str_hash {
public:
	size_t operator()(const string& str) const
	{
		unsigned long __h = 0;
		for (size_t i = 0; i < str.size(); i++)
			__h = 5 * __h + str[i];
		return size_t(__h);
	}
};
 
/*-------------------------------------------*/
/*函数类
*作为hash_map的比较函数 )
*(查找的时候不同的key往往可能对用到相同的hash值
*/
class str_compare
{
public:
	bool operator()(const string& str1, const string& str2)const
	{
		return   str1 == str2;
	}
};
 
struct CharLess : public binary_function<const string&, const string&, bool>
{
public:
	result_type operator()(const first_argument_type& _Left,

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小桥流水78/article/detail/933048