STL中map与hash_map的比较

时间:2024-03-25 17:33:38

1. map :

  C++的STL中map是使用来做查找算法; 时间复杂度:O(log2N)

2. hash_map :

  使用hash表来排列配对,hash表是使用关键字来计算表位置; 时间复杂度:O(1), 最坏的时间复杂度:O(n)


总体来说
:hash_map 比 map 查找速度快,而且查找速度基本和数据量大小无关,属于常数级别,节省一定内存,如果没有必要排序的话,尽量使用 hash_map 。

注:hash还有hash函数的耗时。当有100w条记录的时候,map也只需要20次的比较,200w也只需要21次的比较!所以并不一定常数就比log(n) ;用map,还是hash_map,从3个方面来权衡: 查找速度,数据量, 内存使用,还有一个就是你的经验!没有特别的标准