一、概述
HashMap的resize方法的作用:在向HashMap裡put元素的時候,HashMap基于擴容規則發現需要擴容的時候會調用該方法來進行擴容。
二、方法解析
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) { // 如果老數組長度大于0,說明已經存在元素
// PS1
if (oldCap >= MAXIMUM_CAPACITY) { // 如果數組元素個數大于等于限定的最大容量(2的30次方)
// 擴容閥值設定為int最大值(2的31次方 -1 ),因為oldCap再乘2就溢出了。
threshold = Integer.MAX_VALUE;
return oldTab; // 傳回老的元素數組
}
/*
* 如果數組元素個數在正常範圍内,那麼新的數組容量為老的數組容量的2倍(左移1位相當于乘以2)
* 如果擴容之後的新容量小于最大容量 并且 老的數組容量大于等于預設初始化容量(16),那麼新數組的擴容閥值設定為老閥值的2倍。(老的數組容量大于16意味着:要麼構造函數指定了一個大于16的初始化容量值,要麼已經經曆過了至少一次擴容)
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// PS2
// 運作到這個else if 說明老數組沒有任何元素
// 如果老數組的擴容閥值大于0,那麼設定新數組的容量為該閥值
// 這一步也就意味着構造該map的時候,指定了初始化容量。
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 能運作到這裡的話,說明是調用無參構造函數建立的該map,并且第一次添加元素
newCap = DEFAULT_INITIAL_CAPACITY; // 設定新數組容量 為 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 設定新數組擴容閥值為 16*0.75 = 12。0.75為負載因子(當元素個數達到容量了4分之3,那麼擴容)
}
// 如果擴容閥值為0 (PS2的情況)
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE); // 參見:PS2
}
threshold = newThr; // 設定map的擴容閥值為 新的閥值
@SuppressWarnings({"rawtypes","unchecked"})
// 建立新的數組(對于第一次添加元素,那麼這個數組就是第一個數組;對于存在oldTab的時候,那麼這個數組就是要需要擴容到的新數組)
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 将該map的table屬性指向到該新數組
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) // 如果元素沒有有下一個節點,說明該元素不存在hash沖突
// PS3
// 把元素存儲到新的數組中,存儲到數組的哪個位置需要根據hash值和數組長度來進行取模
// 【hash值 % 數組長度】 = 【 hash值 & (數組長度-1)】
// 這種與運算求模的方式要求 數組長度必須是2的N次方,但是可以通過構造函數随意指定初始化容量呀,如果指定了17,15這種,豈不是出問題了就?沒關系,最終會通過tableSizeFor方法将使用者指定的轉化為大于其并且最相近的2的N次方。 15 -> 16、17-> 32
newTab[e.hash & (newCap - 1)] = e;
// 如果該元素有下一個節點,那麼說明該位置上存在一個連結清單了(hash相同的多個元素以連結清單的方式存儲到了老數組的這個位置上了)
// 例如:數組長度為16,那麼hash值為1(1%16=1)的和hash值為17(17%16=1)的兩個元素都是會存儲在數組的第2個位置上(對應數組下标為1),當數組擴容為32(1%32=1)時,hash值為1的還應該存儲在新數組的第二個位置上,但是hash值為17(17%32=17)的就應該存儲在新數組的第18個位置上了。
// 是以,數組擴容後,所有元素都需要重新計算在新數組中的位置。
else if (e instanceof TreeNode) // 如果該節點為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; // 按命名來翻譯的話,應該叫高位首尾節點
// 以上的低位指的是新數組的 0 到 oldCap-1 、高位指定的是oldCap 到 newCap - 1
Node<K,V> next;
// 周遊連結清單
do {
next = e.next;
// 這一步判斷好狠,拿元素的hash值 和 老數組的長度 做與運算
// PS3裡曾說到,數組的長度一定是2的N次方(例如16),如果hash值和該長度做與運算,那麼該hash值可參與計算的有效二進制位就是和長度二進制對等的後幾位,如果結果為0,說明hash值中參與計算的對等的二進制位的最高位一定為0.
//因為數組長度的二進制有效最高位是1(例如16對應的二進制是10000),隻有*..0**** 和 10000 進行與運算結果才為00000(*..表示不确定的多個二進制位)。又因為定位下标時的取模運算是以hash值和長度減1進行與運算,是以下标 = (*..0**** & 1111) 也= (*..0**** & 11111) 。1111是15的二進制、11111是16*2-1 也就是31的二級制(2倍擴容)。
// 是以該hash值再和新數組的長度取摸的話mod值也不會放生變化,也就是說該元素的在新數組的位置和在老數組的位置是相同的,是以該元素可以放置在低位連結清單中。
if ((e.hash & oldCap) == 0) {
// PS4
if (loTail == null) // 如果沒有尾,說明連結清單為空
loHead = e; // 連結清單為空時,頭節點指向該元素
else
loTail.next = e; // 如果有尾,那麼連結清單不為空,把該元素挂到連結清單的最後。
loTail = e; // 把尾節點設定為目前元素
}
// 如果與運算結果不為0,說明hash值大于老數組長度(例如hash值為17)
// 此時該元素應該放置到新數組的高位位置上
// 例:老數組長度16,那麼新數組長度為32,hash為17的應該放置在數組的第17個位置上,也就是下标為16,那麼下标為16已經屬于高位了,低位是[0-15],高位是[16-31]
else { // 以下邏輯同PS4
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; // 例:hash為 17 在老數組放置在0下标,在新數組放置在16下标; hash為 18 在老數組放置在1下标,在新數組放置在17下标;
}
}
}
}
}
return newTab; // 傳回新數組
}