ConcurrentHashMap是java5中新增加的一個線程安全的Map集合，可以用來替代HashTable。對于ConcurrentHashMap是如何提高其效率的，可能大多人只是知道它使用了多個鎖代替HashTable中的單個鎖，也就是鎖分離技術（Lock Stripping）。實際上，ConcurrentHashMap對提高并發方面的優化，還有一些其它的技巧在里面（比如你是否知道在get操作的時候，它是否也使用了鎖來保護？）。

提供其他原子 putIfAbsent、remove、replace 方法的 Map。內存一致性效果：當存在其他并發 collection 時，將對象放入 ConcurrentMap 之前的線程中的操作 happen-before 隨后通過另一線程從 ConcurrentMap 中訪問或移除該元素的操作。

我們不關心ConcurrentMap中新增的接口，重點理解一下內存一致性效果中的“happens-before”是怎么回事。因為要想從根本上講明白，這個是無法避開的。這又不得不從Java存儲模型來談起了。

在解釋該規則之前，我們先看一段多線程訪問數據的代碼例子：

public class Test1 {    PRivate int a=1, b=2;    public void foo(){  // 線程1         a=3;        b=4;    }    public int getA(){ // 線程2        return a;    }        public int getB(){ // 線程2        return b;    }}

上面的代碼，當線程1執行foo方法的時候，線程2訪問getA和getB會得到什么樣的結果？答案：

A：a=1, b=2  // 都未改變B：a=3, b=4  // 都改變了C：a=3, b=2  //  a改變了，b未改變D：a=1, b=4  //  b改變了，a未改變

上面的A,B,C都好理解，但是D可能會出乎一些人的預料。一些不了解JMM的同學可能會問怎么可能 b=4語句會先于 a=3 執行？

這是一個多線程之間內存可見性（Visibility）順序不一致的問題。有兩種可能會造成上面的D選項。

1) Java編譯器的重排序(Reording)操作有可能導致執行順序和代碼順序不一致。關于Reording：

Java語言規范規定了JVM要維護內部線程類似順序化語義(within-thread as-is-serial semantics)：只要程序的最終結果等同于它在嚴格的順序化環境中執行的結果，那么上述所有的行為都是允許的。

上面的話是《Java并發編程實踐》一書中引自Java語言規范的，感覺翻譯的不太好。簡單的說：假設代碼有兩條語句，代碼順序是語句1先于語句2執行；那么只要語句2不依賴于語句1的結果，打亂它們的順序對最終的結果沒有影響的話，那么真正交給CPU去執行時，他們的順序可以是沒有限制的。可以允許語句2先于語句1被CPU執行，和代碼中的順序不一致。

重排序（Reordering）是JVM針對現代CPU的一種優化，Reordering后的指令會在性能上有很大提升。(不知道這種優化對于多核CPU是否更加明顯，也或許和單核多核沒有關系。)

因為我們例子中的兩條賦值語句，并沒有依賴關系，無論誰先誰后結果都是一樣的，所以就可能有Reordering的情況，這種情況下，對于其他線程來說就可能造成了可見性順序不一致的問題。

2) 從線程工作內存寫回主存時順序無法保證。下圖描述了JVM中主存和線程工作內存之間的交互：

JLS中對線程和主存互操作定義了6個行為，分別為load，save，read，write，assign和use，這些操作行為具有原子性，且相互依賴，有明確的調用先后順序。這個細節也比較繁瑣，我們暫不深入追究。先簡單認為線程在修改一個變量時，先拷貝入線程工作內存中，在線程工作內存修改后再寫回主存(Main Memery)中。

假設例子中Reording后順序仍與代碼中的順序一致，那么接下來呢？有意思的事情就發生在線程把Working Copy Memery中的變量寫回Main Memery的時刻。線程1把變量寫回Main Memery的過程對線程2的可見性順序也是無法保證的。上面的列子，a=3; b=4; 這兩個語句在 Working Copy Memery中執行后，寫回主存的過程對于線程2來說同樣可能出現先b=4；后a=3；這樣的相反順序。

正因為上面的那些問題，JMM中一個重要問題就是：如何讓多線程之間，對象的狀態對于各線程的“可視性”是順序一致的。它的解決方式就是 Happens-before 規則：JMM為所有程序內部動作定義了一個偏序關系，叫做happens-before。要想保證執行動作B的線程看到動作A的結果（無論A和B是否發生在同一個線程中），A和B之間就必須滿足happens-before關系。

我們現在來看一下“Happens-before”規則都有哪些（摘自《Java并發編程實踐》）：

