最后更新于 .

最近有一个server在重启的时候总要花费5分钟左右来加载配置文件,导致外网服务不可用,今天和几个同事一起研究了一下,总算找到了问题所在. 抽象出代码如下:

#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的小于符号:

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的定义改为:

map<int, int> imap1;
map<StTest, int> StTestMap1;

运行结果如下:

cost time : 0.04806
StTestMap1 time cost : 0.06981

用map就没问题,所以怀疑到了哈希函数的身上,我们发现StTest的哈希函数居然是如下定义:

bool operator()(const StTest &lhs)const
{
    return this->dd == lhs.dd;
}

bool型,一直返回1!也就是说所有的节点都放到了一个桶里! 找到了原因,我们来改一下代码:

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

结果正常了,可能由于之前的同事错把

size_t operator()()const
{
    return dd;
}

当成哈希函数,所以才会出现如下问题。使用哈希map的时候,哈希函数的离散情况是很关键的,希望这篇文章能帮助大家避免犯类似的错误。 另外用红黑树map其实大部分情况够用了,不必过分追求效率。 另: 代码下载

Pingbacks

Pingbacks已打开。

Trackbacks

引用地址

评论

  1. 站长工具

    站长工具 on #

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

    Reply

  2. 葡萄酒

    葡萄酒 on #

    来踩踩 春节快乐

    Reply

  3. 青岛西点

    青岛西点 on #

    不太懂==~~~~(&gt;_&lt;)~~~~

    Reply

  4. 雨碎江南

    雨碎江南 on #

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

    Reply

    1. Dante

      Dante on #

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

      Reply

  5. 站长工具

    站长工具 on #

    博主,兔年快乐!

    Reply

    1. Dante

      Dante on #

      哈哈,兔年快乐!

      Reply

  6. 宁波网络公司

    宁波网络公司 on #

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

    Reply

  7. 小小vimer

    小小vimer on #

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

    Reply

    1. Dante

      Dante on #

      这个,吓到我了。。。

      Reply

  8. http://www.jdzstx.com

    http://www.jdzstx.com on #

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

    Reply

发表评论