Categories
程式開發

ConcurrentHashMap核心原理,徹底給整明白了


ConcurrentHashMap,它在技術面試中出現的頻率相當之高,所以我們必須對它深入理解和掌握。

談到ConcurrentHashMap,就一定會想到HashMap。 HashMap 在我們的代碼中使用頻率更高,不需要考慮線程安全的地方,我們一般都會使用HashMap。 HashMap 的實現非常經典,如果你讀過HashMap 的源代碼,那麼對ConcurrentHashMap 源代碼的理解會相對輕鬆,因為兩者採用的數據結構是類似的

這篇文章主要講解ConcurrentHashMap的核心原理,並註釋詳細源碼,文章篇幅較長,可收藏再看

基本結構

ConcurrentHashMap 是一個存儲key/value 對的容器,並且是線程安全的。我們先看ConcurrentHashMap 的存儲結構,如下圖:

ConcurrentHashMap核心原理,徹底給整明白了 1

雖然ConcurrentHashMap 的底層數據結構,和方法的實現細節和HashMap 大體一致,但兩者在類結構上卻沒有任何關聯,我們看下ConcurrentHashMap 的類圖:

ConcurrentHashMap核心原理,徹底給整明白了 2

看ConcurrentHashMap 源碼,我們會發現很多方法和代碼和HashMap 很相似,有的同學可能會問,為什麼不繼承HashMap 呢?

繼承的確是個好辦法,但ConcurrentHashMap 都是在方法中間進行一些加鎖操作,也就是說加鎖把方法切割了,繼承就很難解決這個問題。

ConcurrentHashMap和HashMap兩者的相同之處:

數組、鍊錶結構幾乎相同,所以底層對數據結構的操作思路是相同的(只是思路相同,底層實現不同);

都實現了Map 接口,繼承了AbstractMap 抽像類,所以大多數的方法也都是相同的,HashMap 有的方法,ConcurrentHashMap 幾乎都有,所以當我們需要從HashMap 切換到ConcurrentHashMap 時,無需關心兩者之間的兼容問題。

不同之處:

紅黑樹結構略有不同,HashMap 的紅黑樹中的節點叫做TreeNode,TreeNode 不僅僅有屬性,還維護著紅黑樹的結構,比如說查找,新增等等;ConcurrentHashMap 中紅黑樹被拆分成兩塊,TreeNode 僅僅維護的屬性和查找功能,新增了TreeBin,來維護紅黑樹結構,並負責根節點的加鎖和解鎖;

新增ForwardingNode (轉移)節點,擴容的時候會使用到,通過使用該節點,來保證擴容時的線程安全。

這些概念名詞文章後面都會依次介紹

基本構成

重要屬性

我們來看看ConcurrentHashMap 的幾個重要屬性

//这个Node数组就是ConcurrentHashMap用来存储数据的哈希表。
transient volatile Node[] table
//这是默认的初始化哈希表数组大小
private static final int DEFAULT_CAPACITY = 16;
//转化为红黑树的链表长度阈值
static final int TREEIFY_THRESHOLD = 8
//这个标识位用于识别扩容时正在转移数据
static final int MOVED = -1
//计算哈希值时用到的参数,用来去除符号位
static final int HASH_BITS = 0x7fffffff;
//数据转移时,新的哈希表数组
private transient volatile Node[] nextTable;
复制代码

重要組成元素

節點

“鍊錶中的元素為Node對象。他是鍊錶上的一個節點,內部存儲了key、value值,以及他的下一個節點的引用。這樣一系列的Node就串成一串,組成一個鍊錶。”

轉發節點

“當進行擴容時,要把鍊錶遷移到新的哈希表,在做這個操作時,會在把數組中的頭節點替換為ForwardingNode對象。ForwardingNode中不保存key和value,只保存了擴容後哈希表(nextTable)的引用。此時查找相應node時,需要去nextTable中查找。”

樹形樹

“當鍊錶轉為紅黑樹後,數組中保存的引用為TreeBin,TreeBin 內部不保存key/value,他保存了TreeNode的list以及紅黑樹root。”

樹節點

“紅黑樹的節點。”

下面依次講解各個核心方法,有詳細註釋

Put方法

public V put(K key, V value) {
return putVal(key, value, false);
}
复制代码

ConcurrentHashMap核心原理,徹底給整明白了 3

