关于哈希map奇慢无比的原因定位
浏览:3917次 出处信息
最近有一个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其实大部分情况够用了,不必过分追求效率。
另:
代码下载
建议继续学习:
- 一致性哈希算法及其在分布式系统中的应用 (阅读:7911)
- 分布式哈希和一致性哈希 (阅读:7634)
- Hadoop的map/reduce作业输入非UTF-8编码数据的处理原理 (阅读:4578)
- PHP哈希表碰撞攻击原理 (阅读:3981)
- 浅析Linux Kernel 哈希路由表实现(一) (阅读:3171)
- Java Hash Algorithm Collision Practice (JAVA哈希算法冲突实践) (阅读:3038)
- MySQL B+树索引和哈希索引的区别 (阅读:3045)
- Cuckoo Filter:设计与实现 (阅读:3036)
- 一致性哈希算法(consistent hashing) (阅读:2937)
- 某分布式应用实践一致性哈希的一些问题 (阅读:2320)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:蛋疼研究之怎样刷屏最快?
后一篇:循环、迭代、遍历和递归 >>
文章信息
- 作者:Dante 来源: Vimer
- 标签: map 哈希
- 发布时间:2011-01-27 22:55:08
建议继续学习
近3天十大热文
- [68] Go Reflect 性能
- [68] 如何拿下简短的域名
- [67] Oracle MTS模式下 进程地址与会话信
- [62] IOS安全–浅谈关于IOS加固的几种方法
- [61] 图书馆的世界纪录
- [60] 【社会化设计】自我(self)部分――欢迎区
- [58] android 开发入门
- [56] 视觉调整-设计师 vs. 逻辑
- [49] 给自己的字体课(一)——英文字体基础
- [48] 读书笔记-壹百度:百度十年千倍的29条法则