ConcurrentHashMap的實現(xiàn)原理是什么

這篇文章將為大家詳細講解有關(guān)ConcurrentHashMap的實現(xiàn)原理是什么，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

1.HashTable與ConcurrentHashMap的對比

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

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

2.ConcurrentHashMap的內(nèi)部結(jié)構(gòu)

ConcurrentHashMap主要有三大結(jié)構(gòu)：整個Hash表，segment（段），HashEntry（節(jié)點）。每個segment就相當于一個HashTable。

（1）HashEntry類

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

由于這樣的特性，所以插入Hash鏈中的數(shù)據(jù)都是從頭開始插入的。例如將A,B,C插入空桶中，插入后的結(jié)構(gòu)為：

（2）segment類

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

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

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

ConcurrentHashMap 類

默認的情況下，每個ConcurrentHashMap 類會創(chuàng)建16個并發(fā)的segment，每個segment里面包含多個Hash表，每個Hash鏈都是有HashEntry節(jié)點組成的。

3.用分離鎖實現(xiàn)多個線程間的并發(fā)寫操作

（1）Put方法的實現(xiàn)

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

（2）Get方法的實現(xiàn)

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

（3）Remove方法的實現(xiàn)

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

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

執(zhí)行刪除之前的原鏈表：

執(zhí)行刪除之后的新鏈表

注意：新鏈表在clone的時候。順序發(fā)生反轉(zhuǎn)，A->B變?yōu)锽->A。

（4）containsKey方法的實現(xiàn)

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

4.總結(jié)

在使用鎖來協(xié)調(diào)多線程間并發(fā)訪問的模式下，減小對鎖的競爭可以有效提高并發(fā)性。有兩種方式可以減小對鎖的競爭：

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

• 減少持有鎖的時間。

ConcurrentHashMap 的高并發(fā)性主要來自于三個方面：

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

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

• 通過對同一個 Volatile 變量的寫 / 讀訪問，協(xié)調(diào)不同線程間讀 / 寫操作的內(nèi)存可見性。

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

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

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

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

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