摘要：一出現背景線程不安全的因為多線程環(huán)境下，使用進行操作會引起死循環(huán)，導致利用率接近，所以在并發(fā)情況下不能使用。是由數組結構和數組結構組成。用來表示需要進行的界限值。也是，這使得能夠讀取到最新的值而不需要同步。
一、出現背景
1、線程不安全的HashMap
因為多線程環(huán)境下，使用Hashmap進行put操作會引起死循環(huán)，導致CPU利用率接近100%，所以在并發(fā)情況下不能使用HashMap。
2、效率低下的HashTable容器
HashTable容器使用synchronized來保證線程安全，但在線程競爭激烈的情況下HashTable的效率非常低下。因為當一個線程訪問HashTable的同步方法時，其他線程訪問HashTable的同步方法時，可能會進入阻塞或輪詢狀態(tài)。如線程1使用put進行添加元素，線程2不但不能使用put方法添加元素，并且也不能使用get方法來獲取元素，所以競爭越激烈效率越低。也就是說對于Hashtable而言，synchronized是針對整張Hash表的，即每次鎖住整張表讓線程獨占。相當于所有線程進行讀寫時都去競爭一把鎖，導致效率非常低下。
3、ConcurrentHashMap的鎖分段技術
HashTable容器在競爭激烈的并發(fā)環(huán)境下表現出效率低下的原因，是因為所有訪問HashTable的線程都必須競爭同一把鎖。那假如容器里有多把鎖，每一把鎖用于鎖容器其中一部分數據，那么當多線程訪問容器里不同數據段的數據時，線程間就不會存在鎖競爭，從而可以有效的提高并發(fā)訪問效率，這就是ConcurrentHashMap所使用的鎖分段技術，首先將數據分成一段一段的存儲，然后給每一段數據配一把鎖，當一個線程占用鎖訪問其中一個段數據的時候，其他段的數據也能被其他線程訪問。 另外，ConcurrentHashMap可以做到讀取數據不加鎖，并且其內部的結構可以讓其在進行寫操作的時候能夠將鎖的粒度保持地盡量地小，不用對整個ConcurrentHashMap加鎖。
ConcurrentHashMap是由Segment數組結構和HashEntry數組結構組成。Segment是一種可重入鎖ReentrantLock，在ConcurrentHashMap里扮演鎖的角色，HashEntry則用于存儲鍵值對數據。一個ConcurrentHashMap里包含一個Segment數組，Segment的結構和HashMap類似，是一種數組和鏈表結構， 一個Segment里包含一個HashEntry數組，每個HashEntry是一個鏈表結構的元素， 每個Segment守護著一個HashEntry數組里的元素，當對HashEntry數組的數據進行修改時，必須首先獲得它對應的Segment鎖。
二、ConcurrentHashMap的內部結構
ConcurrentHashMap為了提高本身的并發(fā)能力，在內部采用了一個叫做Segment的結構，一個Segment其實就是一個類Hash Table的結構，Segment內部維護了一個鏈表數組，我們用下面這一幅圖來看下ConcurrentHashMap的內部結構：
從上面的結構我們可以了解到，ConcurrentHashMap定位一個元素的過程需要進行兩次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的鏈表的頭部，因此，這一種結構的帶來的副作用是Hash的過程要比普通的HashMap要長，但是帶來的好處是寫操作的時候可以只對元素所在的Segment進行加鎖即可，不會影響到其他的Segment，這樣，在最理想的情況下，ConcurrentHashMap可以最高同時支持Segment數量大小的寫操作（剛好這些寫操作都非常平均地分布在所有的Segment上），所以，通過這一種結構，ConcurrentHashMap的并發(fā)能力可以大大的提高。
1、Segment
我們再來具體了解一下Segment的數據結構：
static final class Segment extends ReentrantLock implements Serializable {
transient volatile int count;
transient int modCount;
transient int threshold;
transient volatile HashEntry[] table;
final float loadFactor;
}
詳細解釋一下Segment里面的成員變量的意義：
count：Segment中元素的數量
modCount：對table的大小造成影響的操作的數量（比如put或者remove操作）
threshold：閾值，Segment里面元素的數量超過這個值就會對Segment進行擴容
table：鏈表數組，數組中的每一個元素代表了一個鏈表的頭部
loadFactor：負載因子，用于確定threshold
count用來統(tǒng)計該段數據的個數，它是volatile變量，它用來協(xié)調修改和讀取操作，以保證讀取操作能夠讀取到幾乎最新的修改。協(xié)調方式是這樣的，每次修改操作做了結構上的改變，如增加/刪除節(jié)點(修改節(jié)點的值不算結構上的改變)，都要寫count值，每次讀取操作開始都要讀取count的值。這利用了 Java 5中對volatile語義的增強，對同一個volatile變量的寫和讀存在happens-before關系。modCount統(tǒng)計段結構改變的次數，主要是為了檢測對多個段進行遍歷過程中某個段是否發(fā)生改變，在講述跨段操作時會還會詳述。threashold用來表示需要進行rehash的界限值。table數組存儲段中節(jié)點，每個數組元素是個hash鏈，用HashEntry表示。table也是volatile，這使得能夠讀取到最新的 table值而不需要同步。loadFactor表示負載因子。
2、HashEntry
Segment中的元素是以HashEntry的形式存放在鏈表數組中的，看一下HashEntry的結構：
static final class HashEntry {
final K key;
final int hash;
volatile V value;
final HashEntry next;
}
可以看到HashEntry的一個特點，除了value以外，其他的幾個變量都是final的，這意味著不能從hash鏈的中間或尾部添加或刪除節(jié)點，因為這需要修改next 引用值，所有的節(jié)點的修改只能從頭部開始。對于put操作，可以一律添加到Hash鏈的頭部。但是對于remove操作，可能需要從中間刪除一個節(jié)點，這就需要將要刪除節(jié)點的前面所有節(jié)點整個復制一遍，最后一個節(jié)點指向要刪除結點的下一個結點。這在講解刪除操作時還會詳述。為了確保讀操作能夠看到最新的值，將value設置成volatile，這避免了加鎖。
三、ConcurrentHashMap的初始化
下面我們來結合源代碼來具體分析一下ConcurrentHashMap的實現，先看下初始化方法
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
segmentShift = 32 - sshift;
segmentMask = ssize - 1;
this.segments = Segment.newArray(ssize);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = 1;
while (cap < c)
cap <<= 1;
for (int i = 0; i < this.segments.length; ++i)
this.segments[i] = new Segment(cap, loadFactor);
}
CurrentHashMap的初始化一共有三個參數，一個initialCapacity，表示初始的容量，一個loadFactor，表示負載參數，最后一個是concurrentLevel，代表ConcurrentHashMap內部的Segment的數量，ConcurrentLevel一經指定，不可改變，后續(xù)如果ConcurrentHashMap的元素數量增加導致ConrruentHashMap需要擴容，ConcurrentHashMap不會增加Segment的數量，而只會增加Segment中鏈表數組的容量大小，這樣的好處是擴容過程不需要對整個ConcurrentHashMap做rehash，而只需要對Segment里面的元素做一次rehash就可以了
整個ConcurrentHashMap的初始化方法還是非常簡單的，先是根據concurrentLevel來new出Segment，這里Segment的數量是不大于concurrentLevel的最大的2的指數，就是說Segment的數量永遠是2的指數個，這樣的好處是方便采用移位操作來進行hash，加快hash的過程。接下來就是根據intialCapacity確定Segment的容量的大小，每一個Segment的容量大小也是2的指數，同樣使為了加快hash的過程。
這邊需要特別注意一下兩個變量，分別是segmentShift和segmentMask，這兩個變量在后面將會起到很大的作用，假設構造函數確定了Segment的數量是2的n次方，那么segmentShift就等于32減去n，而segmentMask就等于2的n次方減一。
四、ConcurrentHashMap的get操作
前面提到過ConcurrentHashMap的get操作是不用加鎖的，我們這里看一下其實現：
public V get(Object key) {
int hash = hash(key.hashCode());
return segmentFor(hash).get(key, hash);
}
第二行，對hash值進行了二次hash，之所以要進行再哈希，其目的是為了減少哈希沖突，使元素能夠均勻的分布在不同的Segment上，從而提高容器的存取效率。
看第三行，segmentFor這個函數用于確定操作應該在哪一個segment中進行，幾乎對ConcurrentHashMap的所有操作都需要用到這個函數，我們看下這個函數的實現：
1 final Segment segmentFor(int hash) {
2 return segments[(hash >>> segmentShift) & segmentMask];
3 }
這個函數用了位操作來確定Segment，根據傳入的hash值向右無符號右移segmentShift位，然后和segmentMask進行與操作，結合我們之前說的segmentShift和segmentMask的值，就可以得出以下結論：假設Segment的數量是2的n次方，根據元素的hash值的高n位就可以確定元素到底在哪一個Segment中。
在確定了需要在哪一個segment中進行操作以后，接下來的事情就是調用對應的Segment的get方法：
V get(Object key, int hash) {
if (count != 0) { // read-volatile // ①
HashEntry e = getFirst(hash);
while (e != null) {
if (e.hash == hash && key.equals(e.key)) {
V v = e.value;
if (v != null) // ② 注意這里
return v;
return readValueUnderLock(e); // recheck
}
e = e.next;
}
}
return null;
}
先看第二行代碼，這里對count進行了一次判斷，其中count表示Segment中元素的數量。我們可以來看一下count的定義：
transient volatile int count;
可以看到count是volatile的，實際上這里面利用了volatile的語義：
對volatile字段的寫入操作happens-before于每一個后續(xù)的同一個字段的讀操作。因為實際上put、remove等操作也會更新count的值，所以當競爭發(fā)生的時候，volatile的語義可以保證寫操作在讀操作之前，也就保證了寫操作對后續(xù)的讀操作都是可見的，這樣后面get的后續(xù)操作就可以拿到完整的元素內容。
然后，在第三行，調用了getFirst()來取得鏈表的頭部：
1 HashEntry getFirst(int hash) {
2 HashEntry[] tab = table;
3 return tab[hash & (tab.length - 1)];
4 }
同樣，這里也是用位操作來確定鏈表的頭部，hash值和HashTable的長度減一做與操作，最后的結果就是hash值的低n位，其中n是HashTable的長度以2為底的結果。
在確定了鏈表的頭部以后，就可以對整個鏈表進行遍歷，看第4行，取出key對應的value的值，如果拿出的value的值是null，則可能這個key，value對正在put的過程中，如果出現這種情況，那么就加鎖來保證取出的value是完整的，如果不是null，則直接返回value。
get方法沒有使用鎖來同步，只是判斷獲取的entry的value是否為null，為null時才使用加鎖的方式再次去獲取。
這個實現很微妙，沒有鎖同步的話，靠什么保證同步呢？我們一步步分析。
第一步，先判斷一下 count != 0；count變量表示segment中存在entry的個數。如果為0就不用找了。假設這個時候恰好另一個線程put或者remove了這個segment中的一個entry，會不會導致兩個線程看到的count值不一致呢？看一下count 變量的定義：
transient volatile int count;
它使用了volatile來修改。在Java5之后，JMM實現了對volatile的保證：對volatile域的寫入操作happens-before于每一個后續(xù)對同一個域的讀寫操作。所以，每次判斷count變量的時候，即使恰好其他線程改變了segment也會體現出來。
第二步，獲取到要該key所在segment中的索引地址，如果該地址有相同的hash對象，順著鏈表一直比較下去找到該entry。當找到entry的時候，先做了一次比較： if(v != null) 我們用紅色注釋的地方。這是為何呢？考慮一下，如果這個時候，另一個線程恰好新增/刪除了entry，或者改變了entry的value，會如何？
前面說過HashEntry類的結構，除了 value，其它成員都是final修飾的，也就是說value可以被改變，其它都不可以改變，包括指向下一個HashEntry的next也不能被改變。
（1）在get代碼的①和②之間，另一個線程新增了一個entry。如果另一個線程新增的這個entry又恰好是我們要get的，這事兒就比較微妙了。下圖大致描述了put 一個新的entry的過程。
因為每個HashEntry中的next也是final的，沒法對鏈表最后一個元素增加一個后續(xù)entry所以新增一個entry的實現方式只能通過頭結點來插入了。
newEntry對象是通過 new HashEntry(K k , V v, HashEntry next) 來創(chuàng)建的。如果另一個線程剛好new 這個對象時，當前線程來get它。因為沒有同步，就可能會出現當前線程得到的newEntry對象是一個沒有完全構造好的對象引用。沒有鎖同步的話，new 一個對象對于多線程看到這個對象的狀態(tài)是沒有保障的，這里同樣有可能一個線程new這個對象的時候還沒有執(zhí)行完構造函數就被另一個線程得到這個對象引用。所以才需要判斷一下：if (v != null) 如果確實是一個不完整的對象，則使用鎖的方式再次get一次。
有沒有可能會put進一個value為null的entry？ 不會的，已經做了檢查，這種情況會拋出異常，所以 ②處的判斷完全是出于對多線程下訪問一個new出來的對象的狀態(tài)檢測。
（2）在get代碼的①和②之間，另一個線程修改了一個entry的value。value是用volitale修飾的，可以保證讀取時獲取到的是修改后的值。
（3）在get代碼的①之后，另一個線程刪除了一個entry。
假設我們的鏈表元素是：e1-> e2 -> e3 -> e4 我們要刪除 e3這個entry，因為HashEntry中next的不可變，所以我們無法直接把e2的next指向e4，而是將要刪除的節(jié)點之前的節(jié)點復制一份，形成新的鏈表。它的實現大致如下圖所示：
如果我們get的也恰巧是e3，可能我們順著鏈表剛找到e1，這時另一個線程就執(zhí)行了刪除e3的操作，而我們線程還會繼續(xù)沿著舊的鏈表找到e3返回。這里沒有辦法實時保證了。
我們第①處就判斷了count變量，它保障了在 ①處能看到其他線程修改后的。①之后到②之間，如果再次發(fā)生了其他線程再刪除了entry節(jié)點，就沒法保證看到最新的了。不過這也沒什么關系，即使我們返回e3的時候，它被其他線程刪除了，暴漏出去的e3也不會對我們新的鏈表造成影響。
這其實是一種樂觀設計，設計者假設 ①之后到②之間 發(fā)生被其它線程增、刪、改的操作可能性很小，所以不采用同步設計，而是采用了事后（其它線程這期間也來操作，并且可能發(fā)生非安全事件）彌補的方式。而因為其他線程的“改”和“刪”對我們的數據都不會造成影響，所以只有對“新增”操作進行了安全檢查，就是②處的非null檢查，如果確認不安全事件發(fā)生，則采用加鎖的方式再次get。這樣做減少了使用互斥鎖對并發(fā)性能的影響。可能有人懷疑remove操作中復制鏈表的方式是否代價太大，這里我沒有深入比較，不過既然Java5中這么實現，我想new一個對象的代價應該已經沒有早期認為的那么嚴重。
五、ConcurrentHashMap的put操作
看完了get操作，再看下put操作，put操作的前面也是確定Segment的過程，這里不再贅述，直接看關鍵的segment的put方法：
V put(K key, int hash, V value, boolean onlyIfAbsent) {
lock();
try {
int c = count;
if (c++ > threshold) // ensure capacity
rehash();
HashEntry[] tab = table;
int index = hash & (tab.length - 1);
HashEntry first = tab[index];
HashEntry e = first;
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
V oldValue;
if (e != null) {
oldValue = e.value;
if (!onlyIfAbsent)
e.value = value;
}
else {
oldValue = null;
++modCount;
tab[index] = new HashEntry(key, hash, first, value);
count = c; // write-volatile
}
return oldValue;
} finally {
unlock();
}
}
首先對Segment的put操作是加鎖完成的，然后在第五行，如果Segment中元素的數量超過了閾值（由構造函數中的loadFactor算出）這需要進行對Segment擴容，并且要進行rehash，關于rehash的過程大家可以自己去了解，這里不詳細講了。
第8和第9行的操作就是getFirst的過程，確定鏈表頭部的位置。
第11行這里的這個while循環(huán)是在鏈表中尋找和要put的元素相同key的元素，如果找到，就直接更新更新key的value，如果沒有找到，則進入21行這里，生成一個新的HashEntry并且把它加到整個Segment的頭部，然后再更新count的值。
該方法也是在持有段鎖(鎖定整個segment)的情況下執(zhí)行的，這當然是為了并發(fā)的安全，修改數據是不能并發(fā)進行的，必須得有個判斷是否超限的語句以確保容量不足時能夠rehash。接著是找是否存在同樣一個key的結點，如果存在就直接替換這個結點的值。否則創(chuàng)建一個新的結點并添加到hash鏈的頭部，這時一定要修改modCount和count的值，同樣修改count的值一定要放在最后一步。put方法調用了rehash方法，reash方法實現得也很精巧，主要利用了table的大小為2^n，這里就不介紹了。而比較難懂的是這句int index = hash & (tab.length - 1)，原來segment里面才是真正的hashtable，即每個segment是一個傳統(tǒng)意義上的hashtable，如上圖，從兩者的結構就可以看出區(qū)別，這里就是找出需要的entry在table的哪一個位置，之后得到的entry就是這個鏈的第一個節(jié)點，如果e!=null，說明找到了，這是就要替換節(jié)點的值（onlyIfAbsent == false），否則，我們需要new一個entry，它的后繼是first，而讓tab[index]指向它，什么意思呢？實際上就是將這個新entry插入到鏈頭，剩下的就非常容易理解了。
六、ConcurrentHashMap的remove操作
Remove操作的前面一部分和前面的get和put操作一樣，都是定位Segment的過程，然后再調用Segment的remove方法：
V remove(Object key, int hash, Object value) {
lock();
try {
int c = count - 1;
HashEntry[] tab = table;
int index = hash & (tab.length - 1);
HashEntry first = tab[index];
HashEntry e = first;
while (e != null && (e.hash != hash || !key.equals(e.key)))
e = e.next;
V oldValue = null;
if (e != null) {
V v = e.value;
if (value == null || value.equals(v)) {
oldValue = v;
// All entries following removed node can stay
// in list, but all preceding ones need to be
// cloned.
++modCount;
HashEntry newFirst = e.next;
for (HashEntry p = first; p != e; p = p.next)
newFirst = new HashEntry(p.key, p.hash,
newFirst, p.value);
tab[index] = newFirst;
count = c; // write-volatile
}
}
return oldValue;
} finally {
unlock();
}
}
首先remove操作也是確定需要刪除的元素的位置，不過這里刪除元素的方法不是簡單地把待刪除元素的前面的一個元素的next指向后面一個就完事了，我們之前已經說過HashEntry中的next是final的，一經賦值以后就不可修改，在定位到待刪除元素的位置以后，程序就將待刪除元素前面的那一些元素全部復制一遍，然后再一個一個重新接到鏈表上去，看一下下面這一幅圖來了解這個過程：
假設鏈表中原來的元素如上圖所示，現在要刪除元素3，那么刪除元素3以后的鏈表就如下圖所示：
整個操作是在持有段鎖的情況下執(zhí)行的，空白行之前(第11行之前)的行主要是定位到要刪除的節(jié)點e。接下來，如果不存在這個節(jié)點就直接返回null，否則就要將e前面的結點復制一遍，尾結點指向e的下一個結點。e后面的結點不需要復制，它們可以重用。
中間那個for循環(huán)是做什么用的呢？（第22行）從代碼來看，就是將定位之后的所有entry克隆并拼回前面去，但有必要嗎？每次刪除一個元素就要將那之前的元素克隆一遍？這點其實是由entry的不變性來決定的，仔細觀察entry定義，發(fā)現除了value，其他所有屬性都是用final來修飾的，這意味著在第一次設置了next域之后便不能再改變它，取而代之的是將它之前的節(jié)點全都克隆一次。至于entry為什么要設置為不變性，這跟不變性的訪問不需要同步從而節(jié)省時間有關。
整個remove實現并不復雜，但是需要注意如下幾點。第一，當要刪除的結點存在時，刪除的最后一步操作要將count的值減一。這必須是最后一步操作，否則讀取操作可能看不到之前對段所做的結構性修改。第二，remove執(zhí)行的開始就將table賦給一個局部變量tab，這是因為table是 volatile變量，讀寫volatile變量的開銷很大。編譯器也不能對volatile變量的讀寫做任何優(yōu)化，直接多次訪問非volatile實例變量沒有多大影響，編譯器會做相應優(yōu)化。
七、總結
ConcurrentHashMap背景：出現的原因是因為我們起先使用的是HashMap和HashTable，但是隨著并發(fā)量的增加，HashMap并沒有使用同步，在多線程情況下使用HashMap的時候就會出現并發(fā)問題，而HashTable雖然是安全的，但是使用的是synchronized 鎖整表操作，這樣在性能上將會產生很大的影響。那么如何能設計出一款即安全，在效率上又高的集合呢，這樣就有了ConcurrentHashMap的產生。
ConcurrentHashMap采用的是鎖分段技術，內部為Segment數組來進行細分，而每個Segment又通過HashEntry數組來進行組裝，當進行寫操作的時候，只需要對這個key對應的Segment進行加鎖操作，加鎖同時不會對其他的Segment造成影響。總的Map包含了16個Segment（默認數量），每個Segment內部包含16個HashEntry（默認數量），這樣對于這個key所在的Segment加鎖的同時，其他15個Segmeng還能正常使用，在性能上有了大大的提升。
同時ConcurrentHashMap只是針對put方法進行了加鎖，而對于get方法并沒有采用加鎖的操作，因為具體的值，在Segment的HashEntry里面是volatile的，基于happens-before（先行發(fā)生）原則，對數據的寫先行發(fā)生于對數據的讀，所以再讀取的時候獲取到的必然是最新的結果。
因為對數組的操作，在主內存和工作內存中，load和use、assgin和store是必然連在一起的，一旦使用（use）發(fā)生，那load必先行發(fā)生于use之前，use前必然從主內存中加載最新的值到工作內存的變量副本里。而一旦賦值（assgin），必然先行發(fā)生于store將值傳遞給主內存，在write到主內存中去。所以put方式無需加鎖也能獲取到最新的結果。
size操作是先請求2次的count數量，如果有發(fā)生變化，則對put、remove、clean進行加鎖，在統(tǒng)計完之后unlock。
