Map 類和多線程
HashMap
HashMap 是我們最常用的 Map 類晦嵌，在單線程存入和獲取數(shù)據(jù)有非常高的性能蚊俺。下面簡(jiǎn)單介紹下它的基本結(jié)構(gòu)凉翻。
基本結(jié)構(gòu)
HashMap 內(nèi)部管理一個(gè)數(shù)組秦忿，數(shù)組中存儲(chǔ)鏈表節(jié)點(diǎn)默赂。將 (key, value) 插入map是沛鸵，對(duì) key 的 hashCode 調(diào)用 hash() 方法生成優(yōu)化后的散列值，然后調(diào)用 indexOfHash缆八，然后 (n - 1) & hash 計(jì)算出數(shù)組中的下標(biāo)曲掰，為 (key, value) 生成 node 存入數(shù)組中。
存入的 node 一般是鏈表結(jié)構(gòu)的奈辰，如果兩個(gè)條目（Entry）散列后的數(shù)組下標(biāo)相同栏妖，也就是發(fā)生哈希沖突，新條目的 node 會(huì)插入鏈表的最后奖恰。如果鏈表上 node 數(shù)量大于 8 個(gè)吊趾，為了增加查找性能，會(huì)將鏈表結(jié)構(gòu)改變成紅黑樹結(jié)構(gòu)瑟啃。
線程不安全
HashMap 的線程不安全已經(jīng)是面試的“街題”了论泛，為了簡(jiǎn)單說(shuō)明它的不安全性，可以從它的 putVal 函數(shù)入手蛹屿。該函數(shù)是 HashMap 的最核心函數(shù)屁奏，它用于將 （key, value） 存入 HashMap 中。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
相比于 Java8 之前的 addEntry 要復(fù)雜不少（忍不住吐槽下错负，Java8 的類坟瓢，包括 ConcurrentHashMap，功能越來(lái)越牛b犹撒，代碼越來(lái)越復(fù)雜難懂）折联。盡管代碼結(jié)構(gòu)復(fù)雜，但是當(dāng)分析線程安全的時(shí)候识颊，只要抓住 table / modCount / size 等臨界區(qū)變量的非同步訪問(wèn)就能足夠說(shuō)明問(wèn)題了崭庸。
HashTable
HashTable 早在 JDK1.0 的時(shí)候就引入了，它的結(jié)構(gòu)和 HashMap 類似谊囚，唯獨(dú)在 public 接口上使用了 synchronized 修飾符怕享。比如：
public synchronized int size()
public synchronized boolean isEmpty()
public synchronized V get(Object key)
public synchronized V put(K key, V value)
synchronized 的接口執(zhí)行之前會(huì)搶占 HashTable 對(duì)象的內(nèi)置鎖，達(dá)到多線程同步的作用镰踏。但是它的讀線程和寫線程都會(huì)去搶占這個(gè)內(nèi)置鎖函筋，比如 contains 這類需要遍歷元素并調(diào)用 equal的讀數(shù)據(jù)接口，可能會(huì)較長(zhǎng)時(shí)間阻塞其他線程奠伪，不論讀寫跌帐。因此在線程競(jìng)爭(zhēng)激烈的情況下HashTable的效率非常低下首懈。
SynchronizedMap
JDK 還提供了一種獲取線程安全 Map 的方式：Collections.synchronizedMap。這個(gè)接口會(huì)返回 SynchronizedMap 的對(duì)象谨敛，SynchronizedMap 其實(shí)是代理模式下究履，對(duì)具體 Map 的封裝，我們來(lái)看看它的結(jié)構(gòu)：
SynchronizedMap 就兩個(gè)成員變量脸狸，一個(gè)是真正實(shí)現(xiàn) Map 的線程不安全類最仑，一個(gè)是用來(lái)同步的 mutex，當(dāng)調(diào)用 Map 接口時(shí)炊甲，使用 mutex 的內(nèi)置鎖進(jìn)行保護(hù)泥彤，實(shí)際調(diào)用內(nèi)部 Map 對(duì)象的接口。類似于：
public int size() {
synchronized (mutex) {return m.size();}
}
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);}
}
可以說(shuō) SynchronizedMap 和 HashTable 實(shí)現(xiàn)多線程同步的機(jī)制一樣卿啡，所以盡管是線程安全的吟吝，但是在線程競(jìng)爭(zhēng)激烈的情況下效率非常堪憂颈娜。
還有一個(gè)問(wèn)題是既然 SynchronizedMap 和 HashTable 同步機(jī)制類似剑逃，那為什么還要有 SynchronizedMap呢？我想可能是由于 HashTable 內(nèi)部結(jié)構(gòu)和 HashMap 一致官辽。但是還有很多其他的 Map 類蛹磺，比如 LinkedHashMap，TreeMap 等它野崇，它們并沒(méi)有對(duì)應(yīng)的同步容器版本称开。而 SynchronizedMap 能夠成為它們的代理亩钟，既保證這些非 HashMap 的內(nèi)部結(jié)構(gòu)所帶來(lái)的優(yōu)勢(shì)乓梨，又能保證線程安全性。
modCount
在看 HashMap 和 HashTable 的時(shí)候有個(gè) modCount 引人注目清酥。這是代碼中的注釋：
The number of times this Hashtable has been structurally modified
Structural modifications are those that change the number of entries in
the Hashtable or otherwise modify its internal structure (e.g.,
rehash). This field is used to make iterators on Collection-views of
the Hashtable fail-fast. (See ConcurrentModificationException).
簡(jiǎn)單來(lái)說(shuō) modCount 代表了 HashTable 結(jié)構(gòu)變化的次數(shù)扶镀。結(jié)構(gòu)變化是指那些如些插入條目/修改條目/刪除條目等條目操作或者 rehash 這種改變內(nèi)部數(shù)據(jù)結(jié)構(gòu)的操作。
為什么要記錄這個(gè) modCount 呢焰轻？最主要的作用是保證使用迭代器操作時(shí)臭觉，HashTable的數(shù)據(jù)沒(méi)有改變，如果 modCount 變化辱志，則說(shuō)明此時(shí)數(shù)據(jù)不一致蝠筑，拋出 ConcurrentModificationException 異常。具體可以看看 HashTable.Enumerator 的代碼揩懒，簡(jiǎn)單的例子如下：
public T next() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
return nextElement();
}
ConcurrentHashMap
同步容器 VS 并發(fā)容器
HashTable 和SynchronizedMap 都屬于同步容器什乙，這些類實(shí)現(xiàn)線程安全的方式是：將它們的狀態(tài)封裝起來(lái)，對(duì)每個(gè)公有方法的同步使得每次只有一個(gè)線程能訪問(wèn)容器的狀態(tài)已球。以這種所有訪問(wèn)都串行化的方式臣镣，同步容器保證了線程安全性辅愿，但是這種方法的代價(jià)是嚴(yán)重降低并發(fā)行（想象下，所有只有讀線程的情況）忆某，當(dāng)多個(gè)線程競(jìng)爭(zhēng)容器的鎖時(shí)点待，吞吐量將嚴(yán)重降低。
Java 5.0 提供了并發(fā)容器來(lái)改進(jìn)同步容器的性能弃舒。并發(fā)容器可以使多個(gè)線程并發(fā)的訪問(wèn)容器癞埠。通過(guò)并發(fā)容器來(lái)替代同步容器，可以極大地提高伸縮性并降低風(fēng)險(xiǎn)棒坏。
ConcurrentHashMap 就是一種同步容器燕差，它采用了分段鎖（Lock Striping）機(jī)制增加并發(fā)行。在這種機(jī)制下：
- 任意數(shù)量的讀線程可以并發(fā)地訪問(wèn) Map
- 讀線程和寫線程可以并發(fā)的訪問(wèn) Map
- 一定數(shù)量的線程可以并發(fā)修改 Map
弱一致性
還記得上文中 HashTable 的 modCount 和 ConcurrentModificationException 嗎坝冕？在使用同步容器的迭代器時(shí)徒探，如果容器內(nèi)數(shù)據(jù)變化，迭代時(shí)就會(huì)“立即失敗”喂窟，拋出異常测暗。
和 HashTable 不同，ConcurrentHashMap 的迭代器可以容忍并發(fā)修改磨澡，也就是說(shuō)當(dāng)創(chuàng)建迭代器遍歷元素時(shí)碗啄，如果容器內(nèi)元素增加，減少稳摄，變更時(shí)稚字，迭代器也不會(huì)拋出異常，之后也能訪問(wèn)到修改后的數(shù)據(jù)厦酬，而且迭代器在構(gòu)造后可以將修改操作反映給容器胆描。
因?yàn)?ConcurrentHashMap 的 get 操作幾乎全是無(wú)鎖操作，get 和 put 可以同時(shí)進(jìn)行仗阅。用 CAS 操作和 volitale 關(guān)鍵字保證臨界數(shù)據(jù)的可見(jiàn)性昌讲，讀線程總能看到最近已完成的更新，這是產(chǎn)生弱一致性的最根本原因减噪。對(duì)此短绸，Java API 有以下描述：
Retrievals reflect the results of the most
recently completed update operations holding upon their onset. (More formally, an update operation for a given key bears a happens-beforerelation with any (non-null) retrieval for that key reporting the updated value.)
數(shù)據(jù)結(jié)構(gòu)
ConcurrentHashMap 內(nèi)部結(jié)構(gòu)實(shí)現(xiàn)在 Java 8 和 Java 8 之前有很大的變化。
JDK 1.7
在 JDK 1.7 中筹裕，ConcurrentHashMap 內(nèi)部維護(hù)了一個(gè) segment 數(shù)組醋闭，每一個(gè) Segment 相當(dāng)于類似于另外一個(gè) HashMap。每個(gè) Segment 維護(hù)一個(gè) HashEntry 數(shù)組朝卒，HashEntry 采用了鏈表結(jié)構(gòu)证逻，數(shù)據(jù)結(jié)構(gòu)可以看下面這圖：
所以訪問(wèn)一個(gè) Entry 需要進(jìn)行兩次哈希，第一次哈希找到 Segment扎运，第二次哈希是在 table 中找到鏈表瑟曲。分段鎖加在 Segment 上饮戳，也就是說(shuō)不同的 Segment 可以并發(fā)操作，兩條寫線程所要更改的數(shù)據(jù)第一次哈希到同一個(gè) Segment 時(shí)洞拨，線程才會(huì)同步扯罐。
JDK 1.8
在 JDK 1.8 中，對(duì) ConcurrentHashMap 進(jìn)行了兩個(gè)地方的優(yōu)化:
- 取消了 Segment 結(jié)構(gòu)烦衣，直接采用transient volatile HashEntry<K,V>[] table保存數(shù)據(jù)歹河，采用 table 數(shù)組元素作為鎖，從而實(shí)現(xiàn)了對(duì)每一行數(shù)據(jù)進(jìn)行加鎖花吟，進(jìn)一步減少并發(fā)沖突的概率秸歧。
- 將原先table數(shù)組＋單向鏈表的數(shù)據(jù)結(jié)構(gòu)，變更為table數(shù)組＋單向鏈表＋紅黑樹的結(jié)構(gòu)衅澈。雖然ConcurrentHashMap類默認(rèn)的加載因子為0.75键菱，但是在數(shù)據(jù)量過(guò)大或者運(yùn)氣不佳的情況下，還是會(huì)存在一些隊(duì)列長(zhǎng)度過(guò)長(zhǎng)的情況今布，對(duì)于個(gè)數(shù)超過(guò)8(默認(rèn)值)的鏈表经备，jdk1.8中采用了紅黑樹的結(jié)構(gòu)，那么查詢的時(shí)間復(fù)雜度可以降低到O(logN)部默，可以改進(jìn)性能侵蒙。
就數(shù)據(jù)結(jié)構(gòu)上來(lái)看，JDK 1.8 下的 ConcurrentHashMap 和 普通的 HashMap 更加相近傅蹂，但是前者通過(guò)對(duì) table 元素的加鎖纷闺，保證多個(gè) put 線程可以并發(fā)訪問(wèn)。
內(nèi)容來(lái)源
Java 并發(fā)編程實(shí)戰(zhàn)
http://ifeve.com/concurrenthashmap-weakly-consistent/
http://ifeve.com/concurrenthashmap/
http://blog.csdn.net/sbq63683210/article/details/51679790
