HashMap源码解读——逐句分析resize方法的实现

一、前言

最近在阅读HashMap的源码，已经将代码基本过了一遍，对它的实现已经有了一个较为全面的认识。今天就来分享一下HashMap中比较重要的一个方法——resize方法。我将对resize方法的源代码进行逐句的分析。

若想要看懂这个方法的源代码，首先得对HashMap的底层结构和实现有一个清晰的认识，若不清楚的，可以看看我之前写的一篇博客，这篇博客对HashMap的底层结构和实现进行了一个比较清晰和全面的讲解，同时博客的最底下附上了两篇阿里架构师对HashMap的分析，写的非常好，很有参考价值：

Hexo链接 —— HashMap源码解读——深入理解HashMap高效的原因
博客园链接 —— https://www.cnblogs.com/tuyang1129/p/12362959.html

二、解析

2.1 resize方法的作用

没有阅读过HashMap源码的人可能并不知道它有一个叫resize的方法，因为这不是一个public方法，这个方法并没有加上访问修饰符，也就是说，这个方法HashMap所在的包下使用。很多人应该都知道，HashMap的基本实现是数组+链表（从JDK1.8开始已经变成了数组+链表+红黑树），而这个方法的作用也很简单：

当数组并未初始化时，对数组进行初始化；
若数组已经初始化，则对数组进行扩容，也就是创建一个两倍大小的新数组，并将原来的元素放入新数组中；

2.2 resize方法中用到的变量

HashMap中定义了很多的成员变量，而很多都在resize方法中有用到，所以为了看懂这个方法，首先需要了解这些变量的含义：

table：用来存储数据的数组，即数组+链表结构的数组部分；
threshold：阈值，表示当前允许存入的元素数量，当元素数量超过这个值时，将进行扩容；
MAXIMUM_CAPACITY：HashMap允许的最大容量，值为1<<30，也就是2^30；
DEFAULT_INITIAL_CAPACITY：HashMap的默认初始容量，值为16；
loadFactor：负载因子，表示HashMap中的元素数量可以到达总容量的百分之多少，默认是75%，也就是说，默认情况下，当元素数量达到总容量的75%时，将进行扩容；
DEFAULT_LOAD_FACTOR：负载因子的默认值，也就是0.75；

2.3 resize方法源码解读

下面就来看看resize方法的源码吧，我用注释的方式，对每一句代码进行了解读：

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * @return the table
 */
