hashMap類中的幾個屬性
要想理清resize方法，必須先熟悉這幾個hashMap類中的幾個屬性
//HashMap的 初始容量為 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//預設的擴容因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//轉換紅黑樹的臨界值，當連結清單長度大于此值時，會把連結清單結構轉換為紅黑樹結構
static final int TREEIFY_THRESHOLD = 8;
//轉換連結清單的臨界值，當元素小于此值時，會将紅黑樹結構轉換成連結清單結構
static final int UNTREEIFY_THRESHOLD = 6;
//當數組容量大于 64 時，連結清單才會轉化成紅黑樹
static final int MIN_TREEIFY_CAPACITY = 64;
//記錄疊代過程中 HashMap 結構是否發生變化，如果有變化，疊代時會 fail-fast
transient int modCount;
//HashMap 的實際大小，可能不準(因為當你拿到這個值的時候，可能又發生了變化)
transient int size;
//存放資料的數組
transient Node<K,V>[] table;
// 擴容的門檻，有兩種情況
// 如果初始化時，給定數組大小的話，通過 tableSizeFor 方法計算，數組大小永遠接近于 2 的幂次方，
// 比如你給定初始化大小 19，實際上初始化大小為 32，為 2 的 5 次方。
// 如果是通過 resize 方法進行擴容，大小 = 數組容量 * 0.75
int threshold;
/** HashMap中的内部類 **/
//連結清單的節點 1.7之前叫Entry，1.8之後叫Node
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
//紅黑樹的節點
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {}
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;
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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = 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;
}
}
}
}
}
return newTab;
}
resize()方法體分段講解
-
第一階段：計算出新的newCap(擴容後的容量)和newThr(擴容後門檻值)
首先得到擴容之前的table數組oldTab的最大容量oldCap和門檻值oldThr，如果oldTab==null，則table數組仍指向空，還未被指派
接着設定newCap和newThr初始值為0
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
如果oldCap大于0，進入另一個if -else if分支
如果oldCap已經達到了最大容量，那麼直接傳回oldTab不做處理
如果oldCap的2倍容量仍然比最大容量小，那就說明可以繼續擴容，newCap設定為oldCap的2倍
同時将newThr設定為oldThr的2倍
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
}
如果oldCap=0，那就來到了如下判斷語句：
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
一開始我覺得很奇怪，為啥oldCap=0，oldThr可能>0呢？後來明白了，想知道這是為啥就要先對hashmap的構造方法有一定了解：
//無參構造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//帶參構造方法 設定初始容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//帶參構造方法 設定初始容量和擴容因子
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);
}
這時候比如我們使用的是無參構造方法
那麼成員常量threshold==0，table==null,也就意味着oldCap==0，這時候如果調用resize方法，它就知道此時table數組需要預設初始化了，就會直接進入如下if判斷中并初始化newCap和newThr
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
如果我們使用的是帶參構造方法，情況會有很大的不同
上文中提到的帶參構造方法有兩種，差別就是擴容因子loadFactor采用個性值還是采用預設值，不管采用何值，擴容因子隻是代表了門檻值和容量之間的比例關系
關鍵在于我們可以設定個性值initialCapacity，也就是說可以自定義table數組的初始容量是多大。不過要注意的是，table數組最終的實際初始容量大機率不是我們自定義的初始容量，為什麼呢？
public HashMap(int initialCapacity, float loadFactor) {
...
...
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
首先從這個帶參構造方法可以看到，this.threshold = tableSizeFor(initialCapacity)，也就是通過我們設定的initialCapacity，通過tableSizeFor方法将傳回值賦給成員變量threshold
tableSizeFor方法我們隻需要知道它的傳回值有什麼特點就好，它會傳回一個整數，這個整數是一個與initialCapacity最接近的，并且比initialCapacity大的 2的n次幂的整數。例如我們設定initialCapacity==7，那麼return tableSizeFor(7)==8
是以我們現在清楚，盡管調用帶參構造方法後threshold賦上值了，但是調用resize方法給table數組指派之前，table數組就仍然指向null，對應的lodCap==0，而oldThr=threshold>0,是以以下分支結構是有可能執行到的：
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
我們看到改判斷成立時，将oldThr指派給了newCap，也就是說對于個性設定初始容量後，數組的容量最後等于首次被指派的threshold。
然後到了如下if判斷語句
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
這個if判斷語句中newThr==0，其實newThr==0的情況就是之前所說的oldCap==0&&oldThr>0的情況，将newCap乘上一個擴容因子，因為有可能結果為浮點型，是以用float類型的局部變量ft接收，最後再将ft轉成int類型指派給newThr門檻值，前提是newCap還未達到最大容量，否則就直接将最大容量賦給newThr。
threshold = newThr;
最後，不管執行上面哪種if判斷語句，将得到的newThr指派給threshold。這裡注意對于進入if (newThr == 0)判斷語句的threshold被重新指派了，而原先的threshold值前文講到已經被指派給了newCap。
-
第二階段：根據newCap和newThr構造出新的newTab
用newTab來接收一個新的存放Node節點類型資料的數組，newCap為初始數組容量，然後将table指向newTable，實質就是指向new Node[newCap]，注意這裡的table就是hashmap類中的成員變量
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
接下來就進入到了第一個判斷oldTab != null，我們知道當oldTab中已經存在元素，才會進行接下來的一系列因為擴容導緻的索引位重排，元素重排等操作，是以先判斷oldTab是否不為空是非常自然的
if (oldTab != null) {
...
...
接着進入一個循環，從j=0到j=oldCap-1 ，周遊hash table ，每次周遊都會定義一個Node節點類型的指針e，
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
...
...
進入循環後首先判斷指針e指向的oldTab中下标為j的位置是否為空，不為空才需要進行接下來對該索引位元素的操作，對于索引位不為空的情況，把oldTab[j]重置為null，因為所有元素進行重排後最終會放入newTab中，oldTab中的元素被周遊并指派給指針e後就可以置空了。
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
...
...
随後判斷e指向的節點的下個節點是否為null，如果為null就說明還未形成連結清單，索引位上隻有一個元素，然後将指針e指向的元素直添加到新建立的newCap容量的newTab中該元素對應應該存放的位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
如果指針e指向的節點屬于樹節點類型，那就通過TreeNode<K,V>類的split方法重排節點
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
-
Head節點 Head 節點/重排後節點的索引位
如果以上情況都不符合，那就說明指針e指向的元素所在位置已經形成了連結清單但還未樹化，由于擴容後元素重排，重排的元素之間又會重新連結最終形成新的連結清單，是以我們需要先定義一些頭指針，尾指針，來作為中間件連接配接重排後的節點
Node<K,V> loHead 指向 重排後仍會處于原索引位的節點之間重新連結後的連結清單的頭節點 的指針
Node<K,V> loHead 指向 重排後仍會處于原索引位的節點之間重新連結後的連結清單的尾節點 的指針
Node<K,V> hiHead 指向 重排後應該處于新索引位的節點之間重新連結後的連結清單的頭節點 的指針
Node<K,V>hiTail 指向 重排後應該處于新索引位的節點之間重新連結後的連結清單的尾節點 的指針
Node<K,V> next 節點類型的next 指針，用于指向下一個節點
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
講到這裡可能有些小夥伴有些疑惑，重排後節點所處的索引位與原索引位有啥關系呢？
假設某一節點的哈希值為300 哈希表初始容量為16
則初始索引位 300%16=12
第一次擴容後索引位 300%32=12
第二次擴容後索引位 300%64=44=32+12
第三次擴容後索引位 300%128=44
。。。。。。
我們可以看到索引位隻有兩種情況，一種是擴容後索引位=擴容前索引位，另一種情況是擴容後索引位=擴容前的索引位+擴容前的hash table容量
-
do...while 循環
回到代碼繼續看，接下來是一個do...while循環，這一部分是resize方法中的關鍵，節點的重排和連結在這段代碼中完成，我慢慢講
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);
首先看循環的終止條件:
do {
next = e.next;
...
...
}while ((e = next) != null);
next指針指向 e指向節點的下一個節點，随後while判斷體内，首先讓e指針也指向下一個節點，随後判斷next指向的下一個幾點是否為null，是null就代表原始連結清單的周遊結束，退出循環，如果不為null就繼續周遊連結清單中剩下的節點，每次循環結束e指針立即指向後一個節點。
再來看循環體内的代碼：這裡有兩個大的分支，第一個分支能使(e.hash & oldCap) == 0成立的情況就是：原索引位上的連結清單中，重排後仍會處于原索引位 的節點。第二個分支成立的情況就是：重排後将處于（原索引位+原hash table容量） 的節點
-
重排後仍會處于原索引位 的節點
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
注意，這個分支中接下來所述的節點都是 重排後仍會處于原索引位 的節點，這些節點之間不一定相鄰
第一次進入該分支 loTail初始為null，将loHead頭指針指向連結清單中的第一個節點（周遊到連結清單的第一位），随後将loTail尾指針指向連結清單中的第一個節點，此時頭尾節點都指向連結清單中的第一個節點
随後經過若幹輪循環，若第二次進入該分支，我們看到loHead頭指針保持不動，尾指針指向的第一個節點對象中的next指針指向了此時周遊到的第二個節點，說白了就是第一個節點和第二個節點連結上了。随後尾指針重新指向了目前的尾節點，即第二個節點。
如此循環往複，直到連結清單中的所有元素周遊完，那麼所有的節點都會重新連結上形成一個新的連結清單，這個連結清單中的節點都是 重排後仍會處于原索引位的節點
-
重排後将處于(原索引位+原hash table容量) 的節點
注意，這個分支中接下來所述的節點都是 重排後将處于新索引位 的節點，這些節點之間不一定相鄰
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
這一部分的連結原理和第一個分支完全一樣，隻是形成的連結清單中的節點是 重排後将處于新的索引位的節點 而已
-
将兩條連結清單添加到newTab
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
兩條連結清單的尾節點最後都指向null
對于 重排後仍會處于原索引位的節點 組成的連結清單，将該連結清單的頭節點指針賦給newTab中對應的索引位
對于 重排後将處于新索引位的節點 組成的連結清單，将該連結清單的頭節點指針賦給newTab中對應的索引位
-
新哈希表newTab
那麼最終就産生了一個擴容後的新hash table數組 newTab
return newTab
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)