《HashMap》初识

该HashMap的知识学习于微信公众号《程序员小灰》，本篇作为本人学习编程的第一篇学习笔记，大部分内容为记录，图片也来自此公众号，方便以后查看之用。

一、什么是HashMap?

HashMap是一个用于存储key-value键值对的集合，每一个键值对也叫做Entry。这些键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。

HashMap数组的每一个元素的初始值都是Null。

HashMap未添加元素之前的效果图

二、HashMap的Get方法与Put方法解析

对于HashMap,常用的方法是Get方法和Put方法。

1、Put方法的原理：

调用Put方法的时候会发生什么呢？

例如调用hashMap.put("apple",0)来插入一个key为"apple"的元素，这时候我们需要用到一个哈希函数来确定Entry的插入位置(index):

index = Hash("apple")

该函数也可以看出，Entry的插入位置与该Entry中的key有关。也就是说，利用该Entry的key，通过一个哈希函数，最终来确定Entry的插入位置。

假定最后计算出来的index为2，那么插入后的结果如下：

在index为2的地方插入Entrys

但是由于HashMap的长度有限，当插入的Entry越来越多的时候，无论你的哈希函数算法多么完美，也会发生index冲突的现象。如图所示：

index冲突情况

针对这种情况，HashMap的解决方案是利用链表。

HashMap的每一个元素都不止是一个Entry对象，它同时也是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当有新的Entry映射到冲突的数组位置时，只需要将它插入到对应的链表即可。

后来的Entry插入到对应的链表当中

(注意！！！) 新来的Entry节点插入链表时，使用的是"头插法"。因为HashMap的发明者认为，后插入的Entry被查找的可能性更大，放在头部能提高查找的效率。

2、Get方法的原理：

当我们调用Get方法，根据key来查找value的值的时候，发生了什么呢？

首先，会把输入的key做一次hash映射，得到index的值：

index = Hash("apple")

由于有可能出现刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry对象，这时候就需要顺着对应的链表的头节点，一个一个往下查找。假设我们要查找的key是"apple":

查找key为"apple"的Entry对象

第一步，我们根据Hash函数得到index的值为2；

第二步，我们查看头节点Entry6，Entry6的key是banana，显然不是我们要找的结果；

第二步，我们查看的是Next节点Entry1，Entry1的key正是"apple"，就是我们想要找的结果了。

三、关于HashMap的长度问题

1、HashMap的默认初始长度

HashMap的默认初始长度为16，并且每次自动扩展或是手动初始化时，长度必须是2的幂，之所以这样做，是为了服务于从Key映射到index的Hash算法。

2、映射函数(Hash函数)的实现

Hash函数采用的是位运算。

有如下的公式(Length是HashMap的长度)：index = HashCode(key)&(Length-1)

下面我们以值为"book"的key来演示整个过程：

1、计算book的hashCode,结果为十进制的3029737，二进制的1011100011101011101001。

2、假定HashMap的长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。

3、把以上两个结果的二进制做与运算，即1011100011101011101001&1111 = 1001，十进制是9，所以index = 9。

可以说，Hash算法最终得到的index的值，完全取决于key的HashCode值的最后几位。