ConcurrentHashMap 在put 方法上的整體思路和HashMap 相同,但在線程安全方面寫了很多保障的代碼,我們先來看下大體思路:

1.如果數組為空,初始化,初始化完成之後,走2;

2.計算當前槽點有沒有值,沒有值的話,cas 創建,失敗繼續自旋(for 死循環),直到成功,槽點有值的話,走3;

3.如果槽點是轉移節點(正在擴容),就會一直自旋等待擴容完成之後再新增,不是轉移節點走4;

4.槽點有值的,先鎖定當前槽點,保證其餘線程不能操作,如果是鍊錶,新增值到鍊錶的尾部,如果是紅黑樹,使用紅黑樹新增的方法新增;

5.新增完成之後check 需不需要擴容,需要的話去擴容。

ConcurrentHashMap核心原理,徹底給整明白了 4

ConcurrentHashMap在put過程中,採用了哪些手段來保證線程安全呢?

數組初始化時的線程安全

數組初始化時,首先通過自旋來保證一定可以初始化成功,然後通過CAS 設置SIZECTL 變量的值,來保證同一時刻只能有一個線程對數組進行初始化,CAS 成功之後,還會再次判斷當前數組是否已經初始化完成,如果已經初始化完成,就不會再次初始化,通過自旋+ CAS + 雙重check 等手段保證了數組初始化時的線程安全

那麼接下來我們就來看看initTable 方法。

ConcurrentHashMap核心原理,徹底給整明白了 5

注意裡面有個關鍵的值sizeCtl,這個值有多個含義。

1、-1 代表有線程正在創建table;

2、-N 代表有N-1 個線程正在復制table;

3、在table 被初始化前,代表根據構造函數傳入的值計算出的應被初始化的大小;

4、在table 被初始化後,則被設置為table 大小的75%,代表table 的容量(數組容量)。

新增槽點值時的線程安全

此時為了保證線程安全,做了四處優化:

1.通過自旋死循環保證一定可以新增成功。

在新增之前,通過 for (Node[] tab = table;;)這樣的死循環來保證新增一定可以成功,一旦新增成功,就可以退出當前死循環,新增失敗的話,會重複新增的步驟,直到新增成功為止。

2.當前槽點為空時,通過CAS 新增。

Java 這裡的寫法非常嚴謹,沒有在判斷槽點為空的情況下直接賦值,因為在判斷槽點為空和賦值的瞬間,很有可能槽點已經被其他線程複製了,所以我們採用CAS 算法,能夠保證槽點為空的情況下賦值成功,如果恰好槽點已經被其他線程賦值,當前CAS 操作失敗,會再次執行for 自旋,再走槽點有值的put 流程,這裡就是自選+ CAS 的結合。

3.當前槽點有值,鎖住當前槽點。

put 時,如果當前槽點有值,就是key 的hash 衝突的情況,此時槽點上可能是鍊錶或紅黑樹,我們通過鎖住槽點,來保證同一時刻只會有一個線程能對槽點進行修改

