Vimer的程序世界

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