① 程序次序法則：線程中的每個動作A都happens-before于該線程中的每一個動作B，其中，在程序中，所有的動作B都能出現在A之后。② 監視器鎖法則：對一個監視器鎖的解鎖 happens-before于每一個后續對同一監視器鎖的加鎖。③ volatile變量法則：對volatile域的寫入操作happens-before于每一個后續對同一個域的讀寫操作。④ 線程啟動法則：在一個線程里，對Thread.start的調用會happens-before于每個啟動線程的動作。⑤ 線程終結法則：線程中的任何動作都happens-before于其他線程檢測到這個線程已經終結、或者從Thread.join調用中成功返回，或Thread.isAlive返回false。⑥ 中斷法則：一個線程調用另一個線程的interrupt happens-before于被中斷的線程發現中斷。⑦ 終結法則：一個對象的構造函數的結束happens-before于這個對象finalizer的開始。⑧ 傳遞性：如果A happens-before于B，且B happens-before于C，則A happens-before于C

我們重點關注的是②，③，這兩條也是我們通常編程中常用的。后續分析ConcurrenHashMap時也會看到使用到鎖(ReentrantLock)，Volatile，final等手段來保證happens-before規則的。

使用鎖方式實現“Happens-before”是最簡單，容易理解的。

早期Java中的鎖只有最基本的synchronized，它是一種互斥的實現方式。在Java5之后，增加了一些其它鎖，比如ReentrantLock，它基本作用和synchronized相似，但提供了更多的操作方式，比如在獲取鎖時不必像synchronized那樣只是傻等，可以設置定時，輪詢，或者中斷，這些方法使得它在獲取多個鎖的情況可以避免死鎖操作。

而我們需要了解的是ReentrantLock的性能相對synchronized來說有很大的提高。（不過據說Java6后對synchronized進行了優化，兩者已經接近了。）在ConcurrentHashMap中，每個hash區間使用的鎖正是ReentrantLock。

Volatile可以看做一種輕量級的鎖，但又和鎖有些不同。a) 它對于多線程，不是一種互斥（mutex）關系。b) 用volatile修飾的變量，不能保證該變量狀態的改變對于其他線程來說是一種“原子化操作”。

在Java5之前，JMM對Volatile的定義是：保證讀寫volatile都直接發生在main memory中，線程的working memory不進行緩存。它只承諾了讀和寫過程的可見性，并沒有對Reording做限制，所以舊的Volatile并不太可靠。在Java5之后，JMM對volatile的語義進行了增強。就是我們看到的③ volatile變量法則。

那對于“原子化操作”怎么理解呢？看下面例子：

private static volatile int nextSerialNum = 0;public static int generateSerialNumber(){    return nextSerialNum++;}

上面代碼中對nextSerialNum使用了volatile來修飾，根據前面“Happens-Before”法則的第三條Volatile變量法則，看似不同線程都會得到一個新的serialNumber

問題出在了 nextSerialNum++ 這條語句上，它不是一個原子化的，實際上是read-modify-write三項操作，這就有可能使得在線程1在write之前，線程2也訪問到了nextSerialNum，造成了線程1和線程2得到一樣的serialNumber。所以，在使用Volatile時，需要注意a) 需不需要互斥；b) 對象狀態的改變是不是原子化的。

最后也說一下final 關鍵字。

不變模式（immutable）是多線程安全里最簡單的一種保障方式。因為你拿他沒有辦法，想改變它也沒有機會。不變模式主要通過final關鍵字來限定的。在JMM中final關鍵字還有特殊的語義。Final域使得確保初始化安全性（initialization safety）成為可能，初始化安全性讓不可變形對象不需要同步就能自由地被訪問和共享。

3）經過前面的了解，下面我們用Happens-Before規則理解一個經典問題：雙重檢測鎖(DCL)為什么在java中不適用？

public class LazySingleton {    private int someField;    private static LazySingleton instance;    private LazySingleton(){        this.someField = new Random().nextInt(200) + 1; // (1)    }    public static LazySingleton getInstance() {        if (instance == null) {// (2)            synchronized (LazySingleton.class) { // (3)              if (instance == null) { // (4)                instance = new LazySingleton(); // (5)              }            }        }        return instance; // (6)    }    public int getSomeField() {        return this.someField;  // (7)    }}

我想簡單的用對象創建期間的實際場景來分析一下：（注意，這種場景是我個人的理解，所看的資料也是非官方的，不完全保證正確。如果發現不對請指出。

假設線程1執行完(5)時，線程2正好執行到了(2)；看看 new LazySingleton(); 這個語句的執行過程： 它不是一個原子操作，實際是由多個步驟，我們從我們關注的角度簡化一下，簡單的認為它主要有2步操作好了：a） 在內存中分配空間，并將引用指向該內存空間。b） 執行對象的初始化的邏輯(和操作)，完成對象的構建。

此時因為線程1和線程2沒有用同步，他們之間不存在“Happens-Before”規則的約束，所以在線程1創建LazySingleton對象的 a),b)這兩個步驟對于線程2來說會有可能出現a)可見，b)不可見造成了線程2獲取到了一個未創建完整的lazySingleton對象引用，為后邊埋下隱患。

