正文

使用map和hash_map的效率问题(转)2010-04-18 10:28:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/yuqiexing/50949.html

分享到:

这篇文章来自我今天碰到的一个问题,一个朋友问我使用map和hash_map的效率问题,虽然我也了解一些,但是我不敢直接告诉朋友,因为我怕我说错了,通过我查询一些帖子,我这里做一个总结!内容分别来自
alvin_lee ,codeproject,codeguru.baidu等等!

先看看alvin_lee 朋友做的解析,我觉得还是很正确的,从算法角度阐述了他们之间的问题!


实际上这个问题不光C++会遇到,其他所有语言的标准容器的实现及选择上都是要考虑的。做应用程序你可能觉得影响不大,但是写算法或者核心代码就要小心了。今天改进代码,顺便又来温习基础功课了。

  还记得Herb Sutter那极有味道的《C++对话系列》么,在其中《产生真正的hash对象》这个故事里就讲了map的选择。顺便回顾一下,也讲一下我在实用中的理解。

  选择map容器,是为了更快的从关键字查找到相关的对象。与使用list这样的线性表容器相比,一可以简化查找的算法,二可以使任意的关键字做索引,并与目标对象配对,优化查找算法。在C++的STL中map是使用树来做查找算法,这种算法差不多相当与list线性容器的折半查找的效率一样,都是O(log2N),而list就没有map这样易定制和操作了。

  相比hash_map,hash_map使用hash表来排列配对,hash表是使用关键字来计算表位置。当这个表的大小合适,并且计算算法合适的情况下,hash表的算法复杂度为O(1)的,但是这是理想的情况下的,如果hash表的关键字计算与表位置存在冲突,那么最坏的复杂度为O(n)。

  那么有了这样的认识,我们应该怎么样选用算法呢?前两天看Python文章的时候,不知道哪个小子说Python的map比c++的map快,如何如何的。但是他并不知道Python是默认使用的hash_map,而且这些语言特征本质上是使用c/c++写出来的,问题在与算法和手段,而不是在于语言本身的优劣,你熟悉了各种算法,各种语言的细节、设计思想,还能在这偏激的嚷嚷孰好孰坏(片面与偏激的看待事物只能表明愚昧与无知,任何事物都有存在的价值,包括技术)。显然C++的STL默认使用树结构来实现map,是有考究的。

  树查找,在总查找效率上比不上hash表,但是它很稳定,它的算法复杂度不会出现波动。在一次查找中,你可以断定它最坏的情况下其复杂度不会超过O(log2N)。而hash表就不一样,是O(1),还是O(N),或者在其之间,你并不能把握。假若你在开发一个供外部调用的接口,其内部有关键字的查找,但是这个接口调用并不频繁,你是会希望其调用速度快、但不稳定呢,还是希望其调用时间平均、且稳定呢。反之假若你的程序需要查找一个关键字,这个操作非常频繁,你希望这些操作在总体上的时间较短,那么hash表查询在总时间上会比其他要短,平均操作时间也会短。这里就需要权衡了。

  这里总结一下,选用map还是hash_map,关键是看关键字查询操作次数,以及你所需要保证的是查询总体时间还是单个查询的时间。如果是要很多次操作,要求其整体效率,那么使用hash_map,平均处理时间短。如果是少数次的操作,使用hash_map可能造成不确定的O(N),那么使用平均处理时间相对较慢、单次处理时间恒定的map,考虑整体稳定性应该要高于整体效率,因为前提在操作次数较少。如果在一次流程中,使用hash_map的少数操作产生一个最坏情况O(N),那么hash_map的优势也因此丧尽了。

阅读(3274) | 评论(1)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册