Java ConcurrentHashMap原理解析

背景：

對于ConcurrentHashMap的實現原理，很多時候我們只是知道它采用鎖分離技術，在高并發的的情況下可以保證線程安全，但具體其實現原理及實現細節卻沒有細細研究過，今天就針對其應用場景和原理和大家分享一下。

原理解析

java.util.concurrent.ConcurrentHashMap 是jdk1.5之后支持高并發，高吞吐量的hashmap的實現，其主要是實現map接口 和 ConcurrentMap接口，我們看下類圖

對于普通的HashMap,java是采用鏈式結構解決hash沖突的，

下面是一個普通的HashMap的數據結構圖的表示,HashMap的通過hash算法將數據分配到一個數組內(bucket),然后每個bucket中采用鏈表的結構解決沖突，

我們來再看下ConcurrentHashMap的簡單的數據結構的圖

　ConcurrentHashMap 類中包含兩個靜態內部類HashEntry和Segment。HashEntry用來封裝映射表的鍵/值對；Segment 用來充當數據劃分和鎖的角色，每個Segment對象守護整個散列映射表的若干個table。每個table是由若干個 HashEntry對象鏈接起來的鏈表。一個ConcurrentHashMap實例中包含由若干個Segment對象組成的數組, 因此由此可知，要想定位到一個元素需要經過兩次的hash，第一次定位到segment，第二次定位到鏈表頭部，因此hash時間要比普通的 hashmap的 hash算法長。

我們看下每個segment是怎么定義的：

    static final class Segment extends ReentrantLock implements Serializable {  
        transient volatile int count;  
        transient int modCount;  
        transient int threshold;  
        transient volatile AtomicReferenceArray<HashEntry> table;  
        final float loadFactor;  
    }  

Segment繼承了ReentrantLock，表明每個segment都可以當做一個鎖。（ReentrantLock前文已經提到，不了解的話就把當做synchronized的替代者吧）這樣對每個segment中的數據需要同步操作的話都是使用每個segment容器對象自身的鎖來實現。只有對全局需要改變時鎖定的是所有的segment。

上面的這種做法，就稱之為“分離鎖（lock striping）”。

下面我們來看下ConcurrentHashMap的get操作，他是不需要加鎖的

    V get(Object key, int hash) {  
              if (count != 0) { // read-volatile  
                  HashEntry<K,V> 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;  
          }  

上面的代碼中，一開始就對volatile變量count進行了讀取比較，這個還是java5對volatile語義增強的作用，這樣就可以獲取變量的可見性。所以count != 0之后，我們可以認為對應的hashtable是最新的，當然由于讀取的時候沒有加鎖，在get的過程中，可能會有更新。當發現根據key去找元素的時候，但發現找得的key對應的value為null，這個時候可能會有其他線程正在對這個元素進行寫操作，所以需要在使用鎖的情況下在讀取一下 value，以確保最終的值。

在ConcurrentHashMap的remove，put操作還是比較簡單的，都是將remove或者put操作交給key所對應的 segment去做的，所以當幾個操作不在同一個segment的時候就可以并發的進行。具體代碼就不在這里粘貼了，大家有興趣可以去看下源碼的實現。

總結以及注意事項

在實際的應用中，散列表一般的應用場景是：除了少數插入操作和刪除操作外，絕大多數都是讀取操作，而且讀操作在大多數時候都是成功的。正是基于這個前提，ConcurrentHashMap 針對讀操作做了大量的優化。通過 HashEntry 對象的不變性和用 volatile 型變量協調線程間的內存可見性，使得大多數時候，讀操作不需要加鎖就可以正確獲得值。這個特性使得 ConcurrentHashMap 的并發性能在分離鎖的基礎上又有了近一步的提高。

總結

ConcurrentHashMap 是一個并發散列映射表的實現，它允許完全并發的讀取，并且支持給定數量的并發更新。相比于 HashTable 和用同步包裝器包裝的 HashMap（Collections.synchronizedMap(new HashMap())），ConcurrentHashMap擁有更高的并發性。在 HashTable 和由同步包裝器包裝的 HashMap 中，使用一個全局的鎖來同步不同線程間的并發訪問。同一時間點，只能有一個線程持有鎖，也就是說在同一時間點，只能有一個線程能訪問容器。這雖然保證多線程間的安全并發訪問，但同時也導致對容器的訪問變成串行化的了。

在使用鎖來協調多線程間并發訪問的模式下，減小對鎖的競爭可以有效提高并發性。有兩種方式可以減小對鎖的競爭：

  1  減小請求同一個鎖的 頻率。

  2  減少持有鎖的時間。

ConcurrentHashMap 的高并發性主要來自于三個方面：

 1  用分離鎖實現多個線程間的更深層次的共享訪問。

 2  用 HashEntery 對象的不變性來降低執行讀操作的線程在遍歷鏈表期間對加鎖的需求。

 3  通過對同一個 Volatile 變量的寫 / 讀訪問，協調不同線程間讀 / 寫操作的內存可見性。

使用分離鎖，減小了請求同一個鎖的頻率。

通過 HashEntery 對象的不變性及對同一個 Volatile 變量的讀 / 寫來協調內存可見性，使得讀操作大多數時候不需要加鎖就能成功獲取到需要的值。由于散列映射表在實際應用中大多數操作都是成功的讀操作，所以 2 和 3 既可以減少請求同一個鎖的頻率，也可以有效減少持有鎖的時間。

通過減小請求同一個鎖的頻率和盡量減少持有鎖的時間，使得 ConcurrentHashMap 的并發性相對于 HashTable 和用同步包裝器包裝的 HashMap有了質的提高。

參考資料

http://www.ibm.com/developerworks/cn/java/java-lo-concurrenthashmap/index.html
http://blog.csdn.net/statckoverflow/article/details/17652141