All notes
StlAlgorithms

Map, unordered_map

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)。