使用map和hash_map的效率问题 - km的小天地 - ITeye技术网站

使用map和hash_map的效率问题 - km的小天地 - ITeye技术网站

1，选择map容器，是为了更快的从关键字查找到相关的对象。
与使用list这样的线性表容器相比，一可以简化查找的算法，二可以使任意的关键字做索引，并与目标对象配对，优化查找算法。
在C++的STL中map是使用树来做查找算法，这种算法差不多相当与list线性容器的折半查找的效率一样，都是 O(log2N)，而list就没有map这样易定制和操作了。

2，相比map，hash_map使用hash表来排列配对，hash表是使用关键字来计算表位置。当这个表的大小合适，并且计算算法合适的情况下，hash表的算法复杂度为O(1)的，但是这是理想的情况下的，如果hash表的关键字计算与表位置存在冲突，那么最坏的复杂度为O(n)。

3，树查找，在总查找效率上比不上hash表，但是它很稳定，它的算法复杂度不会出现波动。在一次查找中，你可以断定它最坏的情况下其复杂度不会超过 O(log2N)。而hash表就不一样，是O(1)，还是O(N)，或者在其之间，你并不能把握。

4，总结:
选用map还是hash_map，关键是看关键字查询操作次数，以及你所需要保证的是查询总体时间还是单个查询的时间。
如果是要很多次操作，要求其整体效率，那么使用hash_map，平均处理时间短。
如果是少数次的操作，使用hash_map可能造成不确定的O(N)，那么使用平均处理时间相对较慢、单次处理时间恒定的map。

Read full article from 使用map和hash_map的效率问题 - km的小天地 - ITeye技术网站