resize()方法的作用

resize()方法會在HashMap的鍵值對達到“閾值”後進行數組擴容，而擴容時會調用resize()方法，此外，在jdk1.7中數組的容量是在HashMap初始化的時候就已經賦予，而在jdk1.8中是在put第一個元素的時候才會賦予數組容量，而put第一個元素的時候也會調用resize()方法。

resize()方法jdk1.8中和1.7中實現有什麼不同

JDK1.7

resize()源碼

解釋

在1.7中，resize()方法的原理為（圖中假設hashMap的數組大小為4.實際上默認是16）

1. 先新建一個數組，數組長度為原數組的2倍
2. 循環遍歷原數組的每一個鍵值對的，得到鍵的Hashcode然後與新數組的長度（此處為8）進行&運算得到新數組的位置。然後把鍵值對放到對應的位置。故擴容之後可能會變成這樣
   而在jdk1.8中雖然擴容之後的數組也是一樣是上面那樣，但是在計算元素位置的方式上不太一樣，jdk1.7需要與新的數組長度進行重新hash運算，這個方式是相對耗性能的，而在1.8中對這一步進行了優化，下面我們來詳細解釋一下進行了那些優化。

JDK1.8

resize() 源碼

<code>final Node[] resize() {
        Node[] 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[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node 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)e).split(this, newTab, 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;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273/<code>

這一長串的代碼確實看的很暈，但是如果你跟著源代碼一步步調試其實上面部分理解並不困難，困難的點在於for循環中的代碼。

<code>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;
   newTab[j] = loHead;
}
if (hiTail != null) {
   hiTail.next = null;
   newTab[j + oldCap] = hiHead;  //這裡很重要，新的位置為原老所處的位置+原數組的長度，為什麼是這個值呢？下面解釋
}
12345678910111213141516171819202122232425262728/<code>

而newTab[j + oldCap] = hiHead;這一步，是一個非常巧妙的地方，也是本文分析的重點。

解釋

經過觀測可以發現，我們使用的是2次冪的擴展(指長度擴為原來2倍)，所以，經過rehash之後，**元素的位置要麼是在原位置，要麼是在原位置再移動2次冪的位置。對應的就是下方的resize的註釋。**對應的就是下方的resize的註釋。

看下圖可以明白這句話的意思，n為table的長度，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴容後key1和key2兩種key確定索引位置的示例，其中hash1是key1對應的哈希值(也就是根據key1算出來的hashcode值)與高位與運算的結果。

因此，我們在擴充HashMap的時候，不需要像JDK1.7的實現那樣重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”。這個設計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由於新增的1bit是0還是1可以認為是隨機的，因此resize的過程，均勻的把之前的衝突的節點分散到新的bucket了。這一塊就是JDK1.8新增的優化點。有一點注意區別，JDK1.7中rehash的時候，舊鏈表遷移新鏈表的時候，如果在新表的數組索引位置相同，則鏈表元素會倒置，但是從上圖可以看出，JDK1.8不會倒置。

再解釋：為什麼剛好原位置+原數組長度就會等於新的數組中的位置呢？

要搞明白這個問題首先要清楚

1. HashMap的數組長度恆定為2的n次方，也就是說只會為2 4 8 16 。。。。。這種數。源碼中有限制，也就是說即使你創建HashMap的時候是寫的

<code>Map<string> hashMap = new HashMap<>(13);
1/<string>/<code>

最後數組長度也會變成16，而不是你的13. 會取與你傳入的數最近的一個2的n次方的數。

<code>public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
123456789101112/<code>

<code>static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
123456789/<code> 

那麼明確這一點有什麼用呢？我們知道2,4,8,16,32所對應的二進制分別為

<code>2：  0000 0000 0000 0000 0000 0000 0000 0010
4：  0000 0000 0000 0000 0000 0000 0000 0100
8：  0000 0000 0000 0000 0000 0000 0000 1000
16： 0000 0000 0000 0000 0000 0000 0001 0000
32:  0000 0000 0000 0000 0000 0000 0010 0000
12345/<code>

而我們知道，0在做位與運算時與任何一個數運算結果都恆為0

<code>0 & 1 = 0
0 & 0 = 0
12/<code>

故看源碼中

<code> if ((e.hash & oldCap) == 0) 
1/<code>

這一步是否為0只需要看元素的二進制數對應數組長度的二進制數1那個位置是否為0.假設某個元素的hashcode為52：

而假設某個元素的hashcode為100：

而通過源碼可以看出0就還是在原來的位置。不為0就需要變動位置了，新的位置為元素在原數組的位置+原數組的長度，那麼為什麼是這樣呢？我們接著看看之前我們先使用jdk1.7中的方式重新進行hash運算HashMap在運算元素位置的時候使用為 數組長度-1。也就是15.31這種數15 31 對應的二進制為

<code>15：0000 0000 0000 0000 0000 0000 0000 1111
31: 0000 0000 0000 0000 0000 0000 0001 1111 

12/<code>

這裡需要注意的是上面之所以是16&52，16&100是因為只是做判斷而已，而非計算位置的方式，計算位置使用的事length-1.千萬不要看迷糊了。

<code> if ((e.hash & oldCap) == 0)  //僅僅是判斷元素是否需要換位置，不要理解為元素的新位置
1/<code>

這一步才是計算位置，使用的是length-1.

16擴容後變成32.那麼1.7中計算元素的位置方式為 31&52, 31&100.我們把他與擴容前的15&52。15&100做對比看看

可以看到，擴容前和擴容後的位置是否一樣完全取決於多出來的那一位是與新數組計算後值是為0還是1.為0則新位置與原位置相同，不需要換位置，不為零則需要換位置。而為什麼新的位置是原位置+原數組長度，是因為每次換的位置只是前面多了一個1而已。為什麼是前面多1，因為數組擴容為原來的兩倍也是高位進1，比如15是0000 1111，而31就是0001 1111. 那麼新位置的變化的高位進1為。而每一次高位進1都是在加上原數組長度的過程。

正好1+2=3 3+4=7 7+8=15 。也就驗證了新的位置為原位置+原數組長度。

總結

jdk1.8中在計算新位置的時候並沒有跟1.7中一樣重新進行hash運算，而是用了原位置+原數組長度這樣一種很巧妙的方式，而這個結果與hash運算得到的結果是一致的，只是會更塊。

閱讀更多 Gmy傻瓜珍藏版 的文章

關鍵字: Node 位置 oldCap