轉(zhuǎn):http:///java-concurrent-hashmap-2/

經(jīng)過之前的鋪墊，現(xiàn)在可以進(jìn)入正題了。
我們關(guān)注的操作有：get，put，remove 這3個(gè)操作。

對于哈希表，Java中采用鏈表的方式來解決hash沖突的。
一個(gè)HashMap的數(shù)據(jù)結(jié)構(gòu)看起來類似下圖：

實(shí)現(xiàn)了同步的HashTable也是這樣的結(jié)構(gòu)，它的同步使用鎖來保證的，并且所有同步操作使用的是同一個(gè)鎖對象。這樣若有n個(gè)線程同時(shí)在get時(shí)，這n個(gè)線程要串行的等待來獲取鎖。

ConcurrentHashMap中對這個(gè)數(shù)據(jù)結(jié)構(gòu)，針對并發(fā)稍微做了一點(diǎn)調(diào)整。
它把區(qū)間按照并發(fā)級別(concurrentLevel)，分成了若干個(gè)segment。默認(rèn)情況下內(nèi)部按并發(fā)級別為16來創(chuàng)建。對于每個(gè)segment的容量，默認(rèn)情況也是16。當(dāng)然并發(fā)級別(concurrentLevel)和每個(gè)段(segment)的初始容量都是可以通過構(gòu)造函數(shù)設(shè)定的。

創(chuàng)建好默認(rèn)的ConcurrentHashMap之后，它的結(jié)構(gòu)大致如下圖：

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

繼續(xù)看每個(gè)segment是怎么定義的：

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

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

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

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

看上去，單是這樣就已經(jīng)能大大提高多線程并發(fā)的性能了。還沒完，繼續(xù)看我們關(guān)注的get,put,remove這三個(gè)函數(shù)怎么保證數(shù)據(jù)同步的。

先看get方法：

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時(shí)才使用加鎖的方式再次去獲取。

這個(gè)實(shí)現(xiàn)很微妙，沒有鎖同步的話，靠什么保證同步呢？我們一步步分析。

第一步，先判斷一下 count != 0；count變量表示segment中存在entry的個(gè)數(shù)。如果為0就不用找了。
假設(shè)這個(gè)時(shí)候恰好另一個(gè)線程put或者remove了這個(gè)segment中的一個(gè)entry，會(huì)不會(huì)導(dǎo)致兩個(gè)線程看到的count值不一致呢？
看一下count變量的定義： transient volatile int count;
它使用了volatile來修改。我們前文說過，Java5之后，JMM實(shí)現(xiàn)了對volatile的保證：對volatile域的寫入操作happens-before于每一個(gè)后續(xù)對同一個(gè)域的讀寫操作。
所以，每次判斷count變量的時(shí)候，即使恰好其他線程改變了segment也會(huì)體現(xiàn)出來。

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

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

先看一下HashEntry類結(jié)構(gòu)。

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

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

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

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

因?yàn)槊總€(gè)HashEntry中的next也是final的，沒法對鏈表最后一個(gè)元素增加一個(gè)后續(xù)entry
所以新增一個(gè)entry的實(shí)現(xiàn)方式只能通過頭結(jié)點(diǎn)來插入了。

newEntry對象是通過 new HashEntry(K k , V v, HashEntry next) 來創(chuàng)建的。如果另一個(gè)線程剛好new 這個(gè)對象時(shí)，當(dāng)前線程來get它。因?yàn)闆]有同步，就可能會(huì)出現(xiàn)當(dāng)前線程得到的newEntry對象是一個(gè)沒有完全構(gòu)造好的對象引用。

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

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

2) 在get代碼的①和②之間，另一個(gè)線程修改了一個(gè)entry的value
value是用volitale修飾的，可以保證讀取時(shí)獲取到的是修改后的值。

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

假設(shè)我們的鏈表元素是：e1-> e2 -> e3 -> e4 我們要?jiǎng)h除 e3這個(gè)entry
因?yàn)镠ashEntry中next的不可變，所以我們無法直接把e2的next指向e4，而是將要?jiǎng)h除的節(jié)點(diǎn)之前的節(jié)點(diǎn)復(fù)制一份，形成新的鏈表。它的實(shí)現(xiàn)大致如下圖所示：

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

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

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

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

這樣做減少了使用互斥鎖對并發(fā)性能的影響?？赡苡腥藨岩蓃emove操作中復(fù)制鏈表的方式是否代價(jià)太大，這里我沒有深入比較，不過既然Java5中這么實(shí)現(xiàn)，我想new一個(gè)對象的代價(jià)應(yīng)該已經(jīng)沒有早期認(rèn)為的那么嚴(yán)重。

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

我們還需要知道一點(diǎn)，ConcurrentHashMap的迭代器不是Fast-Fail的方式，所以在迭代的過程中別其他線程添加/刪除了元素，不會(huì)拋出異常，也不能體現(xiàn)出元素的改動(dòng)。但也沒有關(guān)系，因?yàn)槊總€(gè)entry的成員除了value都是final修飾的，暴漏出去也不會(huì)對其他元素造成影響。

