---

前言

上一篇文章已经解析过JDK8中HashMap的put和putVal底层源码，这篇文章顺着上一篇文章的节奏，来解析一下另外一个非常重要的方法：resize方法。

---

一、resize方法

在上一篇文章中已经解析了HashMap中的putVal方法，在putVal方法中还调用了一些方法，如下图所示：

首先我们先来看一下resize()方法，resize()顾名思义就是重新调整大小的意思，它有以下几种作用：
1.当数组还没初始化的时候，初始化一个数组大小。
2.当HashMap存放的元素数量超过门槛（负载因子*数组长度），需要进行扩容。
3.treeifyBin()方法中也调用了resize()方法，后续会讲解到。

首先我们来看其他一个问题，我们在上一篇文章中说过，如果我们创建HashMap的时候指定了一个长度，则会调用tableSizeFor返回一个大于等于这个数的最小二次方数，它会把这个数暂时存储到threshold属性中，记住这里，这个属性后续会用到。

this.threshold = tableSizeFor(initialCapacity);
1

接着我们直接来看一下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;
        // 如果⽼数组⼤⼩⼤于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;
        //表示要初始化数组，用户未指定初始化容量，⽤默认值16，并计算新阈值
        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"})
        //⽣成新数组，并赋值给table属性
        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;
                    // 如果该位置上的元素是TreeNode，则对这颗红⿊树进⾏转移
                    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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

resize方法的代码比较长，现在用文字来总结一下resize方法具体做了什么：

1. 首先记录当前数组信息，当前数组、数组长度还有扩容阈值。
2. 接着就到了一个if-elseif-else的代码块，这些就是用来判断当前是进行初始化操作还是扩容操作，如果是扩容操作则需要进行双倍扩容，如果是初始化数组则需要设置数组容量。
3. 如果是扩容操作或者初始化的时候用户指定了初始容量，则要⽤新数组的大小重写计算扩容阈值
4. 重新生成一个数组（无论是扩容操作还是初始化操作都需要）。
5. 如果是初始化操作，到生成数组就已经结束了，但如果是扩容操作，则把⽼数组上的元素转移到新数组上

简单总结：判断当前数组是初始化还是扩容，初始化就根据情况设置数组长度并创建数组；如果是扩容，需要双倍扩容并转移上面的元素。

---

二、转移元素的过程

在JDK1.7中，HashMap的数据结构为数组+链表，转移元素的过程也很暴力，双重循环，遍历每个元素，然后把每个元素放在新数组中该放的地方去。

由于JDK1.8中HashMap的数据结构已经优化为数组+单向链表+双向链表+红黑树，转移起来就比1.7的版本要复杂。

转移的时候需要遍历旧数组的每⼀个位置，可能会发生四种情况：
1.如果该位置上没有元素，不做处理
2.如果该位置只有⼀个元素，则直接转移到新数组上：newTab[e.hash & (newCap - 1)] = e
3.如果该位置上的元素是TreeNode，则对这颗红⿊树进⾏转移 ： ((TreeNode)e).split(this, newTab, j, oldCap);
4.否则，该位置上是⼀个链表，则要转移该链表 ，最后会拆分为高位（原来的位置+旧数组的长度）和低位链表(在新数组中也是原来的位置)。判断元素在低位链表和高位链表的条件是：(e.hash & oldCap) == 0，如果这个值等于0就放在低位链表，如果不是则放在高位链表。

为什么拿(e.hash & oldCap) == 0判断？假设扩容前是原数组长度是16
0001 0000
&
...? ....
-----------------------
结果为0的话就是在低位链表，否则在高位

其实我们也可以自己验证一下，假设扩容前是原数组长度是16，扩容后就是32，拿i = (n - 1) & hash，则只会得到两个结果，就是低位链表和高位链表存放的位置
31：   0001  1111
&
hash:  ...?  0101
--------------------------
i:     000?  0101    ->  5（原下标）或者21（oldtable长度+原下标）
1
2
3
4
5
6
7
8
9
10
11
12
13

因此，我们在扩充HashMap的时候，只需要看看原来的hash值高一位的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”，可以看看下图为16扩充为32的resize示意图：

---

总结

本章主要解析了JDK8中HashMap的resize方法的底层源码，这个方法主要有两个作用，一是用来初始化数组，二是用来扩容，而扩容的时候就需要转移元素，转移元素又分为四种情况。同时在转移红黑树的时候还提到了一个方法split()方法，在以后的文章中将会解析到。

---