Java1.8 對HashMap的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;
	// 隻有非第一次擴容才會進來（第一次擴容在第一次put）
	if (oldCap > 0) {
		// oldCap最大為MAXIMUM_CAPACITY(2^30),可檢視帶參構造方法①
		if (oldCap >= MAXIMUM_CAPACITY) {
			 /**
                 * threshold變成MAX_VALUE(2^31-1),随它們碰撞。但是oldCap不改變,
                 * 因為如果oldCap翻倍就為負數了,如果指派為MAX_VALUE,
                 * 參考 Map容量為什麼不能為MAX_VALUE②
                 */
			threshold = Integer.MAX_VALUE;
			return oldTab;
		}
		// 容量翻倍
		else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
				 oldCap >= DEFAULT_INITIAL_CAPACITY)
			/**
             * 為什麼需要判斷oldCap >= DEFAULT_INITIAL_CAPACITY呢？
             * 應該是容量較小時 capacity * loadFactor造成的誤差比較大,
             * 例如初始化容量為2 threshold則為1,如果每次擴容threshold都翻倍,
             * 那負載因子是0.5了。
             * 為什麼隻小于16呢？
             * 我猜測是在每次擴容都計算threshold和用位運算翻倍之間做權衡
             */
			newThr = oldThr << 1; 
	}
	// 帶參初始化會進入這裡,主要是為了重新算threshold
	else if (oldThr > 0) 
		newCap = oldThr;
	// 不帶參初始化會進入這裡
	else {               
		newCap = DEFAULT_INITIAL_CAPACITY;
		newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
	}
	// 重新算threshold
	if (newThr == 0) {
		float ft = (float)newCap * loadFactor;
		newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
				  (int)ft : Integer.MAX_VALUE);
	}
	threshold = newThr;
	// 擴容
	Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
	table = newTab;
	// 複制資料到新table中
	if (oldTab != null) {
		// 周遊Node
		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 { 
					// 之是以定義兩個頭兩個尾對象,是由于連結清單中的元素的下标在擴容後,要麼是原下标+oldCap,要麼不變,下面會證明
					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) {
						// 尾部節點next設定為null，代碼嚴謹
						loTail.next = null;
						newTab[j] = loHead;
					}
					// 新下标對應的連結清單
					if (hiTail != null) {
						hiTail.next = null;
						newTab[j + oldCap] = hiHead;
					}
				}
			}
		}
	}
	return newTab;
}

①帶參構造方法
public HashMap(int initialCapacity, float loadFactor) {
	if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
	// 容量最大為MAXIMUM_CAPACITY(2^30)
	if (initialCapacity > MAXIMUM_CAPACITY)
		initialCapacity = MAXIMUM_CAPACITY;
	if (loadFactor <= 0 || Float.isNaN(loadFactor))
		throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
	this.loadFactor = loadFactor;
	// threshold初始化為最接近initialCapacity的2的幂次方，并且大于或等于initialCapacity。但是在第一次put的時候，threshold會變成threshold * loadFactor
	this.threshold = tableSizeFor(initialCapacity);
}

②Map容量為什麼不能為MAX_VALUE
該為題可轉為：為什麼在Java1.8,每次擴容都為2的幂次方呢？
// 計算下标,下面是map的put和get中都用到計算下标的
(n - 1) & hash

當容量為MAX_VALUE(2^31-1)時,轉換成二進制
	hash
&
	0111 1111 1111 1111 1111 1111 1111 1110
-----------------------------------------------
        xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxx0
從上面可看出最低位無論hash是任何值時,都為0,也就是下标隻有2^30種可能,有2^30-1個下标沒有被使用
是以當容量為MAX_VALUE(2^31-1)時會造成一半的空間浪費,效率等同于MAXIMUM_CAPACITY(2^30)

③e.hash & oldCap
該步驟是為了計算位置是否需要移動
因為oldTab的元素下标是根據 hash(key) & (oldCap-1) 計算的,如果擴容後,計算下标是 hash(key) & (2*oldCap-1)
換成二進制就比較清晰了
           

是以，HashMap擴容的時候，不需要像Java1.7那樣重新算hash值，隻要看e.hash對應2*oldCap-1高位那個
bit是1還是0就好了，是0下标沒變，是1索引變成：原下标+oldCap,這也是Java1.8優化的地方之一。
           

參考：Java 8系列之重新認識HashMap