final HashMap.Node<K,V>[] resize() {
    HashMap.Node<K,V>[] oldTab = table;
    // 记录Map当前的容量
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 记录Map允许存储的元素数量，即阈值（容量*负载因子）
    int oldThr = threshold;
    // 声明两个变量，用来记录新的容量和阈值
    int newCap, newThr = 0;

    // 若当前容量不为0，表示存储数据的数组已经被初始化过
    if (oldCap > 0) {
        // 判断当前容量是否超过了允许的最大容量
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 若超过最大容量，表示无法再进行扩容
            // 则更新当前的阈值为int的最大值，并返回旧数组
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 将旧容量*2得到新容量，若新容量未超过最大值，并且旧容量大于默认初始容量（16），
        // 才则将旧阈值*2得到新阈值
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }

    // 若不满足上面的oldCap > 0，表示数组还未初始化，
    // 若当前阈值不为0，就将数组的新容量记录为当前的阈值；
    // 为什么这里的oldThr在未初始化数组的时候就有值呢？
    // 这是因为HashMap有两个带参构造器，可以指定初始容量，
    // 若你调用了这两个可以指定初始容量的构造器，
    // 这两个构造器就会将阈值记录为第一个大于等于你指定容量，且满足2^n的数（可以看看这两个构造器）
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    // 若上面的条件都不满足，表示你是调用默认构造器创建的HashMap，且还没有初始化table数组
    else {               // zero initial threshold signifies using defaults
        // 则将新容量更新为默认初始容量（10）
        // 阈值即为（容量*负载因子）
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    // 经过上面的步骤后，newCap一定有值，但是若运行的是上面的第二个分支时，newThr还是0
    // 所以若当前newThr还是0，则计算出它的值（容量*负载因子）
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }

    // 将计算出的新阈值更新到成员变量threshold上
    threshold = newThr;

    // 创建一个记录新数组用来存HashMap中的元素
    // 若数组不是第一次初始化，则这里就是创建了一个两倍大小的新数组
    @SuppressWarnings({"rawtypes","unchecked"})
    HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
    // 将新数组的引用赋值给成员变量table
    table = newTab;

    // 开始将原来的数据加入到新数组中
    if (oldTab != null) {
        // 遍历原数组
        for (int j = 0; j < oldCap; ++j) {
            HashMap.Node<K,V> e;
            // 若原数组的j位置有节点存在，才进一步操作
            if ((e = oldTab[j]) != null) {
                // 清除旧数组对节点的引用
                oldTab[j] = null;
                // 若table数组的j位置只有一个节点，则直接将这个节点放入新数组
                // 使用 & 替代 % 计算出余数，即下标
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 若第一个节点是一个数节点，表示原数组这个位置的链表已经被转为了红黑树
                // 则调用红黑树的方法将节点加入到新数组中
                else if (e instanceof HashMap.TreeNode)
                    ((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);

                // 上面两种情况都不满足，表示这个位置是一条不止一个节点的链表
                // 以下操作相对复杂，所以单独拿出来讲解
                else { // preserve order
                    HashMap.Node<K,V> loHead = null, loTail = null;
                    HashMap.Node<K,V> hiHead = null, hiTail = null;
                    HashMap.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;
                    }
                }
            }
        }
    }
    // 将新创建的数组返回
    return newTab;
}

上面的代码中，最后一部分比较难理解，所以我将在下面单独拿出来讲解。

2.4 resize方法中的链表拆分

resize方法中的最后一部分，是将原数组中的一条链表的节点，放入到扩容后的新数组中，而这一部分相对来说比较难理解。首先我们得知道是怎么实现的，然后再来逐句分析代码。

首先，我们得知道一个结论，那就是：原数组中一条链表上的所有节点，若将它们加入到扩容后的新数组中，它们最多将会分布在新数组中的两条链表上。

在HashMap中，使用按位与运算替代了取模运算来计算下标，因为num % 2^n == num & (2^n - 1)，而HashMap的容量一定是2^n，所以可以使用这条定理（这里我假设大家已经了解了HashMap的容量机制，若不了解的，可以先看看我最上面给出的那篇博客）。我们看下面这张图，左边是扩容前的数组+链表，右边是扩容后的数组+链表，链表矩形中的数字表示节点的hash值。左边数组的容量为2^3==8，只包含一条四个节点的链表，右边数组的容量为2^4 == 16，左边链表上的节点重新存储后，变成了右边两条链表。正对应了我们上面说的结论。

那这个结论是怎么来的呢？我们先说左边第一个节点，它的hash值是2，转换成二进制就是0010，而容量为2^3 == 8，通过num % 2^n == num & (2^n - 1)这个公式，我们知道2与容量8的余数是2 & （8 - 1） == 0010 & 0111 == 0010。任何数与0111做与运算（&），实际上就是取这个数二进制的最后三位。而扩容之后，容量变成了2^4 == 16，这时候，取模就是与16-1 == 15做与运算了，而15的二进制是1111，我们发现，1111与之前的0111唯一的区别就是第四位也变成了1（以下说的第几位都是从右往左）。而2 & 15 == 0010 & 1111 == 0010，和0010 & 0111 结果是一样的。为什么？因为0010的第四位是0，所以从0111变成1111，并不会对计算结果造成影响，因为0和任何数做与运算，结果都是0。所以扩容后，2这个节点，还是放在数字下标为2的位置。我们在来看看剩下的三个数：

