首页 > 代码库 > STL中map与hash_map的比较
STL中map与hash_map的比较
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个方面来权衡: 查找速度,数据量, 内存使用,还有一个就是你的经验!没有特别的标准
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。