1、hash_map 和 map

1.1 区别

(1)   hash_map 采用hash 表进行存储, map采用红黑树 实现,数据结构不同

(2)   hash_map 需要hash 函数;   map 只需要比较函数

1.2 如何使用

(1) hash_map 的查找速度 比 map (Ologn)快,、、hash_map的构造速度较慢。

(2) hash_map 相对消耗内存

(参考:https://www.cnblogs.com/inception6-lxc/p/9263964.html

1.3 hash_map与 map的查找

(1) map的查找方案是采用的是二分法的方案。比如说即使当前是100w的记录,当前比较次数也是不超过21次。  

     但是,如果我们要频繁的去查找,比较的次数也就很多了,这个时候,也就会出现很慢的情况

----------------------上面的提出的问题的解决方案,就是可以使用hash_map 

1.4 hash_map 的原理

hash_map 基于的是hash表的情况,也就是多消耗内存以换得空间的解决的方案,实际上,这个时候,数据额存储和查找的时间就是可以大大的降低。

  其基本原理是:使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数,也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标,hash值)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素“分类”,然后将这个元素存储在相应“类”所对应的地方,称为桶。

1.5 hash_map的使用

(1)例子1 


#include <hash_map>
 
#include <string>
 
using namespace std;
 
int main(){
 
hash_map<int, string> mymap;
 
mymap[9527]="唐伯虎点秋香";
 
mymap[1000000]="百万富翁的生活";
 
mymap[10000]="白领的工资底线";
 
...
 
if(mymap.find(10000) != mymap.end()){
 
...
}

 

1.6 unorder_map  与hash_map(参考:https://blog.csdn.net/chen134225/article/details/83106569

这两个的内部结构都是采用哈希表来实现。区别在哪里?unordered_map在C++11的时候被引入标准库了,而hash_map没有,所以建议还是使用unordered_map比较好

 

2、关于vector 与数据的关系

(1)https://blog.csdn.net/hanbaoyi192/article/details/98769196 这篇blog 提出的结果是 数组要快很多很多

(考虑到s)

 

 

 

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