目錄
- 1.JDK1.7版本的HashMap擴容機制（重要）
- 2.JDK1.8版本的HashMap擴容機制（重要）
- 2.JDK1.7版本的ConcurrentHashMap擴容機制
- 4.JDK1.8版本的ConcurrentHashMap擴容機制(重要)
關于HashMap和ConcurrentHashMap的內容，可以參看Java基礎-HashMap集合，Java并發編程-ConcurrentHashMap，這兩篇文章，本章將深入探討兩者JDK1.7和JDK1.8兩個版本的擴容機制，
1.JDK1.7版本的HashMap擴容機制（重要）
HashMap的初始化容量是16，默認加載因子是0.75，擴容時擴容到原來的兩倍，這些特性對于其它版本的hashMap和concurrentHashMap同樣滿足，當hashmap中的元素個數超過陣列大小加載因子loadFactor時，就會進行陣列擴容，loadFactor的默認值為0.75，也就是說，默認情況下，陣列大小為16，那么當hashmap中元素個數超過160.75=12的時候，就把陣列的大小擴展為2*16=32，即擴大一倍，然后重新計算每個元素在陣列中的位置，而這是一個非常消耗性能的操作，所以如果我們已經預知hashmap中元素的個數，那么預設元素的個數能夠有效的提高hashmap的性能，
JDK1.7版本中，HashMap中鏈表的插入是采用頭插法，
擴容代碼如下：
void transfer(Entry[] newTable) {
Entry[] src = table; //src參考了舊的Entry陣列
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍歷舊的Entry陣列
Entry<K, V> e = src[j]; //取得舊Entry陣列的每個元素
if (e != null) {
src[j] = null;//釋放舊Entry陣列的物件參考（for回圈后，舊的Entry陣列不再參考任何物件）
do {
Entry<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！！重新計算每個元素在陣列中的位置
e.next = newTable[i]; //標記[1]
newTable[i] = e; //將元素放在陣列上
e = next; //訪問下一個Entry鏈上的元素
} while (e != null);
}
}
}
上面的這段代碼不并不難理解，對于擴容操作，底層實作都需要新生成一個陣列，然后拷貝舊陣列里面的每一個Node鏈表到新陣列里面，這個方法在單執行緒下執行是沒有任何問題的，但是在多執行緒下面卻有很大問題，頭插法，也就是說，新table中鏈表的順序和舊串列中是相反的，在HashMap執行緒不安全的情況下，這種頭插法可能會導致環狀節點，主要的問題在于基于頭插法的資料遷移，會有幾率造成鏈表倒置，從而引發鏈表閉鏈，導致程式死回圈，并吃滿CPU，
2.JDK1.8版本的HashMap擴容機制（重要）
在JDK8里面，HashMap的底層資料結構已經變為陣列+鏈表+紅黑樹的結構了，因為在hash沖突嚴重的情況下，鏈表的查詢效率是O(n），所以JDK8做了優化對于單個鏈表的個數大于8的鏈表，會直接轉為紅黑樹結構算是以空間換時間，這樣以來查詢的效率就變為O(logN)，圖示如下：
鏈表轉換為紅黑樹需要滿足兩個條件，第一個是鏈表長度達到8，第二個是散串列陣列長度已經達到64，否則的話，就算slot內部鏈表長度達到了8，它也不會鏈轉樹，它僅僅會發生一次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;
}
擴容演算法：
table陣列的長度是2的次方，因此每次都是按照上一次tableSize位移運算得到的，做一次左移1位運算(這里因為性能原因，CPU不支持直接乘以運算)，
創建新的陣列之后，老陣列的資料遷移程序如下：
遷移是一個桶位一個桶位的遷移處理，遷移的核心思想是尾插法，
第一種：slot存盤的是null
第二種：存盤的是個node，但node沒有鏈化
此時node的next是null,說明這個slot它沒有發生過hash沖突，直接遷移即可，根據新表的tableSize計算出它在新表中的位置,直接遷移過去即可，
第三種：node存盤的是一個鏈化的node
此時node的next不是null，說明這個slot它發生過沖突，需要把當前slot中保存的這個鏈表拆成兩個鏈表，分別是高位鏈和低位鏈，（所有的node#hash欄位轉化成二進制后，低位都是相同的，低位指的是tablesize-1轉化出來的二進制有效位，比如table陣列長度是16,16-1=15,15轉換成二進制數是1111，此時高位是第5位，此時有的第5位可能是0，也可能是1.這塊對應的node遷移到新表中，它們所存放的slot位置也是不一樣的），低位鏈遷移到新表中，和高位鏈是一樣的，高位鏈是1，存盤擴容，也就是到了新表之后，是老表的位置+老表size，
第四種：存盤了一個紅黑樹的TreeNode物件
TreeNode結構依然保留了next欄位，它內部其實還維護一個鏈表，鏈表方便split拆分紅黑樹的時候用的，它也是根據高位和低位拆分成高位鏈和低位鏈，其他程序基本和上述相同，只不過拆分出來的鏈表要看它的長度，如果小于6，直接把這個TreeNode轉化為普通的鏈表，否則的話，升級為紅黑樹
2.JDK1.7版本的ConcurrentHashMap擴容機制
HashMap是執行緒不安全的，我們來看下執行緒安全的ConcurrentHashMap，在JDK7的時候，這種安全策略采用的是分段鎖的機制，ConcurrentHashMap維護了一個Segment陣列，Segment這個類繼承了重入鎖ReentrantLock，并且該類里面維護了一個 HashEntry<K,V>[] table陣列，在寫操作put，remove，擴容的時候，會對Segment加鎖，所以僅僅影響這個Segment，不同的Segment還是可以并發的，所以解決了執行緒的安全問題，同時又采用了分段鎖也提升了并發的效率，
// 方法引數上的 node 是這次擴容后，需要添加到新的陣列中的資料，
private void rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
// 2 倍
int newCapacity = oldCapacity << 1;
threshold = (int)(newCapacity * loadFactor);
// 創建新陣列
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry[newCapacity];
// 新的掩碼，如從 16 擴容到 32，那么 sizeMask 為 31，對應二進制 ‘000...00011111’
int sizeMask = newCapacity - 1;
// 遍歷原陣列，老套路，將原陣列位置 i 處的鏈表拆分到 新陣列位置 i 和 i+oldCap 兩個位置
for (int i = 0; i < oldCapacity ; i++) {
// e 是鏈表的第一個元素
HashEntry<K,V> e = oldTable[i];
if (e != null) {
HashEntry<K,V> next = e.next;
// 計算應該放置在新陣列中的位置，
// 假設原陣列長度為 16，e 在 oldTable[3] 處，那么 idx 只可能是 3 或者是 3 + 16 = 19
int idx = e.hash & sizeMask;
if (next == null) // 該位置處只有一個元素，那比較好辦
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot
// e 是鏈表表頭
HashEntry<K,V> lastRun = e;
// idx 是當前鏈表的頭結點 e 的新位置
int lastIdx = idx;
// 下面這個 for 回圈會找到一個 lastRun 節點，這個節點之后的所有元素是將要放到一起的
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
// 將 lastRun 及其之后的所有節點組成的這個鏈表放到 lastIdx 這個位置
newTable[lastIdx] = lastRun;
// 下面的操作是處理 lastRun 之前的節點，
// 這些節點可能分配在另一個鏈表中，也可能分配到上面的那個鏈表中
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
// 將新來的 node 放到新陣列中剛剛的 兩個鏈表之一 的 頭部
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
注意這里面的代碼，外部已經加鎖，所以這里面是安全的，我們看下具體的實作方式：先對陣列的長度增加一倍，然后遍歷原來的舊的table陣列，把每一個陣列元素也就是Node鏈表遷移到新的陣列里面，最后遷移完畢之后，把新陣列的參考直接替換舊的，此外這里這有一個小的細節優化，在遷移鏈表時用了兩個for回圈，第一個for的目的是為了，判斷是否有遷移位置一樣的元素并且位置還是相鄰，根據HashMap的設計策略，首先table的大小必須是2的n次方，我們知道擴容后的每個鏈表的元素的位置，要么不變，要么是原table索引位置+原table的容量大小，舉個例子假如現在有三個元素（3,5,7）要放入map里面，table的的容量是2，簡單的假設元素位置=元素的值 % 2，得到如下結構：
[0]=null
[1]=3->5->7
現在將table的大小擴容成4，分布如下：
[0]=null
[1]=5->7
[2]=null
[3]=3
因為擴容必須是2的n次方，所以HashMap在put和get元素的時候直接取key的hashCode然后經過再次均衡后直接采用&位運算就能達到取模效果，這個不再細說，上面這個例子的目的是為了說明擴容后的資料分布策略，要么保留在原位置，要么會被均衡在舊的table位置，這里是1加上舊的table容量這是是2，所以是3，基于這個特點，第一個for回圈，作的優化如下，假設我們現在用0表示原位置，1表示遷移到index+oldCap的位置，來代表元素：
[0]=null
[1]=0->1->1->0->0->0->0
第一個for回圈的會記錄lastRun，比如要遷移[1]的資料，經過這個回圈之后，lastRun的位置會記錄第三個0的位置，因為后面的資料都是0，代表他們要遷移到新的陣列中同一個位置中，所以就可以把這個中間節點，直接插入到新的陣列位置而后面附帶的一串元素其實都不需要動，
接著第二個回圈里面在此從第一個0的位置開始遍歷到lastRun也就是第三個元素的位置就可以了，只回圈處理前面的資料即可，這個回圈里面根據位置0和1做不同的鏈表追加，后面的資料已經被優化的遷移走了，但最壞情況下可能后面一個也沒優化，比如下面的結構：
[0]=null
[1]=1->1->0->0->0->0->1->0
這種情況，第一個for回圈沒多大作用，需要通過第二個for回圈從頭開始遍歷到尾部，按0和1分發遷移，這里面使用的是還是頭插法的方式遷移，新遷移的資料是追加在鏈表的頭部，但這里是執行緒安全的所以不會出現回圈鏈表，導致死回圈問題，遷移完成之后直接將最新的元素加入，最后將新的table替換舊的table即可，
4.JDK1.8版本的ConcurrentHashMap擴容機制(重要)
并發map的存盤的資料結構如下：
private transient volatile int sizeCtl;
// 整個 ConcurrentHashMap 就是一個 Node[],鏈表結構
static class Node<K,V> implements Map.Entry<K,V> {}
// hash 表
transient volatile Node<K,V>[] table;
// 擴容時的 新 hash 表
private transient volatile Node<K,V>[] nextTable;
// 擴容時如果某個 bin 遷移完畢, 用 ForwardingNode 作為舊 table bin 的頭結點
//即當某個下標已經處理完了，就加個fnode，讓其它執行緒知道這個下標處理過了，就不會再這上面操作了
//如果其他執行緒來get,它就知道要到新的表中get
static final class ForwardingNode<K,V> extends Node<K,V> {}
// 用在 compute 以及 computeIfAbsent 時, 用來占位, 計算完成后替換為普通 Node
static final class ReservationNode<K,V> extends Node<K,V> {}
// 作為 treebin 的頭節點, 存盤 root 和 first
//它有一個長度閾值，如果長度超過8，鏈表就會變成紅黑樹，轉換之前，會先嘗試擴容，如果紅黑樹元素個數小于6，又會轉換為鏈表，
//TreeBin作為紅黑樹頭結點，TreeNode作為紅黑樹結點
static final class TreeBin<K,V> extends Node<K,V> {}
// 作為 treebin 的節點, 存盤 parent, left, right
static final class TreeNode<K,V> extends Node<K,V> {}
并發map的負載因子不可以修改的，負載因子是用final修飾的，值是固定的0.75
Node的hash欄位在一般情況下是值必須是>=0,它的負值有其它意義：散串列在擴容的時候，會觸發一個資料遷移的程序，把原表的資料遷移，遷移到擴容后的散串列的邏輯，老散串列遷移完了一個桶，需要放一個標記結點forwardingNode，這個Node的hash值它固定是-1.另外，這里紅黑樹由一個特殊的結點來處理是TreeBin結構，它本身繼承Node,它的哈希值比較特殊，它是固定值-2
最重要：sizeCtl:
sizeCtl==-1:表示當前的散串列正在做初始化，由于并發Map的散串列結構它是懶惰初始化的，即使用時創建，但它要保證在并發的條件下，散串列結構只能被創建一次，當多個執行緒都執行到initTable邏輯的時候，就會使用CAS的方式取修改這個sizeCtl的值，CAS采用的期望初始值是0，更新之后是-1，CAS修改成功的執行緒，去真正執行創建散串列的邏輯，CAS失敗的執行緒，會進行一個自旋檢查，檢查這個table是否被創建出來，每次進行自旋檢查之后，會讓執行緒短暫的釋放它所占用的CPU，讓當前執行緒重新競爭CPU資源，把CPU資源讓給其它更饑餓的執行緒去使用，
sizeCtl>0：sizeCtl表示下次觸發擴容的閾值，比如sizeCtl=12的時候，當插入新資料的時候，檢查容量，當發現>=12,就會觸發擴容操作，
sizeCtl<0且sizeCtl≠-1：它表示當前散串列正處于擴容狀態，高16位表示擴容表示戳，低16位表示參與擴容作業的執行緒數量+1，擴容表示戳非常的特殊，它必須保證每個執行緒計算出來的值是一致的，擴容標識戳的計算方式：它要保證每個執行緒在擴容，散串列從小到大，每次翻倍計算出來的值是一致的，擴容標識戳和老表table長度是強相關的，即不同的長度計算出來的戳是不一樣的，(注意：Java中表示負數最高位要設定為1)
并發map是如何保證寫資料安全？
并發map采用的方式是synchronized鎖桶的頭結點，來保證桶內的寫操作是執行緒安全的，
如果slot內是空的（沒有頭結點，沒有資料），這個時候，它是依賴CAS來實作執行緒安全的，執行緒會使用CAS的方式向slot里面寫頭結點資料，成功的話，它就回傳，失敗的話，說明有其它執行緒競爭到這個slot位置了，當前執行緒只能重新執行寫邏輯，但是CAS在并發量小的時候性能還不錯，但是并發量大的情況下，比較低，CAS首先是比較期望值，如果期望值和記憶體值是一致的，再執行替換操作，CAS會反映到內核層面，
并發map的擴容流程
1.觸發擴容的執行緒需要做一些額外的事情：觸發擴容條件的執行緒需要修改sizeCtl的值，根據擴容前的散串列長度，計算出擴容唯一標識戳，sizeCtl低16位存盤的值是參與擴容作業的執行緒數+1.當將低16位設定成2，表示有一個執行緒正在作業了，另外，這個執行緒需要創建一個新的table,大小是擴容前的兩倍，并且需要告訴新表的參考地址到map.nextTable欄位，因為后續的協助擴容的執行緒需要知道將資料遷移到哪里，
2.遷移作業時從高位桶開始，一直遷移到下標是0的桶，
3.我們會創建一個forwardingNode物件，它用來表示指定slot已經被遷移完畢的，forwardingNode里面有一個指向新表的欄位，它提供了一個查詢方法，當我們查詢到這個結點如果碰到了forwardingNode欄位，我們就會去新表中執行查詢，
4.假設散串列正在擴容中，如果又來了一個執行緒要向里面寫資料：如果這個寫操作訪問的桶還沒有被遷移，那么就要先拿到桶的鎖，然后執行正常的插入操作即可，而遷移桶位的時候也會加鎖，所以不存在并發的問題，加鎖是加的鏈表的頭結點，如果寫操作訪問的桶是頭結點，頭結點正好是forwardingNode結點，碰到fwd結點，說明當前正在擴容中，那么這個執行緒就會協助擴容執行緒做擴容作業，這樣能夠提高擴容的速率，當擴容作業完成后，當前執行緒就可以回傳到寫資料的邏輯里面了，最終資料會被寫到新擴容后的table中，
5.最后一個退出擴容任務的執行緒它會再重新檢查老表，看看有沒有遺漏的slot，判斷條件是slot是不是forwardingnode結點，如果是，就跳過，如果不是，當前執行緒就遷移到這個slot的資料，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257756.html
標籤：其他