之所以這里舉到 DCL這個例子，是因為我們后邊分析ConcurrentHashMap時，也會遇到相似的情況。對于對象的創建，出于樂觀考慮，兩個線程之間沒有用“Happens-Before規則來約束”另一個線程可能會得到一個未創建完整的對象，這種情況必須要檢測，后續分析ConcurrentHashMap時再討論。

我們關注的操作有：get，put，remove 這3個操作。

對于哈希表，Java中采用鏈表的方式來解決hash沖突的。一個HashMap的數據結構看起來類似下圖：

實現了同步的HashTable也是這樣的結構，它的同步使用鎖來保證的，并且所有同步操作使用的是同一個鎖對象。這樣若有n個線程同時在get時，這n個線程要串行的等待來獲取鎖。

ConcurrentHashMap中對這個數據結構，針對并發稍微做了一點調整。它把區間按照并發級別(concurrentLevel)，分成了若干個segment。默認情況下內部按并發級別為16來創建。對于每個segment的容量，默認情況也是16。當然并發級別(concurrentLevel)和每個段(segment)的初始容量都是可以通過構造函數設定的。

創建好默認的ConcurrentHashMap之后，它的結構大致如下圖：

看起來只是把以前HashTable的一個hash bucket創建了16份而已。有什么特別的嗎？沒啥特別的。

繼續看每個segment是怎么定義的：

static final class Segment<K,V> extends ReentrantLock implements Serializable

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

面的這種做法，就稱之為“分離鎖（lock striping）”。有必要對“分拆鎖”和“分離鎖”的概念描述一下：

分拆鎖(lock spliting)就是若原先的程序中多處邏輯都采用同一個鎖，但各個邏輯之間又相互獨立，就可以拆(Spliting)為使用多個鎖，每個鎖守護不同的邏輯。分拆鎖有時候可以被擴展，分成可大可小加鎖塊的集合，并且它們歸屬于相互獨立的對象，這樣的情況就是分離鎖(lock striping)。（摘自《Java并發編程實踐》）

看上去，單是這樣就已經能大大提高多線程并發的性能了。還沒完，繼續看我們關注的get,put,remove這三個函數怎么保證數據同步的。

public V get(Object key) {    int hash = hash(key); // throws NullPointerException if key null    return segmentFor(hash).get(key, hash);}

它沒有使用同步控制，交給segment去找，再看Segment中的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;}

它也沒有使用鎖來同步，只是判斷獲取的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于每一個后續對同一個域的讀寫操作。所以，每次判斷count變量的時候，即使恰好其他線程改變了segment也會體現出來。

第二步，獲取到要該key所在segment中的索引地址，如果該地址有相同的hash對象，順著鏈表一直比較下去找到該entry。當找到entry的時候，先做了一次比較： if(v != null) 我們用紅色注釋的地方。這是為何呢？

考慮一下，如果這個時候，另一個線程恰好新增/刪除了entry，或者改變了entry的value，會如何？

先看一下HashEntry類結構。

static final class HashEntry<K,V> {    final K key;    final int hash;    volatile V value;    final HashEntry<K,V> next;    。。。}

除了 value，其它成員都是final修飾的，也就是說value可以被改變，其它都不可以改變，包括指向下一個HashEntry的next也不能被改變。（那刪除一個entry時怎么辦？后續會講到。）

1) 在get代碼的①和②之間，另一個線程新增了一個entry如果另一個線程新增的這個entry又恰好是我們要get的，這事兒就比較微妙了。

下圖大致描述了put 一個新的entry的過程。

因為每個HashEntry中的next也是final的，沒法對鏈表最后一個元素增加一個后續entry所以新增一個entry的實現方式只能通過頭結點來插入了。

newEntry對象是通過 new HashEntry(K k , V v, HashEntry next) 來創建的。如果另一個線程剛好new 這個對象時，當前線程來get它。因為沒有同步，就可能會出現當前線程得到的newEntry對象是一個沒有完全構造好的對象引用。

