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

回复内容：

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时间也许是一个很小的系数，而常数时间也许是一个很大的系数。试一下这几个函数，下次你对顺序没有要求时，你就会想用哈希而不是红黑树了