关于哈希map奇慢无比的原因定位

Published on 一月 27, 2011
3,602

最近有一个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其实大部分情况够用了，不必过分追求效率。
另:
代码下载





原创文章，版权所有。转载请注明：转载自Vimer的程序世界 [ http://www.vimer.cn ]

本文链接地址: http://www.vimer.cn/?p=1971

Posted in: C/C++, 算法 by Dante,3,602 views Tags: , , , ,


较旧一篇«
»较新一篇


11 个评论 在 “关于哈希map奇慢无比的原因定位”

  1. 站长工具 说：
    2011年01月28日 于 2:32 上午

    昨天在功能升级过程中发现搜狗的网站评级系统升级了，由原来100分制变成10分制，而且增加了专用查询服务器，查询链接格式为http://rank.ie.sogou.com/sogourank.php?ur=http://www.wsprite.com/，特来提醒朋友，快试试自己的博客和朋友的博客是属于哪个级别。

    [回复]

  2. 葡萄酒 说：
    2011年01月31日 于 1:18 下午

    来踩踩 春节快乐

    [回复]

  3. 青岛西点 说：
    2011年01月31日 于 1:18 下午

    不太懂==~~~~(>_<)~~~~

    [回复]

  4. 雨碎江南 说：
    2011年01月31日 于 8:19 下午

    妈呀…
    从来没有见过这么牛逼的散列函数.

    [回复]

    Dante 回复:
    二月 3rd, 2011 at 12:40 上午

    同感……，复杂的问题背后总是一个简单的原因……

    [回复]

  5. 站长工具 说：
    2011年02月1日 于 12:14 下午

    博主，兔年快乐！

    [回复]

    Dante 回复:
    二月 3rd, 2011 at 12:38 上午

    哈哈，兔年快乐！

    [回复]

  6. 宁波网络公司 说：
    2011年02月7日 于 2:27 下午

    博主解决了一个大问题阿～

    [回复]

  7. 小小vimer 说：
    2011年05月25日 于 6:31 下午

    博主你简直是我心目中的神

    [回复]

    Dante 回复:
    五月 26th, 2011 at 11:54 下午

    这个，吓到我了。。。

    [回复]

  8. http://www.jdzstx.com 说：
    2011年06月2日 于 2:37 下午

    博主解决了一个大问题阿～

    [回复]

我要评论

*

*