HashMap底層分析_數組擴容

1. resize()方法主要用于對數組進行初始化 或 擴容

2. 初始化：HashMap底層數組初始化采用延時機制，被推遲到put()方法中，但主要還調用resize()方法來完成。HashMap底層數組初始化兩種情況，建立HashMap對象時：指定初始容量 和 不指定初始容量。

• 如果指定初始容量，則這個初始化容量會被tableSizeFor()方法進行調整，以確定數組長度一定為2的整數幂 (指定的初始容量在HashMap構造函數中經tableSizeFor()方法處理後，賦給threshold門檻值，用于熱resize()方法中做記錄使用，并且在resize()方法中記錄完後，會被修改成threshold = 容量值 * 加載因子)。
• 不指定初始容量，則使用預設初始化容量16

3. 擴容：數組每次擴容為原來的兩倍，并且數組擴容後，需要将原數組的節點對象轉移到擴容數組中。

//數組長度達到門檻值
if (++size > threshold)
	//擴容
    resize();
           

final Node<K,V>[] resize() {
	//将table數組賦給oleTab，用oldTab來記錄
    Node<K,V>[] oldTab = table;
    //用oldCap記錄原數組長度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //用oldThr記錄門檻值(如果建立hashMap對象時指定了初始容量，則這個threshold為經過tableSizeFor()處理過的初始容量值，具體可以看HashMap構造函數)
    int oldThr = threshold;
    //分别用newCap、newThr來記錄擴容後的數組長度和門檻值
    int newCap, newThr = 0;
    
    //原數組oldTab長度大于0，則擴容
    if (oldCap > 0) {
    
    	//oldTab >=最大限制容量，則threshold取最大值，并傳回oldTab
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        
        //反之，oldTab，oldThr均擴容為原來的兩倍，并分别賦給newTab 和 newThr
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold 雙倍門檻值
    }
    
    //數組初始化(建立hashMap對象時指定初始容量)，長度為經過tableSizeFor()處理過的初始容量值
    else if (oldThr > 0) // initial capacity was placed in threshold
		/* 注意：這個條件語句中的oldThr的值，為經過tableSizeFor()處理過的初始容量值，
		 *      因為它在HashMap構造函數中又被賦給了threshold，然後在resize()方法開頭又被賦給了oldThr
		 */
        newCap = oldThr;
     
    //數組初始化(建立hashMap對象時不指定初始容量)，長度為預設初始化容量16
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        //門檻值newThr = 16 * 0.75 = 12
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    
    /** 數組初始化(建立hashMap對象時指定初始容量)時，才會走這一步。
     * 因為：
     *     HashMap構造函數中，将經過tableSizeFor()處理過的初始容量值 賦給類了threshold。
     * 		是以這一步的目的就是要将threshold的值進行調整，(否則threshold就等于容量值了，而不是門檻值)
     */
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //newThr記錄完後，反過來賦給threshold
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    	//建立一個空數組，長度為原來的兩倍(如果是首次初始化，則長度為它的初始容量)
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    
    //如果原數組oldTab不為空，将原數組oldTab的node節點元素，移動到擴容後的數組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;
                    }
                }
            }
        }
    }
    傳回newTab
    return newTab;
}