首页 > 编程语言 > 详细

C++ STL中的map用红黑树实现,搜索效率是O(lgN),为什么不像python一样用散列表从而获得常数级搜索效率呢?

时间:2016-04-27 12:19:58      阅读:176      评论:0      收藏:0      [点我收藏+]

C++ STL中的标准规定:
 map, 有序
 unordered_map,无序,这个就是用散列表实现

 

谈谈hashmap和map的区别,我们知道hashmap是平均O(1),map是平均O(lnN)的,实践上是不是hashmap一定优于map呢?这里面有几个因素要考虑:
  1. hashmap的内存效率比map差,这是显而易见的
  2. map的查找效率实践上是非常高的,如在1M数据中查找一个元素,需要多少次比较呢?20次。
  3. map的查找效率比hashmap稳定。
  4. hashmap查找时候要算hash,这个最坏时间复杂度是O(M)(M是key字符串的长度),如果你的key非常非常非常非常非常非常……长,基于比较的map通常只使用头几个字符进行比较,而hashmap要O(M)地算出hash
  5. 内存布局会影响内存局部性,对性能会有影响



C++ STL中的map用红黑树实现,搜索效率是O(lgN),为什么不像python一样用散列表从而获得常数级搜索效率呢?

原文:http://www.cnblogs.com/gofighting/p/5438021.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!