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

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

时间:2021-07-01 10:21:17 帮助过:34人阅读

回复内容:

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. 内存布局会影响内存局部性,对性能会有影响
补一句,红黑树意味着对于键值它是有序存储,当你需要查找某一范围的键值时,非常方便。用时依然为(logN)。
反之,若使用哈希,你将不得不去遍历整个值空间,用时(N)。 大多数时候,我们并不需要这个“有序”,即使在某些特殊情况下,我们需要的“有序”,也不是“动态且有序”,这里有个 0开销支持排序的 gold_hash_map,通用,并且比 std::unordered_xxx 和 google 的 spasre_xxx, dense_xxx 更快更省内存 标准规定map的元素必须是有序的,在满足标准的情况下,才能考虑效率。用散列表不能保证元素是有序的,所以不能用。 map,速度稳定,而且有序;
hashtable,时而比map快一点,时而比map慢无数倍。挑食(找不到好的hash),易受骗(故意的数据碰撞)。

非实时性场合,可以选择hashtable,因为从统计学上看它比map快;
实时性场合,只能选map,因为他不会像hashtable那样有时慢得离谱。
  1. 侯捷老师在《STL源码剖析》一书的第5章提到了:hash table (散列表)及其衍生容器相当重要.它们未被纳入C++标准的原因是,提案太迟了。下一代c++标准程序库很有可能会纳入它们。
  2. 在SGI STL中提供了hash table(散列表),以及以此hash table为底层机制而完成的hash_set (散列集合)、hash_map (散列映射表)、hash_multiset (散列多键集合)、hash_multimap(散列多键映射表)。在新的c++ stl中也引入了unorder_map。
  3. 关于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时间也许是一个很小的系数,而常数时间也许是一个很大的系数。 试一下这几个函数,下次你对顺序没有要求时,你就会想用哈希而不是红黑树了

人气教程排行