关于 resize 方法

HashMap 每添加一个元素，size 就会加一，当超过 threshold 时会触发自身的扩容机制，也就是调用 resize 方法对自身进行扩容。

添加一个元素时，如果存储数据表 table 为空，会调用 resize 扩容。再计算这个元素的 hash 值，根据一定规则转换为索引值，查存储数据表 table 索引位置是否已经存放了元素。如果没有，直接放入数据表 table 中，如果有，判断两个元素是否相同，或调用元素的 equals 方法比较，如果结果为真，则判定该元素为重复元素，放弃添加，如果不相同，则添加到链表的末尾。在 Java 8 中，如果一条链表的元素个数大等于 TREEIFY_THRESHOLD（ 默认 8 ） - 1，并且 table 的大小 >= MIN_TREEIFY_CAPACITY（默认 64 ），就会将该索引位置的链表转换为红黑树。

看一下 HashMap add 方法的源码，resize 两处被调用的地方分别是：
1）table 为空时，调用 resize 扩容 table（初始化）；
2）table size 大于 threshold，调用 resize 扩容。（此时 table size 已经超过了总容量的 75%，调用 resize 扩容至原容量的 2 倍）

从哪里看出来是 2 倍呢？下面借助一个案例来分析 resize 的源码。

这里先附上 resize 方法的源码：

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            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;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        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;
                        }
                    }
                }
            }
        }
        return newTab;
    }

案例代码

以下面的代码为例，添加 100 个元素到 HashSet 中，看下什么时候会执行 resize ，以及 resize 究竟做了什么。

public class Main {
    public static void main(String[] args) {
        HashSet set = new HashSet();
        for (int i = 0; i < 100; i++) {
            set.add(i);
        }
        System.out.println(set);
    }
}

源码分析

1、table 为 null 时调用 resize

for 循环 i 为 0 时，尚未调用 add 方法时，set 为空。第 1 次调用 add 方法，debugg 进去看一下。

HashSet 的 add 调用了 HashMap 的 put 方法，step into

HashMap 的 put 调用了自身的 putVal 方法，step into 到 putVal

此时 table 为 null ，此处第一次调用 resize ，我们继续 step into 进去看一下

resize 方法先把 table 赋给 oldTab ，并且获取 oldTab 的长度，此时 table 为 null ，所以 oldCap 是 0.

在获取当前的 threshold 赋给 oldThr ，此时因为 table 是 null ，threshold 是默认值 0，因此 oldThr 也是 0 。再定义了两个辅助变量，用于存储扩容后的 capacity 和 threshold ，分别为 newCap 和 newThr，默认为 0。

此时因为 oldCap 为 0 ，所以 if 的表达式不成立，判断下一个 if

oldThr 也为 0 ，所以这个 else if 表达式也不成立

所以会执行到这个 else ，也就计算出了 newCap 和 newThr 的值。为了搞懂下面两个玩意儿是啥，看下定义。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;

DEFAULT_INITIAL_CAPACITY 为 16，不难看出，这是 HashMap 给的一个默认初始大小。
DEFAULT_LOAD_FACTOR 是默认加载因子，数值是 0.75，标志着扩容占比，如果当前使用空间超过 75% ，则进行扩容。

newCap：因为是第一次调用 resize 给 table 扩容，因此 HashMap 给了 16 的空间大小。
newThr：计算新的扩容阈值，当 newCap 被计算出来后，新的扩容阈值也要更新，所以是默认加载因子乘当前的 capacity 也就是 DEFAULT_INITIAL_CAPACITY，最终计算出来是 12。（16*0.75=12）

这时，newCap 和 newThr 的值都被计算出来，并且 threshold 的值也更新为 newThr 了。此时 threshold 和 newThr 为 12。
所以此时，按照预计扩容后的大小 newCap 创建了一个容量为 newCap的 newTab 替换了原本为 null 的 table。

紧接着，判断 oldTab 是否为空，我们知道，oldTab 是在进入 resize 时，将 table 赋给 oldTab 的。原本 table 为 null，所以此时的 oldTab 也为 null ，自然 if 里的表达式条件也不为真，因此不执行 if 语法块里的逻辑。

执行到这里，就将扩容后的 table 对象也就是 newTab 返回了。通过 debugger 我们可以看到，HashMap 里的 table 长度已经扩容至 16 了。

至此，当 table 为 null 时的 resize 已经执行完毕了。接下来我们看另一种情况，也就是刚才被跳过的 if 分支，当 table 不为 null 时，resize 都做了些什么呢？

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
static final float DEFAULT_LOAD_FACTOR = 0.75f;

2、table 非空时调用 resize

可以看到，当 for 循环执行一次后，i++ ，i 为 1 时，HashMap 的 table 的长度已经被扩容至 16，并且里面放了一个元素 Integer 0。

那么问题来了，什么时候会再触发 resize 呢？为了方便阅读，我把开头的 HashMap add 方法源码附在下面：

