在查找大数据方面，map要优于数组，对于数组说来就是依次下标遍历了，直到找到这个数据为止，map理想情况下只需要0(1)的时间级，其查找的时间复杂度与元素的数量多少无关。那么map到底用了什么办法达到了这么快的查找速度。
map的组成
简单来说，map的组成是有一个哈希表（也叫散列表）,是根据关键码值（key value)而直接进行访问的数据结构，也就是通过关键码值映射到表中一个位置来访问记录，以加快查找的速度。映射这种关系的函数就是哈希函数（散列函数）。
关系大概如下
记录存储的位置 = 哈希函数(key)
哈希函数
哈希函数到底是怎么映射这种关系的呢，哈希算法有很多种，用哪种算法，没有完美的算法，简单来说，使用一套算法，将所有的健转化为一个数组的索引，值为其对应的值，这样就可以通过f(key)找到数组的下标一次查找到对应的值，达到快速查找的目的。
举个最简单的例子，当然这里没有任何算法1
2
3
4
5
6
7
8
9#比如一个一组key是[3,5,4,7]，在数组中的形式如下
0
1
2
3 值
4 值
5 值
6
7 值
这样做虽然在一定程度上浪费了空间，但是在这个大内存时代，用合理的空间换取时间是能承受的，而这种通过f(key)查找值的方法，也决定了key-value在形式上无序的，跟插入的顺序无关，跟key在哈希表中的f(key)顺序有关。
当然肯定会引申出几个问题，比如数值超过可以能计算的范围，怎么哈希计算，又比如理想的情况下哈希值是均匀分布，但是不一定所有被哈希的值一定是不一样，可能得到相同的哈希值对应多个值，这种情况也叫哈希冲突，这种冲突肯定是不能避免的，遇到哈希冲突又该怎么样，这个数组的长度又应该如何确定，如果长度太小，空间很容易满造成冲突，太长又浪费空间等等，下面将对此做简单的介绍。
常用的哈希算法
实际工作中徐视不同的情况采用不同的哈希函数，通常考虑的的因素有：
- 计算哈希函数所需时间
- 关键字的长度
- 哈希表的大小
- 关键字的分布情况
- 记录的查找频率
1.直接寻址法
取关键字或者关键字的某个线性函数值作为哈希地址，即H(key)=key 或者 H(key) = a*key +b(a,b为整数)，如果H(key)的哈希地址上已经有值了，那么就往下一个位置找，直到找到没有值的位置就把元素放进去，最简单的就是我上面举的那个例子。
2.数字分析法
分析一组数据，比如一组出生年月，发现前几位数字一般都相同，月日差别很大，所以取后面的几位数字来构建哈希地址
3.平方取中法
对关键字进行平方运算，然后取结果的中间几位作为哈希地址。假如有以下关键字序列{421，423，436}，平方之后的结果为{177241，178929，190096}，那么可以取{72，89，00}作为Hash地址
4.折叠法
折叠法即将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(注意:叠加和时去除进位)作为哈希地址，数位叠加可以有移位叠加和间界叠加两种方法.移位叠加是将分割后的每一部分的最低位对齐,然后相加;间界叠加是从一端向另一端沿分割界来回折叠,然后对齐相加.1
2
3
4
5
6
7
8比如548623247
数位叠加 间接叠加
548 548
623 326
+ 247 + 247
—————————— ——————————————
1418 1121
H(key) = 418 H(key) = 121
5. 随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key),其中random为随机函数。通常用于关键字长度不等时采用此法
6.除留余数法
找一个不大于哈希表表长m除最大的质数或m取余数作为哈希地址
处理哈希冲突的方法
1.开放定址法
Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中m为表长，di为增量序列
如果di值可能为1,2,3,…m-1，称线性探测再散列。
如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2)
称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
比如有一组关键字{12，13，25，23，38，34，6，84，91}，Hash表长为11，Hash函数为address(key)=key%11，当插入12(hash(12)=1)，13(hash(13)=2)，25(hash(25)=3)时可以直接插入，而当插入23时，地址1被占用了，因此沿着地址1依次往下探测(探测步长可以根据情况而定,如(hash(23)+1)%11=2,(hash(23)+2)%11=3,(hash(23)+3)%11=4)，直到探测到地址4，发现为空，则将23插入其中。
2.链地址法（拉链法)
当存储结构是链表时，多采用拉链法。其基本思路是：将所有具有相同哈希地址的而不同关键字的数据元素连接到同一个单链表中。如果选定的哈希表长度为m，则可将哈希表定义为一个有m个头指针组成的指针数组T[0..m-1]，凡是哈希地址为i的数据元素，均以节点的形式插入到T[i]为头指针的单链表中。并且新的元素插入到链表的前端，这不仅因为方便，还因为经常发生这样的事实：新近插入的元素最优可能不久又被访问。
3.哈希表的装填因子
装填因子是什么，它表示关键字填充哈希表后饱和的程度。装填因子越大冲突越大
4.建立一个公共溢出区
把凡是重复的放到一个缓存区中，当我通过f(key)查找时，发现找的不对，就在缓存区里找
哈希表大小的确定
哈希表的尺寸最好是一个质数，当然根据实际情况，会有不同的大小，或者比如是10key值，大于10的数是2的4次方，一般设装填因子为0.7.如果大于设定的装填因子值就需要扩容，重新在开辟一片新的空间