concurrenthashmap 原理(ConcurrentHashMap的實現原理是什么)

1.HashTable與ConcurrentHashMap的對比

HashTable本身是線程安全的,寫過Java程序的都知道通過加Synchronized關鍵字實現線程安全,這樣對整張表加鎖實現同步的一個缺陷就在于使程序的效率變得很低。這就是為什么Java中會在1.5后引入ConcurrentHashMap的原因。

從圖中可以看出,HashTable的鎖加在整個Hash表上,而ConcurrentHashMap將鎖加在segment上(每個段上),這樣我們在對segment1操作的時候,同時也可以對segment2中的數據操作,這樣效率就會高很多。

2.ConcurrentHashMap的內部結構

ConcurrentHashMap主要有三大結構:整個Hash表,segment(段),HashEntry(節點)。每個segment就相當于一個HashTable。

(1)HashEntry類

每個HashEntry代表Hash表中的一個節點,在其定義的結構中可以看到,除了value值沒有定義final,其余的都定義為final類型,我們知道Java中關鍵詞final修飾的域成為最終域。用關鍵詞final修飾的變量一旦賦值,就不能改變,也稱為修飾的標識為常量。這就意味著我們刪除或者增加一個節點的時候,就必須從頭開始重新建立Hash鏈,因為next引用值需要改變。

由于這樣的特性,所以插入Hash鏈中的數據都是從頭開始插入的。例如將A,B,C插入空桶中,插入后的結構為:

(2)segment類

Segment 類繼承于 ReentrantLock 類,從而使得 Segment 對象能充當鎖的角色。每個 Segment 對象用來守護其(成員對象 table 中)包含的若干個桶。

table 是一個由 HashEntry 對象組成的數組。table 數組的每一個數組成員就是散列映射表的一個桶。

count 變量是一個計數器,它表示每個 Segment 對象管理的 table 數組(若干個 HashEntry 組成的鏈表)包含的 HashEntry 對象的個數。每一個 Segment 對象都有一個 count 對象來表示本 Segment 中包含的 HashEntry 對象的總數。注意,之所以在每個 Segment 對象中包含一個計數器,而不是在 ConcurrentHashMap 中使用全局的計數器,是為了避免出現“熱點域”而影響 ConcurrentHashMap 的并發性。

ConcurrentHashMap 類

默認的情況下,每個ConcurrentHashMap 類會創建16個并發的segment,每個segment里面包含多個Hash表,每個Hash鏈都是有HashEntry節點組成的。

3.用分離鎖實現多個線程間的并發寫操作

(1)Put方法的實現

整個代碼通過注釋很好理解了,稍微要注意的是這里的加鎖是針對具體的segment,而不是對整個ConcurrentHashMap。Put方法從源碼上可以看出是從鏈表的頭部插入新的數據的。

(2)Get方法的實現

ConcurrentHashMap中的讀方法不需要加鎖,所有的修改操作在進行結構修改時都會在最后一步寫count 變量,通過這種機制保證get操作能夠得到幾乎最新的結構更新。

(3)Remove方法的實現

整個操作是在持有段鎖的情況下執行的,空白行之前的行主要是定位到要刪除的節點e。接下來,如果不存在這個節點就直接返回null,否則就要將e前面的結點復制一遍,尾結點指向e的下一個結點。e后面的結點不需要復制,它們可以重用。

中間那個for循環是做什么用的呢?從代碼來看,就是將定位之后的所有entry克隆并拼回前面去,但有必要嗎?每次刪除一個元素就要將那之前的元素克隆一遍?這點其實是由entry的不變性來決定的,仔細觀察entry定義,發現除了value,其他所有屬性都是用final來修飾的,這意味著在第一次設置了next域之后便不能再改變它,取而代之的是將它之前的節點全都克隆一次。至于entry為什么要設置為不變性,這跟不變性的訪問不需要同步從而節省時間有關。

執行刪除之前的原鏈表:

執行刪除之后的新鏈表

注意:新鏈表在clone的時候。順序發生反轉,A->B變為B->A。

(4)containsKey方法的實現

containsKey方法操作相對簡單,因為它不需要讀取值。

4.總結

在使用鎖來協調多線程間并發訪問的模式下,減小對鎖的競爭可以有效提高并發性。有兩種方式可以減小對鎖的競爭:

• 減小請求同一個鎖的頻率。

• 減少持有鎖的時間。

ConcurrentHashMap 的高并發性主要來自于三個方面:

• 用分離鎖實現多個線程間的更深層次的共享訪問。

• 用 HashEntery 對象的不變性來降低執行讀操作的線程在遍歷鏈表期間對加鎖的需求。

• 通過對同一個 Volatile 變量的寫 / 讀訪問,協調不同線程間讀 / 寫操作的內存可見性。

使用分離鎖,減小了請求同一個鎖的頻率。

concurrentHashMap在jdk1.8中主要做了2方面的改進

改進一:取消segments字段,直接采用transient volatile HashEntry<K,V>[] table保存數據,采用table數組元素作為鎖,從而實現了對每一行數據進行加鎖,進一步減少并發沖突的概率。

改進二:將原先table數組+單向鏈表的數據結構,變更為table數組+單向鏈表+紅黑樹的結構。對于hash表來說,最核心的能力在于將key hash之后能均勻的分布在數組中。如果hash之后散列的很均勻,那么table數組中的每個隊列長度主要為0或者1。但實際情況并非總是如此理想,雖然ConcurrentHashMap類默認的加載因子為0.75,但是在數據量過大或者運氣不佳的情況下,還是會存在一些隊列長度過長的情況,如果還是采用單向列表方式,那么查詢某個節點的時間復雜度為O(n);因此,對于個數超過8(默認值)的列表,jdk1.8中采用了紅黑樹的結構,那么查詢的時間復雜度可以降低到O(logN),可以改進性能。

關于ConcurrentHashMap的實現原理是什么就分享到這里了,希望以上內容可以對大家有一定的幫助,可以學到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。