JDK8-HashMap底层源码解析

image.png

new

JDK1.7：数组+链表
JDK1.8：hash表=数组+链表+红黑树
哇瑟，一个比一个背的熟，面试时稍微问一下就懵逼。

HashMap提供了4个构造函数：

• 无参构造新建时会给负载因子设置默认为0.75，容量大小默认为16，阈值为0；

  • 这里容量大小默认16只是我们约定的而已，没有添加元素前我们底层的Node数组的length一直为0，一切操作都在put操作之后才展开。

• 有参构造，使用参数提供的负载因子，容量会由tableSizeFor方法计算出大于等于参数值的一个二次方的数值；阈值初始值会使用容量的值，然后在put元素的时候才会使用公式：容量*负载因子 重新赋值；

image.png

tableSizeFor方法具体实现：

image.png

我们可以通过反射来查看HashMap在初始化和put后容量和阈值的变化，代码如下：

    private  static void test() throws Exception {
        //指定初始容量15来创建一个HashMap
        HashMap m = new HashMap(16);
        //获取HashMap整个类
        Class<?> mapType = m.getClass();
        //获取指定属性，也可以调用getDeclaredFields()方法获取属性数组
        Field threshold =  mapType.getDeclaredField("threshold");
        //将目标属性设置为可以访问
        threshold.setAccessible(true);
        //获取指定方法，因为HashMap没有容量这个属性，但是capacity方法会返回容量值
        Method capacity = mapType.getDeclaredMethod("capacity");
        //设置目标方法为可访问
        capacity.setAccessible(true);
        //打印刚初始化的HashMap的容量、阈值和元素数量
        System.out.println("初始数据 - 容量："+capacity.invoke(m)+"    阈值："+threshold.get(m)+"    元素数量："+m.size());
        for (int i = 0;i<25;i++){
            m.put(i,i);
            //动态监测HashMap的容量、阈值和元素数量
            System.out.println("容量："+capacity.invoke(m)+"    阈值："+threshold.get(m)+"    元素数量："+m.size());
        }
    }

输出结果如下：

image.png

put

接下来我们看put方法：并没有直接使用key的hashcode方法来生成哈希值，而是执行了这个操作： (h = key.hashCode()) ^ (h >>> 16) ；

在执行hashcode方法后再异或 这个右移16位的值，得到了一个新的哈希值，但是哈希冲突仍然不能避免。

image.png

接着看putVal方法：

1. 如果node数组为空，即table为空，会执行resize方法返回一个Node<K,V>[] 赋值给tab变量，也就是在这个方法中会给阈值重新计算；

   • resize()方法主要是用来扩容的，下面链表尾插入的时候也会用到；

2. 如果tab对应下标没有值，则新建一个Node放入数组；

   • 这里的(p = tab[i = (n - 1) & hash]) 就体现出我们要求数组长度是2的幂次方的重要性，只有n为2的幂次方，n-1 和hash值与运算才能得到0到n-1的下标值。

3. 如果对应下标有值，hash相同key相同，则会在后面根据一个boolean值判断只够进行覆盖；

   • 为什么会有boolean值，put操作默认为true会执行进行覆盖，但还有一个方法map.putIfAbsent()，也是调用的putVal方法；
   • 另外一点就是put方法和putIfAbsent方法都是有返回值的，返回的都是执行插入操作前key对应的value值。

4. 如果Node是TreeNode类型，即Node数组对应下标中是一个红黑树，将要操作红黑树插入；

5. 否则就是链表的尾插入，即Node数组对应下标中是一个链表；

   • JDK1.7是头插入 ，1.8是尾插，使用头插会改变链表上的顺序，采用尾部插入能保持链表原本的顺序，jdk1.7的同步插入在扩容时会造成错误，链表中的指向会发生错乱出现循环引用 。
   • 链表插入会循环判断node.next是否为null，链表长度大于8时转成红黑树，因为先判断在插入所有链表会有9个元素，会调用treeifyBin().

image.png

treeifyBin方法会先判断Node数组是否大于64，小于会调用resize（）扩容 一个长链表转为两个短链表；

大于64则会使用do while循环将所有的Node改造为TreeNode，并且变为一个双向链表，给节点的prev和next赋值；

最后通过treeify将链表转为红黑树。

image.png

resize

//Initializes or doubles table size

final Node<K,V>[] resize()

从源码中可以看出resize()方法有两个功能：初始化数组和扩容；

在putVal方法中，有三处都涉及到了resize()，一是初始化时，二是链表未插入时调用的treeifyBin方法中也会用到，最后就是判断map的size是否大于阈值时也会执行；

resize方法：

1. 判断容量是否大于0，容量翻倍后小于最大值1 << 30(即 1 073 741 824)且大于16，阈值翻倍；
2. 容量等于0，阈值大于0，将阈值赋值为新的容量；
3. 容量等于0，阈值等于0，会初始化数组，容量设为16，阈值设为12；
4. 然后生成新的Node[]，如果老数组为null，直接返回结束；
5. 老数组不为null，则会将老数组的数组移至新数组，是resize方法操作的关键步骤。

image.png

下图为resize方法for循环中具体的代码：

1. 循环Node数组，首先判断是否为单节点（即node.next==null ），根据节点的hash值和翻倍后的容量减一进行与运算的到新的下标（即通过公式：hash & (newCap - 1) ）；
2. 如果节点是TreeNode节点，则证明此下标位置上的是一个红黑树，则会调用split方法（下面会讲）；
3. 最后一种情况则是此下标位置上的一个链表：
   • 新建两个链表和两个尾节点；
   • 节点hash值和老容量进行与运算，判断是否等于0分别放进两个链表中，其实这地方没那么难理解，数组计算下标的公式是hash & (容量 - 1)，意思就是这个下标上的链表中的每一个元素的hash值可能各不相同，在与老的容量值（二进制只有一位为1，其余位都是0）进行与运算后(即hash & 容量 )只可能得到0或者不是0，我们在扩容翻倍后就可以将其从一个大一点的链表拆分为两个小一点的链表，两个新链表对应数组下标的差为扩容前容量的值。

image.png

splite

将这个方法前，先熟悉TreeNode的结构，TreeNode继承自LinkedHashMap.Entry，而LinkedHashMap.Entry又继承自HashMap.Node，HashMap.Node其实是实现了Map.Entry<K,V>。

    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;

1. TreeNode<K,V> b = this 的this是指TreeNode类，split方法是HashMap中的静态内部类TreeNode的一个方法；
2. for循环的内容和resize方法中处理链表如何移到新数组中的操作基本相同，通过遍历节点通过hash值和容量进行与运算是否等于0分别给两个树增加元素，虽然是使用了TreeNode，但也只用到了它的next方法，本质上还是一个链表；
3. 树的长度小于6，会将TreeNode退化为Node链表，untreeify（） 方法返回的是一个Node<K,V>，给传进来的对应数组下标位置进行赋值；
4. 大于6则会通过treeify（） 方法将这个TreeNode构建为一个红黑树。

image.png