源码剖析Java8HashMap的resize扩容时机？扩容机制？

本文从两个面试题分析HashMap的resize()方法源码，分别是：HashMap什么时候扩容？HashMap扩容做了什么？

1、HashMap什么时候扩容？

1. 第一次添加元素时，即当HashMap的数组为null或者数组的长度为0时；
   

2. 链表转红黑树、且数组容量小于64时；
   

3. 数组容量大于扩容阈值时；
   

2、HashMap扩容做了什么？

这里也是resize()方法源码解析。

HashMap的resize()方法扩容大致可以分为两个阶段；

1. 第一阶段：参数newCap、newThr、threshold的解析计算；
2. 第二阶段：根据参数newCap、newThr进行rehash，构建新的数组。

resize()方法中的局部变量解释：

1）第一阶段

第一阶段，计算newCap、newThr：

1. 如果HashMap的数组中有数据，对数组进行两倍扩容；数组容量的上限为1 << 30；
2. 如果HashMap的数组中没有数据，设置数组容量为默认值16、扩容阈值为默认值12；

2）第二阶段

第二阶段，根据第一阶段计算出的newCap、newThr进行rehash构建新数组：

如果老的数组中有数据，则进行数据迁移；数据迁移步骤如下：

1. 遍历老数组的每个槽位；
2. 如果槽位中是一个普通节点，则将节点放在新数组中，所在新数组中的下标计算方式为：e.hash & (newCap - 1);
3. 如果槽位中是一个树节点，则进行红黑树的迁移操作，新数组中下标计算方式同普通节点；
4. 如果槽位中是一个链表节点，则将链表拆为高位链表和低位链表，分别放入新数组的旧数组的下标位置和 （旧数组下标 + 旧数组容量）下标位置；
5. 最后返回新数组。

完整流程图

完整源码

final Node<K,V>[] resize() {
    // 阶段一：计算newCap、newThr
    // 没插入数据之前的哈希数组oldTab
    Node<K,V>[] oldTab = table;
    // old数组的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // old扩容阈值
    int oldThr = threshold;
    // 新的数组容量和扩容阈值
    int newCap, newThr = 0;
    // oldCap > 0表示不是首次初始化，因为hashMap用的是懒加载
    if (oldCap > 0) {
        // 老数组容量大于最大容量（1 << 30）时
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 扩容阈值为整数的最大值
            threshold = Integer.MAX_VALUE;
            // 然后就不扩容了
            return oldTab;
        }
        // 两倍扩容，并且扩容后的长度要小于最大值、old容量要大于等于16
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 扩容阈值变为原扩容阈值的2倍
            newThr = oldThr << 1; 
    }

    // 处理情况：溢出越界
    else if (oldThr > 0) 
        newCap = oldThr;
    // 新的HashMap首次初始化时，设置数组容量
    else {               
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 扩容阈值等于容量*加载因子
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    if (newThr == 0) {
        // 扩容阈值
        float ft = (float)newCap * loadFactor;
        // 判断新数组容量是否大于最大值，扩容阈值是否大于最大值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    // 扩容阈值赋值
    threshold = newThr;
    // 表示忽略该警告
    @SuppressWarnings({"rawtypes","unchecked"})
        // 初始化数组
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    // rehash操作，
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            // 临时变量
            Node<K,V> e;
            // 当前哈希桶的位置值不为null，也就是数组下标处有值，因为有值表示可能会发生冲突
            if ((e = oldTab[j]) != null) {
                // 把已经赋值之后的变量置位null，当然是为了便于回收，释放内存
                oldTab[j] = null;
                // 如果下标处的节点没有下一个元素，也就是普通节点
                if (e.next == null)
                    // 把该变量的值存入newCap中，数组下标为e.hash & (newCap - 1)
                    newTab[e.hash & (newCap - 1)] = e;
                // 该节点为红黑树结构，也就是存在哈希冲突，该哈希桶中有多个元素
                else if (e instanceof TreeNode)
                    // 把此树进行转移到newCap中
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { 
                    // 此处表示为链表结构，同样把链表转移到newCap中；
                    // 则将链表拆为高位链表和低位链表，分别放入新数组的旧数组的下标位置和 （旧数组下标 + 旧数组容量）下标位置；
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    //返回扩容后的hashMap
    return newTab;
}