前言
最近在看并發(fā)編程藝術(shù)這本書费变，對看書的一些總結(jié)及個人理解。
為什么使用ConcurrentHashMap圣贸？
jdk5.0以后提供了多種并發(fā)類容器來替代同步類容器從而改善性能挚歧。同步類容器的狀態(tài)都是串行化的。他們雖然實現(xiàn)了線程安全吁峻，但是嚴重降低了并發(fā)性滑负，在多線程環(huán)境時，嚴重降低了應用程序的吞吐量用含。
線程不安全的HashMap
public class ConcurrentPutHashMap {
public static void main(String[] args) throws InterruptedException {
final HashMap<String, String> map = new HashMap<>(2);
Thread t = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 10000; i++) {
new Thread(new Runnable() {
@Override
public void run() {
map.put(UUID.randomUUID().toString(), "");
}
}, "ftf" + i).start();
}
}
}, "ftf");
t.start();
t.join();
}
}
效率低下的HashTable
HashTable容器使用synchronized來保證線程安全矮慕，但在線程競爭激烈的情況下HashTable的效率非常低下。因為當一個線程訪問HashTable的同步方法啄骇，其他線程也訪問HashTable的同步方法時痴鳄，會進入阻塞或輪詢狀態(tài)。如線程1使用put進行元素添加缸夹，線程2不但不能使用put方法添加元素痪寻，也不能使用get方法來獲取元素，所以競爭越激烈效率越低虽惭。
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
ConcurrentHashMap的鎖分段技術(shù)可有效提升并發(fā)訪問率
HashTable容器在競爭激烈的并發(fā)環(huán)境下表現(xiàn)出效率低下的原因是所有訪問HashTable的線程都必須競爭同一把鎖橡类，假如容器里有多把鎖，每一把鎖用于鎖容器其中一部分數(shù)據(jù)芽唇，那么當多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)時顾画，線程間就不會存在鎖競爭，從而可以有效提高并發(fā)訪問效率，這就是ConcurrentHashMap所使用的鎖分段技術(shù)研侣。首先將數(shù)據(jù)分成一段一段地存儲谱邪，然后給每一段數(shù)據(jù)配一把鎖，當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候庶诡，其他段的數(shù)據(jù)也能被其他線程訪問虾标。
ConcurrentHashMap的結(jié)構(gòu)
ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成。Segment是一種可重入鎖（ReentrantLock）灌砖，在ConcurrentHashMap里扮演鎖的角色璧函；HashEntry則用于存儲鍵值對數(shù)據(jù)。一個ConcurrentHashMap里包含一個Segment數(shù)組基显。Segment的結(jié)構(gòu)和HashMap類似蘸吓，是一種數(shù)組和鏈表結(jié)構(gòu)。一個Segment里包含一個HashEntry數(shù)組撩幽，每個HashEntry是一個鏈表結(jié)構(gòu)的元素库继，每個Segment守護著一個HashEntry數(shù)組里的元素，當對HashEntry數(shù)組的數(shù)據(jù)進行修改時窜醉，必須首先獲得與它對應的Segment鎖.
ConcurrentHashMap初始化
/**
* Creates a new, empty map with the default initial table size (16).
*/
public ConcurrentHashMap() {
}
默認的無參數(shù)構(gòu)造就是生成segments數(shù)組的長度為16的一個對象宪萄，即容器中的鎖也是16個。
既然ConcurrentHashMap使用分段鎖Segment來保護不同段的數(shù)據(jù)榨惰，那么在插入和獲取元素的時候拜英，必須先通過散列算法定位到Segment±糯撸可以看到ConcurrentHashMap會首先使用Wang/Jenkins hash的變種算法對元素的hashCode進行一次再散列居凶。
ConcurrentHashMap的操作
get操作
Segment的get操作實現(xiàn)非常簡單和高效。先經(jīng)過一次再散列藤抡，然后使用這個散列值通過散列運算定位到Segment侠碧，再通過散列算法定位到元素，代碼如下缠黍。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
get操作的高效之處在于整個get過程不需要加鎖弄兜，除非讀到的值是空才會加鎖重讀。我們知道HashTable容器的get方法是需要加鎖的瓷式，那么ConcurrentHashMap的get操作是如何做到不加鎖的呢替饿？原因是它的get方法里將要使用的共享變量都定義成volatile類型，如用于統(tǒng)計當前Segement大小的count字段和用于存儲值的HashEntry的value蒿往。定義成volatile的變量盛垦，能夠在線程之間保持可見性湿弦，能夠被多線程同時讀瓤漏，并且保證不會讀到過期的值，但是只能被單線程寫（有一種情況可以被多線程寫，就是寫入的值不依賴于原值）蔬充，在get操作里只需要讀不需要寫共享變量count和value蝶俱，所以可以不用加鎖。之所以不會讀到過期的值饥漫，是因為根據(jù)Java內(nèi)存模型的happen before原則榨呆，對volatile字段的寫入操作先于讀操作，即使兩個線程同時修改和獲取volatile變量庸队，get操作也能拿到最新的值积蜻，這是用volatile替換鎖的經(jīng)典應用場景。
put操作
由于put方法里需要對共享變量進行寫入操作彻消，所以為了線程安全竿拆，在操作共享變量時必須加鎖。put方法首先定位到Segment宾尚，然后在Segment里進行插入操作丙笋。插入操作需要經(jīng)歷兩個步驟，第一步判斷是否需要對Segment里的HashEntry數(shù)組進行擴容煌贴，第二步定位添加元素的位置御板，然后將其放在HashEntry數(shù)組里。
在插入元素前會先判斷Segment里的HashEntry數(shù)組是否超過容量（threshold）牛郑，如果超過閾值怠肋，則對數(shù)組進行擴容。
ConcurrentHashMap不會對整個容器進行擴容淹朋，而只對某個segment進行擴容灶似。
size操作
如果要統(tǒng)計整個ConcurrentHashMap里元素的大小，就必須統(tǒng)計所有Segment里元素的大小后求和瑞你。Segment里的全局變量count是一個volatile變量酪惭，那么在多線程場景下，是不是直接把所有Segment的count相加就可以得到整個ConcurrentHashMap大小了呢者甲？不是的春感，雖然相加時可以獲取每個Segment的count的最新值，但是可能累加前使用的count發(fā)生了變化虏缸，那么統(tǒng)計結(jié)果就不準了鲫懒。所以，最安全的做法是在統(tǒng)計size的時候把所有Segment的put刽辙、remove和clean方法全部鎖住窥岩，但是這種做法顯然非常低效。
因為在累加count操作過程中宰缤，之前累加過的count發(fā)生變化的幾率非常小颂翼，所以ConcurrentHashMap的做法是先嘗試2次通過不鎖住Segment的方式來統(tǒng)計各個Segment大小晃洒，如果統(tǒng)計的過程中，容器的count發(fā)生了變化朦乏，則再采用加鎖的方式來統(tǒng)計所有Segment的大小球及。
那么ConcurrentHashMap是如何判斷在統(tǒng)計的時候容器是否發(fā)生了變化呢？使用modCount變量呻疹，在put吃引、remove和clean方法里操作元素前都會將變而得知容器的大小是否發(fā)生變化。
總結(jié)
ConcurrentHashMap內(nèi)部使用段（Segment）來表示這些不同的部分刽锤，每個段其實就是一個小的HashTable镊尺，它們有自己的鎖。只要多個修改操作發(fā)生在不同的段上并思，他們就可以并發(fā)進行鹅心。把一個著呢個體分成了16個段（Segment）。
也就是最高支持16個線程的并發(fā)修改操作纺荧。這也是在多線程場景時減小鎖的粒度從而降低鎖競爭的一種方案旭愧，并且代碼中大多共享變量使用volatile關(guān)鍵字聲明（比如size方法中的count），目的是第一時間獲取修改的內(nèi)容宙暇，性能非常好输枯。