hash值为10，转换成二进制1010，1010的第四位为1，所以 1010 & 0111 != 1010 & 1111

hash值为18，转换成二进制10010，10010的第四位为0，所以 10010 & 0111 == 10010 & 1111
    
hash值为26，转换成二进制11010，11010的第四位为1，所以 11010 & 0111 != 11010 & 1111

所以扩容后，余数是否发生改变，实际上只取决于多出来的那一位而已，那一位只有两种结果：0或者1，所以这些节点的新下标最终也只有两种结果。而多出来的那一位是哪一位呢？8转换成二进制是1000，而从8扩容到16，取余的数从0111变成了1111，多出的这个1刚好在第四位，也就是1000中，唯一一个1所在的位置；16的二进制是10000，扩容成32后，取余的数从1111变成11111，在第五位多出了一个1，正好是10000的1所在的位置。所以我们可以知道，扩容后，节点的下标是否需要发生改变，取决于旧容量的二进制中，1那一位。所以容量为8，扩容后，若节点的二进制hash值的第四位为0，则节点在新数组中的下标不变；若为1，节点的下标改变，而且改变的大小正好是+8，因为多出了最高位的1，例如1010 & 0111 = 0010，而1010 & 1111 = 1010，结果相差1000，也就是旧容量的大小8；所以若下标要发生改变，改变的大小将正好是旧数组的容量。

我们如何判断hash值多出来的那一位是0还是1呢，很简单，只要用hash值与旧容量做与运算，结果不为0表示多出的这一位是1，否则就是0。比如说，容量为8（二进制1000），扩容后多出来的是第四位，于是让hash值与1000做与运算，若hash值的第四位是1，与1000做与运算后结果就是1000，若第四位是0，与1000做与运算后就是0。好，下面我们来看看代码吧：

// 创建两个头尾节点，表示两条链表
// 因为旧链表上的元素放入新数组中，最多将变成两条链表
// 一条下标不变的链表，一条下标+oldCap
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.Node<K,V> next;

// 循环遍历原链表上的每一个节点
do {
    // 记录当前节点的下一个节点
    next = e.next;
    // 注意：e.hash & oldCap这一步就是前面说的判断多出的这一位是否为1
    // 若与原容量做与运算，结果为0，表示将这个节点放入到新数组中，下标不变
    if ((e.hash & oldCap) == 0) {
        // 若这是不变链表的第一个节点，用loHead记录
        if (loTail == null)
            loHead = e;
        // 否则，将它加入下标不变链表的尾部
        else
            loTail.next = e;
        // 更新尾部指针指向新加入的节点
        loTail = e;
    }
    // 若与原容量做与运算，结果为1，表示将这个节点放入到新数组中，下标将改变
    else {
        // 若这是改变下标链表的第一个节点，用hiHead记录
        if (hiTail == null)
            hiHead = e;
        // 否则，将它加入改变下标链表的尾部
        else
            hiTail.next = e;
        // 更新尾部指针指向新加入的节点
        hiTail = e;
    }
} while ((e = next) != null);

// 所有节点遍历完后，判断下标不变的链表是否有节点在其中
if (loTail != null) {
    // 将这条链表的最后一个节点的next指向null
    loTail.next = null;
    // 同时将其放入新数组的相同位置
    newTab[j] = loHead;
}
// 另一条链表与上同理
if (hiTail != null) {
    hiTail.next = null;
    // 这条链表放入的位置要在原来的基础上加上oldCap
    newTab[j + oldCap] = hiHead;
}

三、总结

resize的逻辑并不算太难，可能只有链表拆分这一部分比较难理解。为了能尽可能地说清楚，我描述的可能有点啰嗦了，希望对看到的人能够有所帮助吧。

四、参考

https://blog.csdn.net/weixin_41565013/article/details/93190786