寫在前面

本文所有關於 ConcurrentHashMap 的源碼都是基於 JDK 1.6 的，不同 JDK 版本之間會有些許差異，但不影響我們對 ConcurrentHashMap 的數據結構、原理等整體的把握和了解

ConcurrentHashMap是J.U.C(java.util.concurrent包)的重要成員，它是HashMap的一個線程安全的、支持高效並發的版本

ConcurrentHashMap 概述

HashMap 是 Java Collection Framework 的重要成員，也是Map族(如下圖所示)中我們最為常用的一種。不過遺憾的是，HashMap不是線程安全的

HashMap的這一缺點往往會造成諸多不便，雖然在並發場景下HashTable和由同步包裝器包裝的HashMap(Collections.synchronizedMap(Map<K,V> m) )可以代替HashMap，但是它們都是通過使用一個全局的鎖來同步不同線程間的並發訪問，因此會帶來不可忽視的性能問題。慶幸的是，JDK為我們解決了這個問題，它為HashMap提供了一個線程安全的高效版本 —— ConcurrentHashMap

在ConcurrentHashMap中，無論是讀操作還是寫操作都能保證很高的性能：在進行讀操作時(幾乎)不需要加鎖，而在寫操作時通過鎖分段技術只對所操作的段加鎖而不影響客戶端對其它段的訪問。特別地，在理想狀態下，ConcurrentHashMap 可以支持 16 個線程執行並發寫操作（如果並發級別設為16），及任意數量線程的讀操作

ConcurrentHashMap的高效並發機制是通過以下三方面來保證的

  • 通過鎖分段技術保證並發環境下的寫操作；
  • 通過 HashEntry的不變性、Volatile變數的內存可見性和加鎖重讀機制保證高效、安全的讀操作；
  • 通過不加鎖和加鎖兩種方案控制跨段操作的的安全性。

ConcurrentHashMap 在 JDK 中的定義

ConcurrentHashMap類中包含兩個靜態內部類

  • HashEntry： 用來封裝具體的K/V對，是個典型的四元組
  • Segment：用來充當鎖的角色，每個 Segment 對象守護整個ConcurrentHashMap的若干個桶 (可以把Segment看作是一個小型的哈希表)，其中每個桶是由若干個 HashEntry 對象鏈接起來的鏈表

ConcurrentHashMap 在默認並發級別下會創建16個Segment對象的數組，如果鍵能均勻散列，每個 Segment 大約守護整個散列表中桶總數的 1/16。

類結構定義

ConcurrentHashMap 繼承了AbstractMap並實現了ConcurrentMap介面，其在JDK中的定義為：

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
implements ConcurrentMap<K, V>, Serializable {
...
}

成員變數定義

與HashMap相比，ConcurrentHashMap 增加了兩個屬性用於定位段，分別是 segmentMask 和 segmentShift。此外，不同於HashMap的是，ConcurrentHashMap底層結構是一個Segment數組，而不是Object數組

final int segmentMask; // 用於定位段，大小等於segments數組的大小減 1，是不可變的

final int segmentShift; // 用於定位段，大小等於32(hash值的位數)減去對segments的大小取以2為底的對數值，是不可變的

final Segment<K,V>[] segments; // ConcurrentHashMap的底層結構是一個Segment數組

段的定義：Segment

Segment 類繼承於 ReentrantLock 類，從而使得 Segment 對象能充當鎖的角色

在Segment類中，count 變數是一個計數器，它表示每個 Segment 對象管理的 table 數組包含的 HashEntry 對象的個數，也就是 Segment 中包含的 HashEntry 對象的總數。特別需要注意的是，之所以在每個 Segment 對象中包含一個計數器，而不是在 ConcurrentHashMap 中使用全局的計數器，是對 ConcurrentHashMap 並發性的考慮：因為這樣當需要更新計數器時，不用鎖定整個ConcurrentHashMap

基本元素：HashEntry

與HashMap中的Entry類似，HashEntry也包括同樣的四個域，分別是key、hash、value和next。不同的是，在HashEntry類中，key，hash和next域都被聲明為final的，value域被volatile所修飾，因此HashEntry對象幾乎是不可變的，這是ConcurrentHashmap讀操作並不需要加鎖的一個重要原因

由於value域被volatile修飾，所以其可以確保被讀線程讀到最新的值，這是ConcurrentHashmap讀操作並不需要加鎖的另一個重要原因。

ConcurrentHashMap 的構造函數

1，ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

該構造函數意在構造一個具有指定容量、指定負載因子和指定段數目/並發級別(若不是2的冪次方，則會調整為2的冪次方)的空ConcurrentHashMap

