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;
}