HashMap原理初探

1.什么是HashMap

    众所周知，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素的初始值都是Null。

2.HashMap的两个重要方法：put()和get()

    put()方法及其原理

    我们都知道，put()方法是向HashMap中添加一个数据。既然数组是HashMap的主干，那肯定是要有对应的索引(下面会直接用 index 来代替).

    比如我现在有这样一个HashMap:

    HashMap<String, Integer> hashMap = new HashMap<>();

    我要往里面插入一条数据

    hashMap.put("book", 0)；

    我们就需要一个哈希函数来确定index。

    index = hash(“book”);

    说到这里就不得不说一下这个 hash()方法了。在这里计算index，是通过与运算的方式来做的Index = HashCode(Key) & (Length - 1)   //这里的length指的是 HashMap的长度,关于长度的问题，我们在后面会说到.那么问题来了，既然是与运算，那么肯定存在结果一样即发生哈希碰撞的情况。要是我们得到的index是一样的呢？

    其实是这样的：

    HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当

    新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可。

get()方法

使用Get方法根据Key来查找Value的时候，发生了什么呢？

首先会把输入的Key做一次Hash映射，得到对应的index：

index =  Hash（“apple”）

由于刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。假设我们要查找的Key是“apple”：

第一步，我们查看的是头节点Entry6，Entry6的Key是banana，显然不是我们要找的结果。

第二步，我们查看的是Next节点Entry1，Entry1的Key是apple，正是我们要找的结果。

3.HashMap的两个重要参数：容量(Capacity)和负载因子(Load factor)

容量(Capacity)

这个容量就相当于是HashMap的长度了。默认值是16，为什么默认值是16呢？前面我们说到过，计算index的时候，是通过key的哈希值与length -1进行与运算得到的。15的二进制是 1111，那么我们通过与运算得到的值，就可以说完全取决于key的 hashcode的最后几位。这也就符合哈希算法均匀分布的原则。

那如果长度不是16，是别的呢？假如说是 9  二进制就是 1001

那么如果几个key的hashcode的后四位分别对应为 1111  1011 1101 1101

虽然四个值对应的 hashcode值的后四位不一样，但是他们跟 1001做完与运算之后买的都的值就都是 1001.那么他们拿到的index就都是一样的，这样的话，与index对应的链表的长度就变长了。我们知道，get()的时候，如果index是一样的，就会去链表中查询。而链表的特点就是增删快、查询慢，所以性能方面就会降低很多。因此我们要尽量避免哈希碰撞。所以长度值尽量设置为2的幂次方（为什么是2的幂次方呢？因为2的幂次方 - 1的二进制就都是1）

负载因子(Load factor)

负载因子是什么呢？我们HashMap能容纳的元素的个数 =  容量 * 负载因子

这个值的默认大小是 0.75 当然了我们可以动态修改容量和负载因子的值，HashMap也为我们提供了构造方法让我们去自己设置。

但是这个值有什么影响呢？

这里就要说一下HashMap所占内存空间的问题了。如果我们没有设置容量，默认是16，负载因子默认是0.75.那么这个HashMap所能容纳的最多的元素个数就是 16 * 0.75 = 12，当元素数量超过12的时候，HashMap就会去重新申请一块容量为之前的两倍的空间，然后把之前的HashMap中对应的元素全部拷贝过去，再回收掉之前所占的内存空间。

所以，如果这个值我们设置的太小，那么就会造成空间的浪费。如果设置的太大呢？那么HashMap中发生HashMap的碰撞就会变多，随之而来的就是数组每一个index对应的链表的长度就会变成，随之而来的就是查询速度回变慢。