技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置：首页 --> 算法 --> 关于哈希map奇慢无比的原因定位

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

浏览:3933次  出处信息

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

建议继续学习：

  1. 一致性哈希算法及其在分布式系统中的应用    (阅读：7933)
  2. 分布式哈希和一致性哈希    (阅读：7662)
  3. Hadoop的map/reduce作业输入非UTF-8编码数据的处理原理    (阅读：4598)
  4. PHP哈希表碰撞攻击原理    (阅读：4016)
  5. 浅析Linux Kernel 哈希路由表实现(一)    (阅读：3190)
  6. Java Hash Algorithm Collision Practice （JAVA哈希算法冲突实践）    (阅读：3059)
  7. MySQL B+树索引和哈希索引的区别    (阅读：3076)
  8. Cuckoo Filter：设计与实现    (阅读：3066)
  9. 一致性哈希算法(consistent hashing)    (阅读：2963)
  10. 某分布式应用实践一致性哈希的一些问题    (阅读：2342)
QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习
<< 前一篇：蛋疼研究之怎样刷屏最快？
后一篇：循环、迭代、遍历和递归 >>
文章信息
  • 作者：Dante    来源： Vimer
  • 标签： map 哈希
  • 发布时间：2011-01-27 22:55:08
© 2009 - 2024 by blogread.cn 微博：@IT技术博客大学习

京ICP备15002552号-1