HashMap是Java中提供的一种用来存储哈希表的存储结构，它允许存储null的键和null的值操作，并且在使用的时候不会保证键值对存储的顺序，其底层是一个基于数组和链表的实现，但是在Java8之后，变成了红黑树结构。下面我们就来介绍Java8之后Hash如何进行扩容操作的。

HashMap实现扩容触发的条件。

在HashMap中扩容是为了保证在插入大量元素时，保持较低的碰撞概率和高效的查询性能。扩容的触发条件是当前元素个数超过了阈值（threshold），这个阈值计算公式如下所示

threshold=capacity×load factor

其中，默认的load factor是0.75。而capacity则表示当前容量。

从Java8开始，与之前的变化主要有两个如下所示。

• 第一、将链表转红黑树，当单个桶（bucket）中元素数量超过一定阈值（默认是8）时，链表结构会转化为红黑树，以提高性能。
• 第二、将红黑树转链表，当红黑树中的元素数量减少到一定阈值以下（默认是6）时，红黑树会重新退化为链表。

在进行扩容操作的时候，新的数组容量通常是旧容量的两倍，并且旧的元素会被重新分配到新数组中。如下所示。

// HashMap.java
final Node[] resize() {
    Node[] oldTable = table;
    int oldCap = (oldTable == null) ? 0 : oldTable.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTable;
        }
        newCap = oldCap << 1;
        if (newCap < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1;
    }
    else if (oldThr > 0)
        newCap = oldThr;
    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[] newTable = (Node[])new Node[newCap];
    table = newTable;
    if (oldTable != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node e;
            if ((e = oldTable[j]) != null) {
                oldTable[j] = null;
                if (e.next == null)
                    newTable[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode)e).split(this, newTable, j, oldCap);
                else { // preserve order
                    Node loHead = null, loTail = null;
                    Node hiHead = null, hiTail = null;
                    Node 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;
                        newTable[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTable[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTable;
}

关键步骤介绍

第一步、重新对容量进行计算，具体操作代码如下所示。

newCap = oldCap << 1; // 新容量是旧容量的两倍
newThr = oldThr << 1; // 新阈值是旧阈值的两倍

第二步、需要根据新的计算容量，来创建新的数组实现存储。如下所示。

Node[] newTable = (Node[])new Node[newCap];

第三步、需要重新添加分配元素，将旧的数组中的元素通过重新的计算Hash值然后放入到新的数组中。如下所示。

newTable[e.hash & (newCap - 1)] = e;

第四步、处理完数组节点，接下来就是对于链表和红黑树的处理，具体操作如下所示。

if (e.next == null)
    newTable[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
    ((TreeNode)e).split(this, newTable, j, oldCap);
else {
    // 处理链表节点的重新分配
}

链表和红黑树的处理

在HashMap扩容的过程中，对于链表和红黑树的处理是扩容逻辑的核心部分。下面我们就来详细的介绍一下再HashMap的扩容操作中对链表和红黑树的处理机制，包括它们的重新分配、转换以及相关的源码解析。

链表节点的处理

在扩容时，需要将旧数组中的链表节点重新分配到新数组中。需要进行如下的操作步骤，如下所示。

• 第一步、确定新位置，通过新的容量重新计算每个节点的位置。
• 第二步、拆分链表，将链表拆分成两个部分，一个部分保留在原索引位置，另一个部分移动到新的索引位置（索引位置+旧容量）。

具体的操作代码如下所示。

if (e.next == null) {
    newTable[e.hash & (newCap - 1)] = e;
} else {
    Node loHead = null, loTail = null;
    Node hiHead = null, hiTail = null;
    Node 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;
        newTable[j] = loHead;
    }
    if (hiTail != null) {
        hiTail.next = null;
        newTable[j + oldCap] = hiHead;
    }
}

其中参数说明如下所示，

• oHead 和 loTail 用于存储低位链表节点。
• hiHead 和 hiTail 用于存储高位链表节点。
• 节点根据hash & oldCap的结果被分配到loHead或hiHead。

最终，低位链表和高位链表分别放入新的数组位置中。通过上面的操作之后，就完成了对于旧的链表往新的链表的转换操作，接下来我们就来看看如何实现对于红黑树的转换操作。

红黑树节点的处理

在Java 8中，通过引入了红黑树存储来优化因为链表过长的时候的性能问题。在Java8存储中当链表长度超过阈值（默认是8）时，对应的链表就会转换为红黑树。然后再我们进行扩容的时候，对于红黑树的节点处理也就比较复杂了，需要考虑到拆分树节点和重新平衡树等操作，具体操作如下所示。

• 第一步、拆分红黑树，根据新的容量，将红黑树节点分配到新的索引位置，类似于链表的拆分操作。
• 第二步、在保持树结构的同时，需要重新组织节点，来确保红黑树的平衡和性质。

树节点处理的代码如下

else if (e instanceof TreeNode) {
    ((TreeNode) e).split(this, newTable, j, oldCap);
}

当桶中包含树节点时，需要进行树节点的拆分，这在TreeNode类中的split方法实现，如下所示。

final void split(HashMap map, Node[] newTab, int index, int bit) {
    TreeNode b = this;
    // 两个新的树头
    TreeNode loHead = null, loTail = null;
    TreeNode hiHead = null, hiTail = null;
    int lc = 0, hc = 0;
    for (TreeNode e = b, next; e != null; e = next) {
        next = (TreeNode)e.next;
        e.next = null;
        if ((e.hash & bit) == 0) {
            if ((e.prev = loTail) == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
            ++lc;
        }
        else {
            if ((e.prev = hiTail) == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
            ++hc;
        }
    }
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            newTab[index] = loHead.untreeify(map);
        else {
            newTab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(newTab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            newTab[index + bit] = hiHead.untreeify(map);
        else {
            newTab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(newTab);
        }
    }
}

参数说明

• loHead 和 loTail 用于存储低位树节点。
• hiHead 和 hiTail 用于存储高位树节点。
• 节点根据hash & bit的结果被分配到loHead或hiHead。

只有当树结构中的节点数低于阈值（默认是6）时，树结构才会退化为链表。否则，就会继续要保持树结构进行存储。

总结

Java 8中HashMap扩容时对于链表和红黑树的操作是其执行扩容的关键，其中对于链表的处理操作需要根据新哈希值重新分配位置，将链表拆分成低位和高位两部分，分别放入新的数组位置，对于红黑树的操作，主要包括了对树结构的拆分，并且将树节点移动到新的数组位置，同时还要保持红黑树的性质，在树节点不满足阈值要求的时候，需要进行树化或退化处理。

通过这些处理机制，HashMap在扩容后能继续保持高效的性能，避免过多的哈希冲突和链表过长的问题。