V oldVal = null;
//锁定当前槽点,其余线程不能操作,保证了安全
synchronized (f) {
复制代码

4.紅黑樹旋轉時,鎖住紅黑樹的根節點,保證同一時刻,當前紅黑樹只能被一個線程旋轉

Hash算法

spread方法源碼分析

哈希算法的邏輯,決定ConcurrentHashMap 保存和讀取速度。

static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
复制代码

傳入的參數h為key 對象的hashCode,spreed 方法對hashCode 進行了加工。重新計算出hash。

hash 值是用來映射該key 值在哈希表中的位置。取出哈希表中該hash 值對應位置的代碼如下。

tabAt(tab, i = (n - 1) & hash);
复制代码

我們先看這一行代碼的邏輯,第一個參數為哈希表,第二個參數是哈希表中的數組下標。通過 (n – 1) & hash 計算下標。 n 為數組長度,我們以默認大小16 為例,那麼n-1 = 15,我們可以假設hash 值為100

n的值15转为二进制:
0000 0000 0000 0000 0000 0000 0000 1111
hash的值100转为二进制:
0000 0000 0000 0000 0000 0000 0110 0100。
计算结果:
0000 0000 0000 0000 0000 0000 0000 0100
对应的十进制值为 4
复制代码

15的二進制高位都為0,低位都是1。那麼經過&計算後,hash值100的高位全部被清零,低位則保持不變,並且一定是小於(n-1)的。也就是說經過如此計算,通過hash值得到的數組下標絕對不會越界。

這裡提出幾個問題:

1、數組大小可以為17,或者18 嗎?

2、如果為了保證不越界為什麼不直接用% 計算取餘數?

3、為什麼不直接用key 的hashCode,而是使用經spreed 方法加工後的hash 值?

數組大小必須為2 的n 次方

第一個問題的答案是數組大小必須為2 的n 次方,也就是16、32、64….不能為其他值。因為如果不是2 的n 次方,那麼經過計算的數組下標會增大碰撞的機率

如果hash值的二進制是10000(十進制16)、10010(十進制18)、10001(十進制17),和10100做&計算後,都是10000,也就是都被映射到數組16這個下標上。這三個值會以鍊錶的形式存儲在數組16下標的位置。這顯然不是我們想要的結果。

但如果數組長度n為2的n次方,2進制的數值為10,100,1000,10000……n-1後對應二進制為1,11,111,1111……這樣和hash值低位&後,會保留原來hash值的低位數值,那麼只要hash值的低位不一樣,就不會發生碰撞。

同時(n – 1) & hash等價於 hash%n。那麼為什麼不直接用hash%n呢?

這是因為按位的操作效率會更高。

為什麼不直接用key 的hashCode?

其實說到底還是為了減少碰撞的概率。我們先看看spreed 方法中的代碼做了什麼事情:

h ^ (h >>> 16)
复制代码

這個意思是把h 的二進制數值向右移動16 位。我們知道整形為32 位,那麼右移16 位後,就是把高16 位移到了低16 位。而高16 位清0了。

^為異或操作,二進制按位比較,如果相同則為0,不同則為1。這行代碼的意思就是把高低16位做異或。如果兩個hashCode值的低16位相同,但是高位不同,經過如此計算,低16位會變得不一樣了。

為什麼要把地位變得不一樣呢?

這是由於哈希表數組長度n會是偏小的數值,那麼進行(n – 1) & hash運算時,一直使用的是hash較低位的值。那麼即使hash值不同,但如果低位相當,也會發生碰撞。而進行h ^ (h >>> 16)加工後的hash值,讓hashCode高位的值也參與了哈希運算,因此減少了碰撞的概率。

(h ^ (h >>> 16)) & HASH_BITS
复制代码

為何高位移到低位和原來低位做異或操作後,還需要和HASH_BITS這個常量做& 計算呢? HASH_BITS 這個常量的值為0x7fffffff,轉化為二進制為0111 1111 1111 1111 1111 1111 1111 1111。這個操作後會把最高位轉為0,其實就是消除了符號位,得到的都是正數。這是因為負的hashCode 在ConcurrentHashMap 中有特殊的含義,因此我們需要得到一個正的hashCode。

擴容源碼分析

我們大致了解了ConcurrentHashMap 的存儲結構,那麼我們思考一個問題,當數組中保存的鍊錶越來越多,那麼再存儲進來的元素大概率會插入到現有的鍊錶中,而不是使用數組中剩下的空位。這樣會造成數組中保存的鍊錶越來越長,由此導致哈希表查找速度下降,從O(1) 慢慢趨近於鍊錶的時間複雜度O(n/2),這顯然違背了哈希表的初衷。

所以ConcurrentHashMap 會做一個操作,稱為擴容。也就是把數組長度變大,增加更多的空位出來,最終目的就是預防鍊錶過長,這樣查找的時間複雜度才會趨向於O(1)。

擴容的操作並不會在數組沒有空位時才進行,因為在空位快滿時,新保存元素更大的概率會命中已經使用的位置,那麼可能最後幾個桶位很難被使用,而鍊錶卻越來越長了。

另外ConcurrentHashMap 還會有鍊錶轉紅黑樹的操作,以提高查找的速度,紅黑樹時間複雜度為 O(logn),而鍊錶是 O(n/2),因此只在 O(logn)

接下來我們分析treeifyBin 方法代碼,這個代碼中會選擇是把此時保存數據所在的鍊錶轉為紅黑樹,還是對整個哈希表擴容

ConcurrentHashMap核心原理,徹底給整明白了 6

我們再重點看一下tryPresize,此方法中實現了對數組的擴容,傳入的參數size 是原來哈希表大小的一倍。我們假定原來哈希表大小為16,那麼傳入的size 值為32

ConcurrentHashMap核心原理,徹底給整明白了 7

ConcurrentHashMap 的擴容時機和HashMap 相同,都是在put 方法的最後一步檢查是否需要擴容,如果需要則進行擴容,但兩者擴容的過程完全不同,ConcurrentHashMap 擴容的方法叫做transfer,從put 方法的addCount 方法進去,就能找到transfer 方法,transfer 方法的主要思路是:

1.首先需要把老數組的值全部拷貝到擴容之後的新數組上,先從數組的隊尾開始拷貝;

2.拷貝數組的槽點時,先把原數組槽點鎖住,保證原數組槽點不能操作,成功拷貝到新數組時,把原數組槽點賦值為轉移節點;

3.這時如果有新數據正好需要put 到此槽點時,發現槽點為轉移節點,就會一直等待,所以在擴容完成之前,該槽點對應的數據是不會發生變化的;

4.從數組的尾部拷貝到頭部,每拷貝成功一次,就把原數組中的節點設置成轉移節點;

5.直到所有數組數據都拷貝到新數組時,直接把新數組整個賦值給數組容器,拷貝完成。

擴容方法主要是通過在原數組上設置轉移節點,put 時碰到轉移節點時會等待擴容成功之後才能put 的策略,來保證了整個擴容過程中肯定是線程安全的,因為數組的槽點一旦被設置成轉移節點,在沒有擴容完成之前,是無法進行操作的

ConcurrentHashMap核心原理,徹底給整明白了 8

Get方法

ConcurrentHashMap 讀的話,就比較簡單,先獲取數組的下標,然後通過判斷數組下標的key 是否和我們的key 相等,相等的話直接返回,如果下標的槽點是鍊錶或紅黑樹的話,分別調用相應的查找數據的方法,整體思路和HashMap 很像

ConcurrentHashMap核心原理,徹底給整明白了 9

構造函數源碼

public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity = (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
复制代码

這是一個有參數的構造方法。如果你對未來存儲的數據量有預估,我們可以指定哈希表的大小,避免頻繁的擴容操作。 tableSizeFor 這個方法確保了哈希表的大小永遠都是2 的n 次方。

注意這里傳入的參數不是initialCapacity,而是initialCapacity 的1.5 倍+ 1。這樣做是為了保證在默認75% 的負載因子下,能夠足夠容納initialCapacity 數量的元素。

ConcurrentHashMap (int initialCapacity) 構造函數總結下:

1、構造函數中並不會初始化哈希表;

2、構造函數中僅設置哈希表大小的變量sizeCtl;

3、initialCapacity 並不是哈希表大小;

4、哈希表大小為 initialCapacity*1.5+1 後,向上取最小的2 的n 次方。如果超過最大容量一半,那麼就是最大容量。

tableSizeFor 是如何實現向上取得最接近入參2 的n 次方的。下面我們來看tableSizeFor 源代碼:

private static final int tableSizeFor(int c) {
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
复制代码

依舊是二進制按位操作,這樣一頓操作後,得到的數值就是大於c 的最小2 的n 次。我們推演下過程,假設c 是9:

1、int n = 9 - 1
n=8
2、n |= n >>> 1
n=1000
n >>> 1=0100
两个值按位或后
n=1100
3、n |= n >>> 2
n=1100
n >>> 2=0011
n=1111
复制代码

到這裡可以看出規律來了。如果c 足夠大,使得n 很大,那麼運算到n |= n >>> 16 時,n 的32 位都為1。

總結一下這一段邏輯,其實就是把n 有數值的bit 位全部置為1。這樣就得到了一個肯定大於等於n 的值。我們再看最後一行代碼,最終返回的是n+1,那麼一個所有位都是1 的二進制數字,+1 後得到的就是一個2 的n 次方數值。

看完三件事❤️

如果你覺得這篇內容對你還蠻有幫助,我想邀請你幫我三個小忙:

點贊,轉發,有你們的『點贊和評論』,才是我創造的動力。關注公眾號『 java爛豬皮 』,不定期分享原創知識。同時可以期待後續文章ing🚀

ConcurrentHashMap核心原理,徹底給整明白了 10