最近有一个server在重启的时候总要花费5分钟左右来加载配置文件，导致外网服务不可用，今天和几个同事一起研究了一下，总算找到了问题所在.
抽象出代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#include <sys/time.h>
#include <stdio.h>
#include <memory.h>
#include <map>
#include <string>
#if 0
#include <hash_map.h>
#else
#include <tr1/unordered_map>
#define hash_map std::tr1::unordered_map
#endif
using namespace std;
class CTimer
{
public:
CTimer()
{
memset(&tpStart, 0, sizeof(tpStart));
memset(&tpEnd, 0, sizeof(tpEnd));
}
void Begin()
{
gettimeofday(&tpStart, NULL);
}
float GetElapseTime()
{
gettimeofday(&tpEnd, NULL);
float timecost = 0.0f;
timecost = tpEnd.tv_sec - tpStart.tv_sec + (float)(tpEnd.tv_usec-tpStart.tv_usec)/1000000;
return timecost;
}
private:
struct timeval tpStart;
struct timeval tpEnd;
};
struct StTest
{
int dd;
size_t operator()()const
{
return dd;
}
bool operator == (const StTest &lhs)const
{
return this->dd == lhs.dd;
}
bool operator()(const StTest &lhs)const
{
return this->dd == lhs.dd;
}
};
const int cnt = 40000;
int main()
{
hash_map<int, int> imap1;
hash_map<StTest, int, StTest> StTestMap1;
CTimer t1;
t1.Begin();
for (size_t i=0; i<cnt; ++i)
{
imap1[i] = i;
}
printf("cost time : %5.5f\n", t1.GetElapseTime());
StTest st;
t1.Begin();
for (size_t i=0; i<cnt; ++i)
{
st.dd = i;
StTestMap1[st] = i;
}
printf("StTestMap1 time cost : %5.5f\n",t1.GetElapseTime());
return 0;
}
|
对imap1和StTestMap1两个map分别插入40000次，运行结果如下:
cost time : 0.02598
StTestMap1 time cost : 27.84836
StTestMap1的插入居然消耗了27秒，太奇怪了!难道真的hash_map的实现有问题？我们来换成map试一下.
先重载一下StTest的小于符号:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
struct StTest
{
int dd;
size_t operator()()const
{
return dd;
}
bool operator == (const StTest &lhs)const
{
return this->dd == lhs.dd;
}
bool operator()(const StTest &lhs)const
{
return this->dd == lhs.dd;
}
bool operator < (const StTest &lhs)const
{
return this->dd < lhs.dd;
}
};
|
两个map的定义改为:
1
2
|
map<int, int> imap1;
map<StTest, int> StTestMap1;
|
运行结果如下:
cost time : 0.04806
StTestMap1 time cost : 0.06981
用map就没问题，所以怀疑到了哈希函数的身上，我们发现StTest的哈希函数居然是如下定义:
1
2
3
4
|
bool operator()(const StTest &lhs)const
{
return this->dd == lhs.dd;
}
|
bool型，一直返回1！也就是说所有的节点都放到了一个桶里！
找到了原因，我们来改一下代码:
1
2
3
4
5
6
7
8
9
10
11
12
|
struct StTest
{
int dd;
bool operator == (const StTest &lhs)const
{
return this->dd == lhs.dd;
}
size_t operator()(const StTest &lhs)const
{
return lhs.dd;
}
};
|
运行结果如下:
cost time : 0.02406
StTestMap1 time cost : 0.02213
结果正常了，可能由于之前的同事错把
1
2
3
4
|
size_t operator()()const
{
return dd;
}
|
当成哈希函数，所以才会出现如下问题。使用哈希map的时候，哈希函数的离散情况是很关键的，希望这篇文章能帮助大家避免犯类似的错误。
另外用红黑树map其实大部分情况够用了，不必过分追求效率。
另:
代码下载
