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

回复内容: c++ stl中的标准规定:* map, 有序* unordered_map,无序,这个就是用散列表实现 谈谈hashmap和map的区别,我们知道hashmap是平均o(1),map是平均o(lnn)的,实践上是不是hashmap一定优于map呢?这里面有几个因素要考虑:hashmap的内存效率比map差,这是显而易见的map的查找效率实践上是非常高的,如在1m数据中查找一个元素,需要多少次比较呢?20次。map的查找效率比hashmap稳定。hashmap查找时候要算hash,这个最坏时间复杂度是o(m)(m是key字符串的长度),如果你的key非常非常非常非常非常非常……长,基于比较的map通常只使用头几个字符进行比较,而hashmap要o(m)地算出hash内存布局会影响内存局部性,对性能会有影响 补一句,红黑树意味着对于键值它是有序存储,当你需要查找某一范围的键值时,非常方便。用时依然为(logn)。反之,若使用哈希,你将不得不去遍历整个值空间,用时(n)。 大多数时候,我们并不需要这个“有序”,即使在某些特殊情况下,我们需要的“有序”,也不是“动态且有序”,这里有个 0开销支持排序的 gold_hash_map,通用,并且比 std::unordered_xxx 和 google 的 spasre_xxx, dense_xxx 更快更省内存 标准规定map的元素必须是有序的,在满足标准的情况下,才能考虑效率。用散列表不能保证元素是有序的,所以不能用。 map,速度稳定,而且有序;hashtable,时而比map快一点,时而比map慢无数倍。挑食(找不到好的hash),易受骗(故意的数据碰撞)。非实时性场合,可以选择hashtable,因为从统计学上看它比map快;实时性场合,只能选map,因为他不会像hashtable那样有时慢得离谱。 侯捷老师在《stl源码剖析》一书的第5章提到了:hash table (散列表)及其衍生容器相当重要.它们未被纳入c++标准的原因是,提案太迟了。下一代c++标准程序库很有可能会纳入它们。在sgi stl中提供了hash table(散列表),以及以此hash table为底层机制而完成的hash_set (散列集合)、hash_map (散列映射表)、hash_multiset (散列多键集合)、hash_multimap(散列多键映射表)。在新的c++ stl中也引入了unorder_map。关于map与unordered_map的时间复杂度(查找)与空间复杂度请看stack overflow的答案c++ - is there any advantage of using map over unordered_map in case of trivial keys?答案主要是:1、map是有序的,unordered_map是无序的2、两者之间的查找速度不同(log(n)和n)3、由于hash要控制负载率在0-1之间,所以unordered_map消耗空间更大。具体的时间与空间消耗: hash是普通dictionary抽象数据类型的一种实现,rbt是ordered dictionary抽象数据类型的一种实现。普通dictionary只支持search、insert、delete,ordered dictionary除了那三个操作外,还支持一些导航类的操作,如和一个给定key最邻近的key,最大key、最小key这些操作。两种dictionary的实现各有适用场景。 可能当初定c++标准库的时候,hash table还不流行。现在11的标准库加入了基于hash的unordered_set和unordered_map。另外,光看所谓的算法复杂度是不够的。log时间也许是一个很小的系数,而常数时间也许是一个很大的系数。 试一下这几个函数,下次你对顺序没有要求时,你就会想用哈希而不是红黑树了试一下这几个函数,下次你对顺序没有要求时,你就会想用哈希而不是红黑树了

分享这篇文章:
收藏+0