最后，再來看一下Java6文檔中對ConcurrentHashMap的描述（我們分析過的地方或者需要注意的使用了紅色字體）：

支持獲取的完全并發(fā)和更新的所期望可調(diào)整并發(fā)的哈希表。此類遵守與 Hashtable 相同的功能規(guī)范，并且包括對應(yīng)于 Hashtable 的每個(gè)方法的方法版本。不過，盡管所有操作都是線程安全的，但獲取操作不 必鎖定，并且不 支持以某種防止所有訪問的方式鎖定整個(gè)表。此類可以通過程序完全與 Hashtable 進(jìn)行互操作，這取決于其線程安全，而與其同步細(xì)節(jié)無關(guān)。

獲取操作（包括 get）通常不會(huì)受阻塞，因此，可能與更新操作交迭（包括 put 和 remove）。獲取會(huì)影響最近完成的 更新操作的結(jié)果。對于一些聚合操作，比如 putAll 和 clear，并發(fā)獲取可能只影響某些條目的插入和移除。類似地，在創(chuàng)建迭代器/枚舉時(shí)或自此之后，Iterators 和 Enumerations 返回在某一時(shí)間點(diǎn)上影響哈希表狀態(tài)的元素。它們不會(huì) 拋出 ConcurrentModificationException。不過，迭代器被設(shè)計(jì)成每次僅由一個(gè)線程使用。

這允許通過可選的 concurrencyLevel 構(gòu)造方法參數(shù)（默認(rèn)值為 16）來引導(dǎo)更新操作之間的并發(fā)，該參數(shù)用作內(nèi)部調(diào)整大小的一個(gè)提示。表是在內(nèi)部進(jìn)行分區(qū)的，試圖允許指示無爭用并發(fā)更新的數(shù)量。因?yàn)楣１碇械奈恢没旧鲜请S意的，所以實(shí)際的并發(fā)將各不相同。理想情況下，應(yīng)該選擇一個(gè)盡可能多地容納并發(fā)修改該表的線程的值。使用一個(gè)比所需要的值高很多的值可能會(huì)浪費(fèi)空間和時(shí)間，而使用一個(gè)顯然低很多的值可能導(dǎo)致線程爭用。對數(shù)量級估計(jì)過高或估計(jì)過低通常都會(huì)帶來非常顯著的影響。當(dāng)僅有一個(gè)線程將執(zhí)行修改操作，而其他所有線程都只是執(zhí)行讀取操作時(shí)，才認(rèn)為某個(gè)值是合適的。此外，重新調(diào)整此類或其他任何種類哈希表的大小都是一個(gè)相對較慢的操作，因此，在可能的時(shí)候，提供構(gòu)造方法中期望表大小的估計(jì)值是一個(gè)好主意。

參考：

http://www./topic/344876

本來我的分析已經(jīng)結(jié)束，不過正好看到Concurrency-interest郵件組中的一個(gè)問題，可以加深一下我們隊(duì)ConcurrentHashMap的理解，同時(shí)也反駁了我剛開始所說的“ConcurrentHashMap完全可以替代HashTable”，我必須糾正一下。先看例子：

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();

I would expect that one of the following scenarios to be true (for the contents of the map) after this code runs:

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

However, upon inspection of ConcurrentHashMap, it seems to me that the following scenario might also be true:

Map("first" -> true) ???

This seems surprising because “first” gets put before “second”, so if “second” is cleared, then surely “first” should be cleared too.

Likewise, consider the following code:

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();

I would expect one of the following scenarios to be true for the contents of myKeys after this code has run:

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

However, upon closer inspection, it seems that the following scenario might also be true:

List("first", "second") ???

This is surprising because “second” is only ever put into the map after “first” is removed. They should never be in the map simultaneously, but an iterator might perceive them to be so.

對于這兩個(gè)現(xiàn)象的解釋：ConcurrentHashMap中的clear方法：

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

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

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

Doug Lea 對這個(gè)問題的回復(fù)中提到：

We leave the tradeoff of consistency-strength versus scalability
as a user decision, so offer both synchronized and concurrent versions
of most collections, as discussed in the j.u.c package docs

http://java./javase/6/docs/api/java/util/concurrent/package-summary.html

大意是我們將“一致性強(qiáng)度”和“擴(kuò)展性”之間的對比交給用戶來權(quán)衡，所以大多數(shù)集合都提供了synchronized和concurrent兩個(gè)版本。

通過他的說法，我必須糾正我一開始以為ConcurrentHashMap完全可以代替HashTable的說法，如果你的環(huán)境要求“強(qiáng)一致性”的話，就不能用ConcurrentHashMap了，它的get，clear方法和迭代器都是“弱一致性”的。不過真正需要“強(qiáng)一致性”的場景可能非常少，我們大多應(yīng)用中ConcurrentHashMap是滿足的。

（全文完）如果您喜歡此文請點(diǎn)贊，分享，評論。