我主要对 map 和 hash_map 的插入、查询、遍历、清除（也就是清空）作了对比。
先来看一下我的源程序（可以直接在Windows下编译）：
<span style="font-family:Courier New;">#include <stdio.h>
#include <hash_map>
#include <map>
#include <time.h>
#include <iostream>
#include <Windows.h>
#include <stdlib.h>
#include <winternl.h>
using namespace std;
#define PACKETS_COUNT 2000000
// Struct of response packet
typedef struct _PACKET_RESPONSE_
{
int packetNum; // The num of current packet
int count404; // The count of 404 Not Found
clock_t clockTick; // The clock tick of the packet that start at the process opened
}PACKET_RESPONSE;
typedef map<unsigned int, _PACKET_RESPONSE_*> RESPONSE_HASH_MAP;
PACKET_RESPONSE **response = {NULL};
// 插入
int insert(RESPONSE_HASH_MAP &responseHashMap)
{
for (int i=0; i<PACKETS_COUNT; i++)
{
PACKET_RESPONSE *newPacketResponse = *(response+i);
newPacketResponse->count404 = i;
newPacketResponse->packetNum = i;
newPacketResponse->clockTick = clock();
responseHashMap.insert(RESPONSE_HASH_MAP::value_type(i, newPacketResponse));
}
cout << "OK!" << endl;
return 0;
}
// 查找
int find(RESPONSE_HASH_MAP::iterator &iter, RESPONSE_HASH_MAP *responseHashMap, int key)
{
iter = responseHashMap->find(key);
if (responseHashMap->end() == iter)
{
cout << "not find!" << endl;
return -1;
}
cout << "find OK !\nKey: " << key << "\ncount404: " << iter->second->count404 << "\npacketNum: " << iter->second->packetNum << "\nclockTick: " << iter->second->clockTick << endl;
}
// 遍历
int visit(RESPONSE_HASH_MAP &responseHashMap)
{
int MaxPacketNum = 0;
RESPONSE_HASH_MAP::iterator iter = responseHashMap.begin();
while (responseHashMap.end() != iter)
{
if (MaxPacketNum < iter->second->packetNum)
{
MaxPacketNum = iter->second->packetNum;
}
++iter;
}
cout << "MaxPacketNum is: " << MaxPacketNum << endl;
return 0;
}
// 清理
int clear(RESPONSE_HASH_MAP &responseHashMap)
{
if (0 != responseHashMap.size())
{
responseHashMap.clear();
}
return 0;
}
DWORD getCpuUsage()
{
MEMORYSTATUS ms;
::GlobalMemoryStatus(&ms);
return ms.dwMemoryLoad;
}
int main()
{
response = new PACKET_RESPONSE*[PACKETS_COUNT];
clock_t t = clock();
for (int i=0; i<PACKETS_COUNT; i++)
{
response[i] = new PACKET_RESPONSE;
}
cout << "======================> clock is:" << clock()-t << endl;
RESPONSE_HASH_MAP responseHashMap;
RESPONSE_HASH_MAP::iterator iter = responseHashMap.begin();
DWORD dwStart = getCpuUsage();
clock_t start = clock();
insert(responseHashMap);
cout << "====> insert clock is: " << clock()-start << " ms" << endl;
DWORD dwInsert = getCpuUsage();
cout << "insert 内存使用率为: " << dwInsert-dwStart << "%" << endl;
RESPONSE_HASH_MAP::iterator it = responseHashMap.begin();
clock_t eraseStart = clock();
for (int i=0; i<1000; i++)
{
PACKET_RESPONSE *newNode = new PACKET_RESPONSE;
newNode->packetNum = PACKETS_COUNT + i;
newNode->count404 = PACKETS_COUNT + i;
newNode->clockTick = clock();
responseHashMap.insert(RESPONSE_HASH_MAP::value_type(PACKETS_COUNT + i, newNode));
it = responseHashMap.erase(it);
}
cout << "=====> erase clock is: " << clock()-eraseStart << " ms" << endl;
clock_t findStart = clock();
find(iter, &responseHashMap, PACKETS_COUNT-1);
cout << "====> find clock is: " << clock()-findStart << " ms" << endl;
DWORD dwFind = getCpuUsage();
cout << "find 内存使用率为: " << dwFind - dwInsert << "%" << endl;
clock_t visitStart = clock();
visit(responseHashMap);
cout << "====> visit clock is: " << clock()-visitStart << " ms" << endl;
DWORD dwVisit = getCpuUsage();
cout << "visit 内存使用率为：" << dwVisit << "%" << endl;
clock_t clearStart = clock();
clear(responseHashMap);
cout << "======> clear clock is: " << clock()-clearStart << " ms" << endl;
DWORD dwClear = getCpuUsage();
cout << "clear 内存使用率为：" << dwClear << "%" << endl;
return 0;
}</span>
由于我是验证 map 与 hash_map 的性能，所以有些变量的命名是按照之前 hash_map 来命名的，不要觉得奇怪。
我把验证的结果贴出来。
<usigned int, PACKET_RESPONSE*> -- 自己管理内存。
插入 查询 遍历
200条 4ms 2ms 1ms hash_map
2ms 2ms 1ms map
2000条 33ms 3ms 3ms hash_map
17ms 2ms 3ms map
20000条 400ms 2ms 21ms hash_map
178ms 2ms 27ms map
200000条 10s 3ms 185ms hash_map
2s 3ms 250ms map
2000000条 8min 3ms 1.8s hash_map
22s 4ms 2.6s map
<usigned int, PACKET_RESPONSE> -- 把内存交给 map 或者 hash_map
插入 查询 遍历
200条 6ms 2ms 1ms hash_map
2ms 2ms 1ms map
2000条 33ms 3ms 3ms hash_map
17ms 2ms 3ms map
20000条 400ms 3ms 21ms hash_map
178ms 2ms 27ms map
200000条 10s 3ms 185ms hash_map
2s 3ms 250ms map
2000000条 9min 3ms 1.7s hash_map
22s 3ms 2.5s map
<usigned int, int> -- value 类型为内置类型
插入 查询 遍历
200条 6ms 1ms 1ms hash_map
2ms 2ms 1ms map
2000条 34ms 1ms 3ms hash_map
17ms 1ms 3ms map
20000条 400ms 1ms 22ms hash_map
175ms 2ms 27ms map
200000条 10s 1ms 186ms hash_map
2s 1ms 249ms map
2000000条 9min 1ms 1.8s hash_map
22s 2ms 2.5s map
<usigned int, PACKET_RESPONSE*> --自己管理内存 批量申请内存
插入 查询 遍历 清除
200条 4ms 2ms 1ms 1ms hash_map
2ms 2ms 1ms 0ms map
2000条 31ms 2ms 3ms 34ms hash_map
15ms 3ms 4ms 1ms map
20000条 400ms 3ms 21ms 1.3s hash_map
186ms 3ms 35ms 10ms map
200000条 10s 2ms 183ms 74s hash_map
2.1s 4ms 288ms 110ms map
2000000条 8min 2ms 1.7s 1h hash_map
22s 3ms 2.5s 900ms map
我是根据 value 的类型不同而作的验证。从结果中可以看出，map 的插入、清除性能远比 hash_map 的要高，尤其是清除，大家看最后一个，清除 200W 条的记录时，map 只花了900ms，而 hash_map 却花了一个小时，我开始还以为程序有问题，后来我花了几个小时验证了好几遍，都是这样。而 hash_map 的遍历性能比 map 要高。如果你使用的时候频繁插入或者频繁清除的话，就选择 map，如果你频繁的遍历那就建议使用 hash_map。还有，这个跟 value 的类型没多少关系，我开始在网上看有些人说 map 对内置类型的处理性能比 hash_map 高，而对于自定义类型的处理 hash_map 要高，事实证明，不是这样的。
后来我怀疑是 new 操作影响了性能，所以我用了一个批量申请内存，但是从验证的结果来看，这个对性能没多大的影响。如果你要自己管理内存的话，我建议还是批量申请内存好。如果你不想自己管理内存，那就把内存管理交给 map 或者 hash_map，它们有着一套非常不错的内存管理机制，当它们释放完内存后，并不是交给 ISO，而是留着自己下次使用。这个就是我上面<usigned int, PACKET_RESPONSE>所列出的情况，是将自定义的结构体直接插入 map 或 hash_map中。
我上面的代码是使用了批量申请内存，然后自己管理内存的。如果大家想看看其它的情况的话，可以自己改下代码。
希望对大家有所帮助，还有如果有人觉得哪里不对的话可以告诉我，大家共同进步。
13 个解决方案
#1
记得那个谁说，VC的hash_map有问题。
#2
这个测试用例想写好还是有要求的. 建议你去专门的性能评测网站看看别人写的测试用例.
#4
我还不知道hash_map呢
#5
学习了，以前都不知道有unordered_map
#6
shuoshuo ni yong de vc banben?
#7
hash_map本质上就是数组啊，数组的删除必然是一个耗时很久的事情嘛，map本质上就是红黑树啊，红黑树本质上就是二叉树啊，二叉树本质上就是链表啊，只是多了一个parent字段而已啊，链表的删除自然要远远优于数组啊，说到搜索，也要看你使用什么算法来映射hash_map啊，如果算法使用得当，自然是很快的，如果你经常不能命中，而要挂接链表，那这个查找速度也不快的说，map的劣势也很明显，他的比较算法在很多类型上的时间复杂度要远超hash_map的映射算法，并且他要比较log2N次，hash_map只要计算一次，同时如果命中之后，根本不需要再遍历。
#8
我用VS2010，CPU是i3的。
还有，我要向大家说声抱歉，之前编译的版本是DEBUG版本，所以性能才会这么低。
大家测性能的时候一定要用RELEASE版本，这样性能会提高很多。
我换成RELEASE版本就好多了。具体结果我就不贴出来了。- -
还有，我要向大家说声抱歉，之前编译的版本是DEBUG版本，所以性能才会这么低。
大家测性能的时候一定要用RELEASE版本，这样性能会提高很多。
我换成RELEASE版本就好多了。具体结果我就不贴出来了。- -
#9
不要用hash_map，用unordered_map
#10
据我所知，unordered_map在一般的情况下跟hash_map的性能差不多，只是unordered_map支持string为key，也支持更多的自定义类型的key。其它的和 hash_map 差不多。
#11
最大的区别：一个是标准容器，一个是非标准，差太多了。
#12
用过map和hash_map没用过unordered_map
#13
unordered_map虽然号称是标准容器，但在vs2008里面没有
#1
记得那个谁说，VC的hash_map有问题。
#2
这个测试用例想写好还是有要求的. 建议你去专门的性能评测网站看看别人写的测试用例.
#3
#4
我还不知道hash_map呢
#5
学习了，以前都不知道有unordered_map
#6
shuoshuo ni yong de vc banben?
#7
hash_map本质上就是数组啊，数组的删除必然是一个耗时很久的事情嘛，map本质上就是红黑树啊，红黑树本质上就是二叉树啊，二叉树本质上就是链表啊，只是多了一个parent字段而已啊，链表的删除自然要远远优于数组啊，说到搜索，也要看你使用什么算法来映射hash_map啊，如果算法使用得当，自然是很快的，如果你经常不能命中，而要挂接链表，那这个查找速度也不快的说，map的劣势也很明显，他的比较算法在很多类型上的时间复杂度要远超hash_map的映射算法，并且他要比较log2N次，hash_map只要计算一次，同时如果命中之后，根本不需要再遍历。
#8
我用VS2010，CPU是i3的。
还有，我要向大家说声抱歉，之前编译的版本是DEBUG版本，所以性能才会这么低。
大家测性能的时候一定要用RELEASE版本，这样性能会提高很多。
我换成RELEASE版本就好多了。具体结果我就不贴出来了。- -
还有，我要向大家说声抱歉，之前编译的版本是DEBUG版本，所以性能才会这么低。
大家测性能的时候一定要用RELEASE版本，这样性能会提高很多。
我换成RELEASE版本就好多了。具体结果我就不贴出来了。- -
#9
不要用hash_map，用unordered_map
#10
据我所知，unordered_map在一般的情况下跟hash_map的性能差不多，只是unordered_map支持string为key，也支持更多的自定义类型的key。其它的和 hash_map 差不多。
#11
最大的区别：一个是标准容器，一个是非标准，差太多了。
#12
用过map和hash_map没用过unordered_map
#13
unordered_map虽然号称是标准容器，但在vs2008里面没有