2，ConcurrentHashMap(int initialCapacity, float loadFactor)

該構造函數意在構造一個具有指定容量、指定負載因子和默認並發級別(16)的空ConcurrentHashMap

3，ConcurrentHashMap(int initialCapacity)

該構造函數意在構造一個具有指定容量、默認負載因子(0.75)和默認並發級別(16)的空ConcurrentHashMap

4，ConcurrentHashMap()

該構造函數意在構造一個具有默認初始容量(16)、默認負載因子(0.75)和默認並發級別(16)的空ConcurrentHashMap

5，ConcurrentHashMap(Map<? extends K, ? extends V> m)

該構造函數意在構造一個與指定 Map 具有相同映射的 ConcurrentHashMap，其初始容量不小於 16 (具體依賴於指定Map的大小)，負載因子是 0.75，並發級別是 16， 是 Java Collection Framework 規範推薦提供的

小結

在這裡，我們提到了三個非常重要的參數：初始容量、負載因子 和 並發級別，這三個參數是影響ConcurrentHashMap性能的重要參數

ConcurrentHashMap 的數據結構

通過使用段(Segment)將ConcurrentHashMap劃分為不同的部分，ConcurrentHashMap就可以使用不同的鎖來控制對哈希表的不同部分的修改，從而允許多個修改操作並發進行, 這正是ConcurrentHashMap鎖分段技術的核心內涵

ConcurrentHashMap 的並發存取

在ConcurrentHashMap中，線程對映射表做讀操作時，一般情況下不需要加鎖就可以完成，對容器做結構性修改的操作(比如，put操作、remove操作等)才需要加鎖。

用分段鎖機制實現多個線程間的並發寫操作: put(key, vlaue)

在ConcurrentHashMap中，典型結構性修改操作包括put、remove和clear，下面我們首先以put操作為例說明對ConcurrentHashMap做結構性修改的過程

public V put(K key, V value) {
if (value == null)
throw new NullPointerException();
int hash = hash(key.hashCode());
return segmentFor(hash).put(key, hash, value, false);
}

ConcurrentHashMap不同於HashMap，它既不允許key值為null，也不允許value值為null

定位段的segmentFor()方法源碼如下

final Segment<K,V> segmentFor(int hash) {
return segments[(hash >>> segmentShift) & segmentMask];
}

根據key的hash值的高n位就可以確定元素到底在哪一個Segment中

段的put()方法的源碼如下所示

V put( K key, int hash, V value, boolean onlyIfAbsent )
{
lock(); /* 上鎖 */
try {
int c = count;
if ( c++ > threshold ) /* ensure capacity */
rehash();
HashEntry<K, V>[] tab = table; /* table是Volatile的 */
int index = hash & (tab.length - 1); /* 定位到段中特定的桶 */
HashEntry<K, V> first = tab[index]; /* first指向桶中鏈表的表頭 */
HashEntry<K, V> e = first;
/* 檢查該桶中是否存在相同key的結點 */
while ( e != null && (e.hash != hash || !key.equals( e.key ) ) )
e = e.next;
V oldValue;
if ( e != null ) /* 該桶中存在相同key的結點 */
{
oldValue = e.value;
if ( !onlyIfAbsent )
e.value = value; /* 更新value值 */
}else { /* 該桶中不存在相同key的結點 */
oldValue = null;
++modCount; /* 結構性修改，modCount加1 */
tab[index] = new HashEntry<K, V>( key, hash, first, value ); /* 創建HashEntry並將其鏈到表頭 */
count = c; /* write-volatile，count值的更新一定要放在最後一步(volatile變數) */
}
return(oldValue); /* 返回舊值(該桶中不存在相同key的結點，則返回null) */
} finally {
unlock(); /* 在finally子句中解鎖 */
}
}

相比較於 HashTable 和由同步包裝器包裝的HashMap每次只能有一個線程執行讀或寫操作，ConcurrentHashMap 在並發訪問性能上有了質的提高。在理想狀態下，ConcurrentHashMap 可以支持 16 個線程執行並發寫操作（如果並發級別設置為 16），及任意數量線程的讀操作

最後

如果你是一名想要或準備要往架構師方向發展的java程序員、如果你想要關於java架構學習的視頻資料和BAT的面試題及答案的。請私信我【資料】，我會將（分散式架構、高可擴展、高性能、高並發、性能優化、Spring boot、Redis、ActiveMQ、Nginx、Mycat、Netty、Jvm大型分散式項目實戰學習架構師視頻）免費分享哦！

獲取資料的方式：轉發+私信【資料】領取！

推薦閱讀：

相关文章