回想一下我們之前討論的DCL的問題，這里也一樣，沒有鎖同步的話，new 一個對象對于多線程看到這個對象的狀態是沒有保障的，這里同樣有可能一個線程new這個對象的時候還沒有執行完構造函數就被另一個線程得到這個對象引用。所以才需要判斷一下：if (v != null) 如果確實是一個不完整的對象，則使用鎖的方式再次get一次。

有沒有可能會put進一個value為null的entry？ 不會的，已經做了檢查，這種情況會拋出異常，所以 ②處的判斷完全是出于對多線程下訪問一個new出來的對象的狀態檢測。

2) 在get代碼的①和②之間，另一個線程修改了一個entry的value

value是用volitale修飾的，可以保證讀取時獲取到的是修改后的值。

3) 在get代碼的①之后，另一個線程刪除了一個entry

假設我們的鏈表元素是：e1-> e2 -> e3 -> e4 我們要刪除 e3這個entry，因為HashEntry中next的不可變，所以我們無法直接把e2的next指向e4，而是將要刪除的節點之前的節點復制一份，形成新的鏈表。

它的實現大致如下圖所示：

如果我們get的也恰巧是e3，可能我們順著鏈表剛找到e1，這時另一個線程就執行了刪除e3的操作，而我們線程還會繼續沿著舊的鏈表找到e3返回。這里沒有辦法實時保證了。

我們第①處就判斷了count變量，它保障了在 ①處能看到其他線程修改后的。①之后到②之間，如果再次發生了其他線程再刪除了entry節點，就沒法保證看到最新的了。

不過這也沒什么關系，即使我們返回e3的時候，它被其他線程刪除了，暴漏出去的e3也不會對我們新的鏈表造成影響。

這其實是一種樂觀設計，設計者假設 ①之后到②之間 發生被其它線程增、刪、改的操作可能性很小，所以不采用同步設計，而是采用了事后（其它線程這期間也來操作，并且可能發生非安全事件）彌補的方式。而因為其他線程的“改”和“刪”對我們的數據都不會造成影響，所以只有對“新增”操作進行了安全檢查，就是②處的非null檢查，如果確認不安全事件發生，則采用加鎖的方式再次get。

這樣做減少了使用互斥鎖對并發性能的影響。可能有人懷疑remove操作中復制鏈表的方式是否代價太大，這里我沒有深入比較，不過既然Java5中這么實現，我想new一個對象的代價應該已經沒有早期認為的那么嚴重。

我們基本分析完了get操作。對于put和remove操作，是使用鎖同步來進行的，不過是用的ReentrantLock而不是synchronized，性能上要更高一些。它們的實現前文都已經提到過，就沒什么可分析的了。

我們還需要知道一點，ConcurrentHashMap的迭代器不是Fast-Fail的方式，所以在迭代的過程中別其他線程添加/刪除了元素，不會拋出異常，也不能體現出元素的改動。但也沒有關系，因為每個entry的成員除了value都是final修飾的，暴漏出去也不會對其他元素造成影響。

ConcurrentHashMap<String, Boolean> map = new ...;Thread a = new Thread {    void run() {        map.put("first", true);        map.put("second", true);    }};Thread b = new Thread {    void run() {        map.clear();    }};a.start();b.start();a.join();b.join();

結果：

Map("first" -> true, "second" -> true)Map("second" -> true)Map()

Map("first" -> true)

ConcurrentHashMap<String, Boolean> map = new ...;List<String> myKeys = new ...;Thread a = new Thread {    void run() {        map.put("first", true);        // more stuff        map.remove("first");        map.put("second", true);    }};Thread b = new Thread {    void run() {        Set<String> keys = map.keySet();        for (String key : keys) {            myKeys.add(key);        }    }};a.start();b.start();a.join();b.join();

結果：

List()List("first")List("second")

List("first", "second")

解釋：對于這兩個現象的解釋：ConcurrentHashMap中的clear方法：

public void clear() {    for (int i = 0; i < segments.length; ++i)        segments[i].clear();}

如果線程b先執行了clear，清空了一部分segment的時候，線程a執行了put且正好把“first”放入了“清空過”的segment中，而把“second”放到了還沒有清空過的segment中，就會出現上面的情況。

第二段代碼，如果線程b執行了迭代遍歷到first，而此時線程a還沒有remove掉first，那么即使后續刪除了first，迭代器里不會反應出來，也不拋出異常，這種迭代器被稱為“弱一致性”(weakly consistent)迭代器。

參考：http://ifeve.com/java-concurrent-hashmap-2/