对HashMap源码的解读

对HashMap源码的解读

HashMap底层机制：

1）HashMap底层维护了Node类型的数组table，默认为null。（也就是说，数组元素的类型是Node，链表元素类型是Entry）

2）当创建对象时，将加载因子（loadfactor）初始化为0.75

3）当添加key-val时，通过key的哈希值得到在table的索引，然后判断该索引处是否有元素，如果没有元素则直接添加。如果该索引处有元素，继续判断该元素的key和准备加入的key是否相等，如果相等，则直接替换val；如果不相等，则需要判断是树结构还是链表结构，做出相应处理。如果添加时发现容量不够，则需要扩容。

4）第一次添加，则需要扩容table容量为16，临界值threshold为12

5）以后再扩容，则需要扩容table容量为原来的2倍，临界值为原来的2倍，即24，以此类推

6）在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8)，并且table的大小 >= MIN_TREEIFY_CAPACITY（默认64），就会进行树化（红黑树）

以下面代码为例，我们debug追进去源码：

public class HashMapSource {
    public static void main(String[] args) {
        HashMap hashmap = new HashMap();
        hashmap.put("java",10); 
        hashmap.put("php", 10); 
        hashmap.put("java", 20);   
        System.out.println(hashmap);    // {java=20, php=10}
    }
}

1、通过debug追踪进入HashMap源码：

执行构造器 new HashMap()

1）初始化加载因子0.75

2）此时hashmap对象里面就有一个table数组，类型是Node，只是它是个null

3）可以看到，keySet、values这些属性都有

2、追踪进put()：

1）先装箱，对基本数据类型的封装

返回，再进入源码：

2）进去put()方法，依次先进行hash计算，得到索引位：

对hashCode进行 按位异或^ 无符号右移16位

3）再进入putVal()方法：

3-1）定义了辅助变量

3-2）因为是第一次添加元素，所以此时table的容量为null，因此进入第一段if执行语句：resize()扩容

①进入resize()方法中有一句很关键：

 Node[] newTab = (Node[])new Node[newCap]; 这一段是对table数组进行扩容的，扩容的长度是16位，同时类型是Node类型

3-3）接着返回putVal方法，执行第二段if语句，根据hash值判断对应的table索引位Node是否有元素，如果没有元素，则把k-v创建成一个节点，加入到这里

① n的值为16，在第一段if语句中，已经扩容得到了值

②tab[i = (n - 1) & hash] 得到的值是3，因此在table索引位为3的位置上创建节点元素：

3-4）执行完创建节点后，进入下面的记录值：

①记录修改次数

②判断当前table个数是否大于临界值，如果大于，则需要扩容

③返回null则说明添加成功

到这里，第一个put()元素就添加成功了：

执行第二个put()方法：原理与第一个put添加大致相同，因为添加的key不一样，所以执行方法差不多

1、进入装箱，对基本数据类型封装：

2、返回，再进入put()方法：

1）这里对传入进来的key计算hash值，hash得到结果是：110969

2）然后再进入putVal方法

3、进入putVal()方法：

1）第一段if语句不执行，因为table不为null

2）执行第二段if语句，根据hash值判断对应的table索引位Node是否有元素，这里tab[i = (n - 1) & hash] 得出table[i]的值为9，也就是在索引位为9的位置上，创建Node节点元素，将k-v加入进去

4、进入下面的记录值修改这里：

1）每增加一个Node节点，modCount就++，size也同理

5、至此，第二个put()元素添加也成功了：

执行第三个put()方法：关键->对相同key的添加，看下会怎么执行

1、同样先进行装箱

2、进入put()源代码：

①因为key是相同的"java"元素值，所以得到的hash值仍然是3254803，与第一个put相同

3、进入putVal方法：

 ①第一段if语句肯定不执行

②第二段if语句也不执行，因为当前key的索引位已经有节点元素，所以不为null

③进入else语句，执行第一个if，首先判断当前索引位的节点的hash值是否与传入进来的hash值相同 并且 (索引位的key值与传入的key值是否同一个对象 或者 key值不等于null并且传入进来的key与索引位上的key进行equals比较，得到结果相同)，那么就将原先的节点元素P(包含有key，value，hash等数据)赋值给 Node变量e，此时就不再执行下面的else if 和 else语句了。

对一个元素判断有两种情况：==对象判断 和 equals内容判断

④然后再对e进行判断是否为空，此时e肯定不为空，然后将原来的value赋值给oldValue变量，再将传入进来的value元素 替换 原先的元素，也就是赋值给e.value

⑤最后返回oldValue，连最下面的记录值++modCount; 这些也不执行，因此，返回的不是null，那么就添加失败。【注意：这里的value值已经被修改替换了哦】

3-1）else语句里面的第二段else if 和 else的理解：

 ①第二段else if的理解：判断当前table已有的Node节点类型是否是红黑树，如果是，则按照红黑树的方法来添加节点

②第三段else的理解：这一段是无限循环，意思是找到了节点，但由于这里面是个tab链表，所以需要对这个链表进行循环判断：

1、首先判断当前节点的下一个节点是否为空（为什么不是e=p？上面第二个if语句 跟else第一个if语句已经写明），如果为空，就在下一个节点创建元素(hash, key, ....)，然后还判断当前遍历的链表节点个数是否 大于等于 树化的TREEIFY_THRESHOLD临界值8，如果是，则就调用treeifyBin方法进行红黑树转换，然后break【如果是这里创建的对象，就不会执行else下面的if语句】

    1-2、这里treeifyBin不是马上就进行红黑树转换，它还是会先进行判断是否需要resize()扩容：

2、其次如果当前节点的下一个节点不为空，那么就判断它的hash值是否与传进来的hash值相同，这里的if条件满足，也break，然后将当前节点e赋值给p，又循环，直到链表的最后一个next为空，创建节点元素了，就break；

4、至此，第三个put()元素没有添加成功，但是value值被修改了：