Hashtable，Collections.SynchronizedMap和ConcurrentHashMap線程安全實(shí)現(xiàn)原理的區(qū)別以及性能測(cè)試
這三種 Map 都是 Java 中比較重要的集合類，雖然前兩個(gè)不太常用，但是因?yàn)榕c多線程相關(guān)，所以關(guān)于這幾種 Map 的對(duì)比已經(jīng)成為了 Java 面試時(shí)的高頻考點(diǎn)。首先要說(shuō)明的是，其中每一個(gè)單獨(dú)拎出來(lái)都足夠支撐一篇長(zhǎng)篇大論的技術(shù)文章，所以本文把重點(diǎn)放在了這三種集合類的線程安全實(shí)現(xiàn)原理的對(duì)比以及性能測(cè)試上，其他細(xì)節(jié)不做深入探討。
一、線程安全原理對(duì)比
1. Hashtable
首先必須吐槽一下這個(gè)類名，作為官方工具類竟然不符合駝峰命名規(guī)則，怪不得被棄用了，開(kāi)玩笑哈哈，主要原因還是性能低下，那 Hashtable 的性能為什么低下呢，這個(gè)嘛只需要看一下它的源碼就一目了然了，以下是 Hashtable 中幾個(gè)比較重要的方法：
public synchronized V put(K key, V value) {...}
public synchronized V get(Object key) {...}
public synchronized int size() {...}
public synchronized boolean remove(Object key, Object value) {...}
public synchronized boolean contains(Object value) {...}
... ...
查看源碼后可以看出，Hashtable 實(shí)現(xiàn)線程安全的原理相當(dāng)簡(jiǎn)單粗暴，直接在方法聲明上使用 synchronized 關(guān)鍵字。這樣一來(lái)，不管線程執(zhí)行哪個(gè)方法，即便只是讀取數(shù)據(jù)，都需要鎖住整個(gè) Hashtable 對(duì)象，可想而知其并發(fā)性能必然不會(huì)太好。
2. Collections.SynchronizedMap
SynchronizedMap 是 Collections 集合類的私有靜態(tài)內(nèi)部類，其定義和構(gòu)造方法如下：
private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable {
private static final long serialVersionUID = 1978198479659022715L;
// 用于接收傳入的Map對(duì)象，也是類方法操作的對(duì)象
private final Map<K,V> m;
// 鎖對(duì)象
final Object mutex;
// 以下是SynchronizedMap的兩個(gè)構(gòu)造方法
SynchronizedMap(Map<K,V> m) {
this.m = Objects.requireNonNull(m);
mutex = this;
}
SynchronizedMap(Map<K,V> m, Object mutex) {
this.m = m;
this.mutex = mutex;
}
}
SynchronizedMap 一共有三個(gè)成員變量，序列化ID拋開(kāi)不談，另外兩個(gè)分別是 Map 類型的實(shí)例變量 m，用于接收構(gòu)造方法中傳入的 Map 參數(shù)，以及 Object 類型的實(shí)例變量 mutex，作為鎖對(duì)象使用。
再來(lái)看構(gòu)造方法，SynchronizedMap 有兩個(gè)構(gòu)造方法。第一個(gè)構(gòu)造方法需要傳入一個(gè) Map 類型的參數(shù)，這個(gè)參數(shù)會(huì)被傳遞給成員變量 m，接下來(lái) SynchronizedMap 所有方法的操作都是針對(duì) m 的操作，需要注意的是這個(gè)參數(shù)不能為空，否則會(huì)由 Objects 類的 requireNonNull() 方法拋出空指針異常，然后當(dāng)前的 SynchronizedMap 對(duì)象 this 會(huì)被傳遞給 mutex 作為鎖對(duì)象；第二個(gè)構(gòu)造方法有兩個(gè)參數(shù)，第一個(gè) Map 類型的參數(shù)會(huì)被傳遞給成員變量 m，第二個(gè) Object 類型的參數(shù)會(huì)被傳遞給 mutex 作為鎖對(duì)象。
-
最后來(lái)看 SynchronizedMap 的主要方法 (只選取了一部分)：
public int size() { synchronized (mutex) {return m.size();} } public boolean isEmpty() { synchronized (mutex) {return m.isEmpty();} } public boolean containsKey(Object key) { synchronized (mutex) {return m.containsKey(key);} } public V get(Object key) { synchronized (mutex) {return m.get(key);} } public V put(K key, V value) { synchronized (mutex) {return m.put(key, value);} } public V remove(Object key) { synchronized (mutex) {return m.remove(key);} }
從源碼可以看出，SynchronizedMap 實(shí)現(xiàn)線程安全的方法也是比較簡(jiǎn)單的，所有方法都是先對(duì)鎖對(duì)象 mutex 上鎖，然后再直接調(diào)用 Map 類型成員變量 m 的相關(guān)方法。這樣一來(lái)，線程在執(zhí)行方法時(shí)，只有先獲得了 mutex 的鎖才能對(duì) m 進(jìn)行操作。因此，跟 Hashtable 一樣，在同一個(gè)時(shí)間點(diǎn)，只能有一個(gè)線程對(duì) SynchronizedMap 對(duì)象進(jìn)行操作，雖然保證了線程安全，卻導(dǎo)致了性能低下。這么看來(lái)，連 Hashtable 都被棄用了，那性能同樣低下的 SynchronizedMap 還有什么存在的必要呢？別忘了，后者的構(gòu)造方法需要傳入一個(gè) Map 類型的參數(shù)，也就是說(shuō)它可以將非線程安全的 Map 轉(zhuǎn)化為線程安全的 Map，而這正是其存在的意義，以下是 SynchronizedMap 的用法示例 (這里并沒(méi)有演示多線程操作)：
Map<String, Integer> map = new HashMap<>();
//非線程安全操作
map.put("one", 1);
Integer one = map.get("one");
Map<String, Integer> synchronizedMap = Collections.synchronizedMap(map);
//線程安全操作
one = synchronizedMap.get("one");
synchronizedMap.put("two", 2);
Integer two = synchronizedMap.get("two");
3. ConcurrentHashMap
接下來(lái)是數(shù)據(jù)結(jié)構(gòu)和線程安全原理都最復(fù)雜的 ConcurrentHashMap。首先必須要感嘆一下，這個(gè)類的結(jié)構(gòu)之復(fù)雜（包含53個(gè)內(nèi)部類），設(shè)計(jì)之精妙（不知道怎么形容，反正就是很精妙），真是令人嘆為觀止。說(shuō)實(shí)話，要想徹底理解 ConcurrentHashMap 的各個(gè)細(xì)節(jié)，還是需要相當(dāng)扎實(shí)的基礎(chǔ)并花費(fèi)大量精力的。本文對(duì)于 ConcurrentHashMap 線程安全的原理只是做了宏觀的介紹，想要深入理解的同學(xué)，可以去文末的傳送門(mén)。另外，本文著重介紹 JDK 1.8 版本的 ConcurrentHashMap，不過(guò)會(huì)對(duì) JDK 1.7 版本做個(gè)簡(jiǎn)單的回顧。
3.1 JDK 1.7 ConcurrentHashMap鎖實(shí)現(xiàn)原理回顧
如果你有一定基礎(chǔ)的話，應(yīng)該會(huì)知道分段鎖這個(gè)概念。沒(méi)錯(cuò)，這是JDK 1.7版本的 ConcurrentHashMap 實(shí)現(xiàn)線程安全的主要手段，具體一點(diǎn)就是 Segment + HashEntry + ReentrantLock。簡(jiǎn)單來(lái)說(shuō)，ConcurrentHashMap 是一個(gè) Segment 數(shù)組（默認(rèn)長(zhǎng)度為16），每個(gè) Segment 又包含了一個(gè) HashEntry 數(shù)組，所以可以看做一個(gè) HashMap， Segment 通過(guò)繼承 ReentrantLock 來(lái)進(jìn)行加鎖，所以每次需要加鎖的操作鎖住的是一個(gè) Segment，這樣只要保證每個(gè) Segment 是線程安全的，也就實(shí)現(xiàn)了全局的線程安全。
3.2 JDK 1.8 ConcurrentHashMap 線程安全原理詳解
JDK 1.8 版本摒棄了之前版本中較為臃腫的 Segment 分段鎖設(shè)計(jì)，取而代之的是 Node 數(shù)組 + CAS + synchronized + volatile 的新設(shè)計(jì)。這樣一來(lái)，ConcurrentHashMap 不僅數(shù)據(jù)結(jié)構(gòu)變得更簡(jiǎn)單了（與JDK 1.8 的HashMap類似），鎖的粒度也更小了，鎖的單位從 Segment 變成了 Node 數(shù)組中的桶（科普：桶就是指數(shù)組中某個(gè)下標(biāo)位置上的數(shù)據(jù)集合，這里可能是鏈表，也可能是紅黑樹(shù)）。說(shuō)到紅黑樹(shù)，必須提一下，在JDK 1.8 的 HashMap 和 ConcurrentHashMap 中，如果某個(gè)數(shù)組位置上的鏈表長(zhǎng)度過(guò)長(zhǎng)（大于等于8），就會(huì)轉(zhuǎn)化為紅黑樹(shù)以提高查詢效率，不過(guò)這不是本文的重點(diǎn)。以下是 ConcurrentHashMap 線程安全原理的詳細(xì)介紹：
3.2.1 get 操作過(guò)程
? 可以發(fā)現(xiàn)發(fā)現(xiàn)源碼中完全沒(méi)有加鎖的操作，后面會(huì)說(shuō)明原因
- 首先計(jì)算hash值，定位到該table索引位置，如果是首節(jié)點(diǎn)符合就返回
- 如果遇到擴(kuò)容的時(shí)候，會(huì)調(diào)用標(biāo)志正在擴(kuò)容節(jié)點(diǎn)ForwardingNode的find方法，查找該節(jié)點(diǎn)，匹配就返回
- 以上都不符合的話，就往下遍歷節(jié)點(diǎn)，匹配就返回，否則最后就返回null
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode()); //計(jì)算hash
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {//讀取頭節(jié)點(diǎn)的Node元素
if ((eh = e.hash) == h) { //如果該節(jié)點(diǎn)就是首節(jié)點(diǎn)就返回
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//hash值為負(fù)值表示正在擴(kuò)容，這個(gè)時(shí)候查的是ForwardingNode的find方法來(lái)定位到nextTable來(lái)
//eh代表頭節(jié)點(diǎn)的hash值，eh=-1，說(shuō)明該節(jié)點(diǎn)是一個(gè)ForwardingNode，正在遷移，此時(shí)調(diào)用ForwardingNode的find方法去nextTable里找。
//eh=-2，說(shuō)明該節(jié)點(diǎn)是一個(gè)TreeBin，此時(shí)調(diào)用TreeBin的find方法遍歷紅黑樹(shù)，由于紅黑樹(shù)有可能正在旋轉(zhuǎn)變色，所以find里會(huì)有讀寫(xiě)鎖。
//eh>=0，說(shuō)明該節(jié)點(diǎn)下掛的是一個(gè)鏈表，直接遍歷該鏈表即可。
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {//既不是首節(jié)點(diǎn)也不是ForwardingNode，那就往下遍歷
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
可能有同學(xué)會(huì)提出疑問(wèn)：為什么 get 操作不需要加鎖呢？這個(gè)嘛，也需要看一下源碼：
/**
* The array of bins. Lazily initialized upon first insertion.
* Size is always a power of two. Accessed directly by iterators.
* 這是ConcurrentHashMap的成員變量，用 volatile修飾的Node數(shù)組，保證了數(shù)組在擴(kuò)容時(shí)對(duì)其他線程的可見(jiàn)性
* 另外需要注意的是，這個(gè)數(shù)組是延遲初始化的，會(huì)在第一次put元素時(shí)進(jìn)行初始化，后面還會(huì)用到這個(gè)知識(shí)點(diǎn)
*/
transient volatile Node<K,V>[] table;
/**
* 這是ConcurrentHashMap靜態(tài)內(nèi)部類Node的定義，可見(jiàn)其成員變量val和next都使用volatile修飾，可保證
* 在多線程環(huán)境下線程A修改結(jié)點(diǎn)的val或者新增節(jié)點(diǎn)的時(shí)候是對(duì)線程B可見(jiàn)的
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
}
使用 volatile 關(guān)鍵字已經(jīng)足以保證線程在讀取數(shù)據(jù)時(shí)不會(huì)讀取到臟數(shù)據(jù)，所以沒(méi)有加鎖的必要。
3.2.2 put 操作過(guò)程
- 第一次 put 元素會(huì)初始化 Node 數(shù)組 (initTable)
- put 操作又分為 key (hash 碰撞) 存在時(shí)的插入和 key 不存在時(shí)的插入
- put 操作可能會(huì)引發(fā)數(shù)組擴(kuò)容 (tryPresize) 和鏈表轉(zhuǎn)紅黑樹(shù) (treeifyBin)
- 擴(kuò)容會(huì)使用到數(shù)據(jù)遷移方法 (transfer)
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// 得到 hash 值
int hash = spread(key.hashCode());
// 用于記錄相應(yīng)鏈表的長(zhǎng)度
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 如果數(shù)組"空"，進(jìn)行數(shù)組初始化
if (tab == null || (n = tab.length) == 0)
// 表的初始化，這里不展開(kāi)了，核心思想是使用sizeCtl的變量和CAS操作進(jìn)行控制，保證數(shù)組在擴(kuò)容時(shí)
// 不會(huì)創(chuàng)建出多余的表
tab = initTable();
// 找該 hash 值對(duì)應(yīng)的數(shù)組下標(biāo)，得到第一個(gè)節(jié)點(diǎn) f
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 如果數(shù)組該位置為空，用一次 CAS 操作將這個(gè)新值放入其中即可，這個(gè) put 操作差不多就結(jié)束了
// 如果 CAS 失敗，那就是有并發(fā)操作，進(jìn)到下一個(gè)循環(huán)就好了(循環(huán)的意思是 CAS 在執(zhí)行失敗后會(huì)進(jìn)行 // 重試)
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
// 幫助數(shù)據(jù)遷移，
tab = helpTransfer(tab, f);
else { // 到這里就是說(shuō)，f 是該位置的頭結(jié)點(diǎn)，而且不為空
V oldVal = null;
// 獲取數(shù)組該位置的頭結(jié)點(diǎn)鎖對(duì)象
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) { // 頭結(jié)點(diǎn)的 hash 值大于 0，說(shuō)明是鏈表
// 用于累加，記錄鏈表的長(zhǎng)度
binCount = 1;
// 遍歷鏈表
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 如果發(fā)現(xiàn)了"相等"的 key，判斷是否要進(jìn)行值覆蓋，然后也就可以 break 了
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
// 到了鏈表的最末端，將這個(gè)新值放到鏈表的最后面
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value, null);
break;
}
}
}
else if (f instanceof TreeBin) { // 紅黑樹(shù)
Node<K,V> p;
binCount = 2;
// 調(diào)用紅黑樹(shù)的插值方法插入新節(jié)點(diǎn)
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
// 判斷是否要將鏈表轉(zhuǎn)換為紅黑樹(shù)，臨界值和 HashMap 一樣，也是 8
if (binCount >= TREEIFY_THRESHOLD)
// 這個(gè)方法和 HashMap 中稍微有一點(diǎn)點(diǎn)不同，那就是它不是一定會(huì)進(jìn)行紅黑樹(shù)轉(zhuǎn)換，
// 如果當(dāng)前數(shù)組的長(zhǎng)度小于 64，那么會(huì)選擇進(jìn)行數(shù)組擴(kuò)容，而不是轉(zhuǎn)換為紅黑樹(shù)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
以上是 put 方法的源碼和分析，其中涉及到的其他方法，比如 initTable，helpTransfer，treeifyBin 和 tryPresize 等方法不再一一展開(kāi)，有興趣的同學(xué)可以去文末傳送門(mén)看詳細(xì)解析。
3.2.3 CAS 操作簡(jiǎn)要介紹
? CAS 操作是新版本 ConcurrentHashMap 線程安全實(shí)現(xiàn)原理的精華所在，如果說(shuō)其共享變量的讀取全靠 volatile 實(shí)現(xiàn)線程安全的話，那么存儲(chǔ)和修改過(guò)程除了使用少量的 synchronized 關(guān)鍵字外，主要是靠 CAS 操作實(shí)現(xiàn)線程安全的。不了解 CAS 操作的同學(xué)看這里 JAVA CAS原理深度分析
// CAS操作的提供者
private static final sun.misc.Unsafe U;
// 以下是put方法里用到CAS操作的代碼片段
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
// tabAt方法通過(guò)Unsafe.getObjectVolatile()的方式獲取數(shù)組對(duì)應(yīng)index上的元素，getObjectVolatile作用于對(duì)
// 應(yīng)的內(nèi)存偏移量上，是具備volatile內(nèi)存語(yǔ)義的。
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
// 如果獲取的是空，嘗試用CAS的方式在數(shù)組的指定index上創(chuàng)建一個(gè)新的Node。
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
在 ConcurrentHashMap 中，數(shù)組初始化、插入刪除元素、擴(kuò)容、數(shù)據(jù)遷移以及鏈表和紅黑樹(shù)的轉(zhuǎn)換等過(guò)程都會(huì)涉及到線程安全問(wèn)題，而相關(guān)的方法中實(shí)現(xiàn)線程安全的思想是一致的：對(duì)桶中的數(shù)據(jù)進(jìn)行添加或修改操作時(shí)會(huì)用到 synchronized 關(guān)鍵字，也就是獲得該位置上頭節(jié)點(diǎn)對(duì)象的鎖，保證線程安全，另外就是用到了大量的 CAS 操作。以上就是對(duì)這三種 Map 的線程安全原理的簡(jiǎn)要介紹。
二、性能測(cè)試
直接上代碼
public class MapPerformanceTest {
private static final int THREAD_POOL_SIZE = 5;
private static Map<String, Integer> hashtableObject = null;
private static Map<String, Integer> concurrentHashMapObject = null;
private static Map<String, Integer> synchronizedMap = null;
private static void performanceTest(final Map<String, Integer> map) throws InterruptedException {
System.out.println(map.getClass().getSimpleName() + "性能測(cè)試開(kāi)始了... ...");
long totalTime = 0;
// 進(jìn)行五次性能測(cè)試，每次開(kāi)啟五個(gè)線程，每個(gè)線程對(duì) map 進(jìn)行500000次查詢操作和500000次插入操作
for (int i = 0; i < 5; i++) {
long startTime = System.nanoTime();
ExecutorService service = Executors.newFixedThreadPool(THREAD_POOL_SIZE);
for (int j = 0; j < THREAD_POOL_SIZE; j++) {
service.execute(() -> {
for (int k = 0; k < 500000; k++) {
Integer randomNumber = (int)Math.ceil(Math.random() * 500000);
// 從map中查找數(shù)據(jù),查找結(jié)果并不會(huì)用到,這里不能用int接收返回值，因?yàn)镮nteger可能是
// null，賦值給int會(huì)引發(fā)空指針異常
Integer value = map.get(String.valueOf(randomNumber));
//向map中添加元素
map.put(String.valueOf(randomNumber), randomNumber);
}
});
}
//關(guān)閉線程池
service.shutdown();
service.awaitTermination(Long.MAX_VALUE, TimeUnit.DAYS);
long endTime = System.nanoTime();
// 單次執(zhí)行時(shí)間
long singleTime = (endTime - startTime) / 1000000;
System.out.println("第" + (i + 1) + "次測(cè)試耗時(shí)" + singleTime + "ms...");
totalTime += singleTime;
}
System.out.println("平均耗時(shí)" + totalTime / 5 + "ms...");
}
public static void main(String[] args) throws InterruptedException {
//Hashtable性能測(cè)試
hashtableObject = new Hashtable<>();
performanceTest(hashtableObject);
//SynchronizedMap性能測(cè)試
Map<String, Integer> map = new HashMap<>(500000);
synchronizedMap = Collections.synchronizedMap(map);
performanceTest(synchronizedMap);
//ConcurrentHashMap性能測(cè)試
concurrentHashMapObject = new ConcurrentHashMap<>(5000000);
performanceTest(concurrentHashMapObject);
}
}
在這里說(shuō)明一點(diǎn)，這段代碼在不同環(huán)境下運(yùn)行的結(jié)果會(huì)存在差別，但是結(jié)果的數(shù)量級(jí)對(duì)比應(yīng)該是一致的，以下是我機(jī)子上的運(yùn)行結(jié)果：
從運(yùn)行結(jié)果可以看出，在250萬(wàn)這個(gè)數(shù)量級(jí)別的數(shù)據(jù)存取上，Hashtable 和 SynchronizedMap 的性能表現(xiàn)幾乎一致，畢竟它們的鎖實(shí)現(xiàn)原理大同小異，而 ConcurrentHashMap 表現(xiàn)出了比較大的性能優(yōu)勢(shì)，耗時(shí)只有前兩者的三分之一多一點(diǎn)兒。嗯... 以后面試再被問(wèn)到相關(guān)問(wèn)題，可以直接把數(shù)據(jù)甩給面試官... ...
三、結(jié)語(yǔ)
好了，以上就是本篇文章的全部?jī)?nèi)容了，完結(jié)撒花，簡(jiǎn)書(shū)上不知道怎么調(diào)圖片大小哈哈。第一次寫(xiě)博客，竟然嘮叨了這么多，不足之處還請(qǐng)各位看官老爺不吝賜教。另外想要進(jìn)一步深入了解 ConcurrentHashMap 原理的朋友可以看一下下面兩篇文章，是我看過(guò)的講的比較詳細(xì)的。
