看不懂来找我！JDK1.8 HashMap resize()

Title：JDK1.8 HashMap resize() loTail.next = e loTail = e

技术博客已迁移至个人页，欢迎查看 yloopdaed.icu

您也可以关注 JPP - 这是一个Java养成计划，需要您的加入。

title：JDK1.8 HashMap resize() loTail.next = e loTail = e

前言

HashMap扩容的过程包含了很多巧妙的思考，思想简单易懂，但是代码的实现真的让人折服！

今天快速浏览resize方法时，被两行代码绕住了：

image

可能是对于引用类型的理解不够深刻吧，这两行代码真的看了我一天！网上也很少有人分析这两行代码（可能因为太容易了吧）

最后我自己写了个Demo，算是把这个操作搞清楚了。因为是引用类型的指针指向问题，所以画图也不太好理解，只能自己写个Demo，一点点Debug分析过程。

准备工作

准备一个简单的链表对象

static class Node<K, V> {
    K key;
    V value;
    Node<K, V> next;

    Node(K key, V value, Node<K, V> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }
    
}

简化过程

先看下面的代码，理解这个过程：

Node a = null;
Node b = null;
Node c = new Node('c', 'c', null);
b = c;
a = c;
c = new Node(8,8, null);
a.next = c;
a = c;

代码1-5行

声明了a，b两个Node类型的引用，声明c指向一个Node@478对象

然后把a和b都指向了Node@478对象。如下图所示：

代码 6行

创建了一个新的Node@479对象，将c引用指向这个对象。如下图所示：

代码 7行

在Node@478中有一个next属性，a.next = c;表示将Node@478的next指向c引用指向的地址(即Node@479)

代码 8行

a = c; 就是将a的引用重新指向c引用指向的地址(即Node@479)

所以最终的结果就是：

a，c引用指向相同的Node@479对象

b指向Node@478对象，其中Node@478的next引用指向Node@479对象

image

理解了上面的过程，下面就非常容易了 ^ ^

创建链表

创建链表并插入10个元素（尾插）来模拟HashMap数组中某一个节点的链表。

JDK1.8中，链表长度超过 变树阈值 时会将链表变化成红黑树
这个变化需要满足两个条件：1 链表长度超过变树阈值 2 HashMap的size大于64

Node tab = new Node(0,0,null); // node链表
Node p = tab;

for (int i = 1; i <= 10; i++) {
    Node tail = new Node(i, i, null); // 最后一个节点
    if (p.next == null) {
        p.next = tail;
    }else { // 尾插
        Node e;
        while ((e = p.next) != null) {
            if (e.next == null) {
                e.next = tail;
                break;
            }
            p = e;
        };
    }
}

仿写resize核心代码

在HashMap扩容时有一个很巧妙的操作，就是数组长度扩容至原先两倍时，重新计算链表节点的插入角标会将原链表随机分布到新数组的两个位置：1 原来角标的位置 2 原角标+原数组长度的位置

而这个操作在JDK1.7和JDK1.8中的思想是相同的，不过实现方式略有不同：

假设：
现在有两个链表节点
他们的hash值低8位分别是 0110 1011 、1001 1011
扩容前数组长度为16，扩容长度变为32
扩容前他们都在数组角标11的位置

// JDK1.7 e.hash & (length-1)
// 第一个节点
    0110 1011
    0001 1111
& 0000 1011 角标11
// 第二个节点
    1001 1011
    0001 1111
& 0001 1011 角标27

// JDK1.8 (e.hash & oldCap) == 0
// 第一个节点
    0110 1011
    0001 0000
& 0000 0000 结果0，在原数组位置
// 第二个节点
    1001 1011
    0001 0000
& 0001 0000 结果1，在新数组位置

JDK1.7中，直接通过hash值与新数组长度减1 按位与得到新角标

JDK1.8中，通过计算hash值对应的原数组位置是否为0，如果为0则插入tab[j]，否则插入tab[j+oldCap]

我模拟的Demo中没有设计这么多复杂的数据，所以简化为节点value值的奇偶判断

Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
Node e = tab;
do {
    next = e.next;
    if ((int)e.value % 2 == 0) { // 进入次判断的节点为 0,2,4,6,8
        if (loTail == null)
            loHead = e;
        else
            loTail.next = e;
        loTail = e;
    }
    if ((int)e.value % 2 == 1) {
        if (hiTail == null)
            hiHead = e;
        else
            hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

以取模结果等于0为例：

第一次进入，loHead = 0, loTail = 0。loTail和loHead指向相同的内存地址

第二次进入，loTail.next = 2会移动loHead.next指向 2。随后loTail = 2，即loHead.next和loTail指向相同的内存地址

第三次进入，loTail.next = 4也就是loHead.next.next指向4。随后loTail = 4，即loHead.next.next和loTail指向相同的内存地址

以此类推，如下图：

image

思考

上面就是我对 loTail.next = e; loTail = e; 这两行代码的理解。

进一步思考，为什么HashMap在 JDK1.7 的时候会选择头插法插入元素？

不考虑JDK1.7中resize时的循环引用问题，我认为头插法无论是从理解的角度，还是从代码实现的角度都更胜一筹。甚至还可能能稍微优化一些查询的速率。

就拿上面Demo中的尾插生成测试链表为例，我的写法是仿照JDK1.8的，中间要声明很多局部变量，所以你会看到 JDK1.8 的源码中有很多判断中赋值的操作。如果不这么写的话，估计JDK1.8的源码会再多几百行（本身实现了一套红黑树，代码量相较1.7膨胀了几乎一倍）