可以看到，当 size 大于 threshold 时，才会再触发一次 resize 。threshold 保存的是扩容阈值，关于计算方法上面已经讲过了。那么此时 threshol 的值是多少你还记得吗？答案是 12 ，因为经历过第一次扩容，table 的容量从 0 增加到了 16，threshold = 16 * 0.75 = 12 。（本文的案例中使用的是无参构造器，因此 threshold 等于 DEFAULT_LOAD_FACTOR 乘容量，DEFAULT_LOAD_FACTOR 的默认值是 0.75 ）。这一点通过 debugger 也可以得到验证。

所以我们可以断定，当 set 已经添加了 12 个元素，准备添加第 13 个元素时，会再触发一次 resize ，也就是 for 循环 i 等于 12 的这一轮 add 操作。
下面我们分析一下。

此时我们可以看到，for 循环的 i 已经来到了 12 ，也就是第 13 次添加元素，table 中也已经塞了 12 个元素，现在我们 step into

调用 HashMap 的 put 方法，继续 step into

调用了 HashMap putVal ，继续 step into 到 putVal 中去

跳过上面无关的 add 方法逻辑，直接来到关键点，可以看到 ++ size 后，size 值大于 threshold 的值（13>12），因此这时会触发第二次 resize ，我们 step into 进去看一下。

ok，现在终于来到了 resize 方法内部，重头戏来了。
先将 table 赋给 oldTab ，再获取 oldCap、oldThr 的值，分别是 16 和 12。也就是说，if 表达式的值为真，因为 oldCap=16 大于 0 。

进入 if 语法块，先判断 oldCap 的大小是否超限了。此处 MAXIMUM_CAPACITY 是 2 的 30 次方。oldCap 等于 16，显然没有超限，所以这个 if 的表达式结果为 false ，不执行 if 语法块的内容。

来到 else - if 语法块，先判断表达式结果是否为 true。
1）newCap = oldCap << 1：将 oldCap 左移一位，赋给 newCap。（可以理解为 oldCap =2 ），因此，newCap 等于两倍的 oldCap ，也就是 HashMap 预计要扩容至原大小的 2 倍。
2）newCap < MAXIMUM_CAPACITY ：然后判断 newCap 的值有没有超限，显然这里 newCap 等于 162 = 32 ，不会超限，因此这个 else-if 表达式的前一个条件成立。
3）oldCap >= DEFAULT_INITIAL_CAPACITY：这边条件肯定成立，因为 oldCap 等于 16，大等于默认的 capacity 。（DEFAULT_INITIAL_CAPACITY 的值为 16 ）

上面 else-if 的表达式为真，所以执行 else-if 语法块中的语句，此处 newThr 显然是等于 oldThr*2 ，也就是将原来的阈值乘 2 ，因为此时 newCap 的值已经由 16 增加至 32 了，自然扩容阈值也应该要乘 2。

经过上面的计算，newThr 等于 24，不等于 0 ，因此这个 if 表达式为 false ，不成立，对应语法块的内容也不执行。

然后 newThr 的值就赋给了 threshold ，这标志着 HashMap 的扩容阈值被提高了 2 倍，由 12 变为 24 了。并且，按照 newCap 的值，HashMap 新建了一个长度为 newCap 的 Node 数组，将其赋给了 table 。这时 HashMap 要干什么我们已经不难猜出来了，肯定是要把旧的值一个一个塞回去，这就完成了扩容。

继续往下，因为此时 oldTab 中存放着扩容前的旧值，因此肯定不为 null ，表达式的值为 true。

下面这一段 for 循环才是 resize 方法理解的难点。先判断当前 oldTab[j] 节点是否为 null ，如果为 null 则 j++ ，进入下一个循环。

当前节点不为空的情况下，有三种情况。
1）当前节点既不是链表，也不是红黑树
2）当前节点是红黑树
3）当前节点是链表
依次对应 if-else if -else 三个语法块
如果哈希算法给力，理想状态下是尽量避免哈希冲突，也就是尽力回避节点拉出一个链表，或链表过长再红黑树化。

本文的案例这个例子，并不会产生冲突，因此后两种情况不会进入，但难点也就是在这后两种情况。因为第一种情况比较理想，在计算出元素在新 table 的索引值后，就直接赋值过去了，旧值之所以被赋 null ，是因为帮助 jvm gc 。

前两种情况就不讲了，重点看第三种，看一下 HashSet 扩容时遇到链表时，是如何处理的。

先是定义了 5 个辅助变量。

然后是一个 do-while 循环，主要解决的是将链表上每个节点按照一定规则均匀分配到新 table 的对应索引位置。

最后一步，把两个链表的头的地址赋给 newTab 对应索引位置，就完成了 oldTab[ j ] 这个位置的链表分配。

https://www.bilibili.com/video/BV1xv411L7vr