关于使用STL的红黑树map还是hashmap的问题

关于使用STL的红黑树map还是hashmap的问题

最近在修改一个代理机server，增加url rewrite的功能，由于其单机的访问量很高，20000/s左右，对性能要求很高，所以在做url映射的时候，纠结在用map还是hashmap存储映射的问题上。

于是做了一个简单的测试，对与map和hashmap（我们用unordered_map），循环10000*24次，map大小是12（因为目前预估会配置的url个数是12左右）。
部分代码如下：

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include "markupstl.h"
#include <tr1/unordered_map>
#include <sys/time.h>
using namespace std;
#define hashmap std::tr1::unordered_map
#define CONFIG_FILE_PATH "./urlconfig.xml"
map<string,string> g_mapUrl;
hashmap<string,string> g_hashmapUrl;
struct timeval g_tpstart,g_tpend;
int timeuse;
gettimeofday(&g_tpstart,NULL);
for(int i = 0;i<10000;++i)
{
    for(unsigned j = 0;j<g_vec.size();++j)
    {
        if (g_mapUrl.find(g_vec[j]) != g_mapUrl.end())
        {
            temp = g_mapUrl[g_vec[j]];
            //cout<<temp<<endl;
        }
    }
}
gettimeofday(&g_tpend,NULL);
timeuse=1000000*(g_tpend.tv_sec-g_tpstart.tv_sec)+g_tpend.tv_usec-g_tpstart.tv_usec;
printf("map timeuse:%d\n",timeuse);
gettimeofday(&g_tpstart,NULL);
for(int i = 0;i<10000;++i)
{
    for(unsigned j = 0;j<g_vec.size();++j)
    {
        if (g_hashmapUrl.find(g_vec[j]) != g_hashmapUrl.end())
        {
            temp = g_hashmapUrl[g_vec[j]];
            //cout<<temp<<endl;
        }
    }
}
gettimeofday(&g_tpend,NULL);
timeuse=1000000*(g_tpend.tv_sec-g_tpstart.tv_sec)+g_tpend.tv_usec-g_tpstart.tv_usec;
printf("hashmap timeuse:%d\n",timeuse);

url映射是存在配置文件中的，12个左右：

<url clean="/user/info" ugly="/cgi-bin/xyoapp/xyoapp_get_userinfo.cgi" />
<url clean="/user/multi_info" ugly="/cgi-bin/xyoapp/xyoapp_multi_info.cgi" />
<url clean="/user/is_setup" ugly="/cgi-bin/xyoapp/xyoapp_get_issetuped.cgi" />
<url clean="/user/emotion" ugly="/cgi-bin/xyoapp/xyoapp_get_emotion.cgi" />
<url clean="/relation/is_friend" ugly="/cgi-bin/xyoapp/xyoapp_get_isrelation.cgi" />
<url clean="/relation/friends" ugly="/cgi-bin/xyoapp/xyoapp_get_relationinfo.cgi" />
<url clean="/network/classes" ugly="/cgi-bin/xyoapp/xyoapp_get_joinclass.cgi" />
<url clean="/pay/balance" ugly="/cgi-bin/xyoapp/xyoapp_pay_get.cgi" />
<url clean="/pay/pre_pay" ugly="/cgi-bin/xyoapp/xyoapp_pay_pay.cgi" />
<url clean="/pay/confirm" ugly="/cgi-bin/xyoapp/xyoapp_pay_confirm.cgi" />
<url clean="/pay/cancel" ugly="/cgi-bin/xyoapp/xyoapp_pay_cancel.cgi" />
<url clean="/pay/is_vip" ugly="/cgi-bin/xyoapp/xyoapp_pay_showvip.cgi" />

运行后得到的结果是：

map timeuse:392035
hashmap timeuse:480670

有点出乎意料，hashmap居然比map的红黑树方式还要慢一点的。

再测试一下，我把map的数据量调大，变成1000左右。再次运行：

map timeuse:1085809
hashmap timeuse:453852

这个时候，hashmap几乎比map快了一倍还要多，不过基于我目前map的大小只有12左右，所以用红黑树的map就足够了。

刚才又上网搜了一下红黑树，发现大学学的算法是忘记的一干二净了，抽时间得补习一下了。。。

附：源代码下载

建议继续学习：