一、集合

1. ConcurrentHashMap 的實現(xiàn)原理

ConcurrentHashMap 在 JDK 1.6 和 1.7 都采用了相同的數(shù)據(jù)結(jié)構(gòu)，即分段鎖的技術(shù)來實現(xiàn)的。ConcurrentHashMap 內(nèi)部有一個叫 Segment 的數(shù)組，里面存放的都是 Segment 對象。Segment 對象繼承了 ReentrantLock，這樣就使得每個段都有一把鎖。 Segment 里面有一個被 volatile 修飾的 HashEntry 的數(shù)組。（在 ConcurrentHashMap 初始化的時候，創(chuàng)建了 Segment 數(shù)組，并初始化第一個元素。）

JDK 1.7

重要變量

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

    private static final long serialVersionUID = 2249069246763182397L;

    static final int MAX_SCAN_RETRIES =
        Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;

    transient volatile HashEntry<K,V>[] table;

    transient int count;

    transient int modCount;

    transient int threshold;

    final float loadFactor;
}

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

    HashEntry(int hash, K key, V value, HashEntry<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
}

put 操作

1. 判斷 value 是否為 null， 如果 value 為 null 則拋出異常。

2. 當(dāng)用戶調(diào)用 put 方法的時候，首先根據(jù) key 的 hash 值找到具體的 Segment 在 table 中的位置。

3. 如果這個位置上的 Segment 沒有初始化，則進(jìn)行初始化的操作。

4. 最后委托給 Segment 的 put 方法。此方法中會根據(jù)計算出的 (tab.length - 1) & hash 的 index 定位到 HashEntry， 如果這個位置上的節(jié)點為null，則新建一個 HashEntry并返回 。如果不為 null，則遍歷 HashEntry 的每一個節(jié)點，如果有相同的 key 存在則更新 value， 如果沒有則新建一個 HashEntry 放入鏈表頭部的位置。

5. 如果 ConcurrentHashMap 內(nèi)存放的元素個數(shù)超過了閾值，那么需要對其進(jìn)行擴(kuò)容。整個操作都是加鎖的。

get 操作

get 操作的時候沒有對 ConcurrentHashMap 進(jìn)行上鎖，

1. 根據(jù) key 的 hash 值計算出在哪個 Segment 上，再根據(jù) hash 值計算出在哪個 HashEntry 上

2. 然后遍歷 HashEntry 的所有節(jié)點，如果找到 key，那么就返回對應(yīng)的 value，如果 key 沒有找到，就返回 null。

remove 操作

1. 根據(jù) key 的 hash 值找到在哪個 Segment 上

2. 然后調(diào)用 Segment 的 remove 方法，根據(jù) int index = (tab.length - 1) & hash; 計算出 index 并找到對應(yīng)的 HashEntry

3. 遍歷 HashEntry 的所有節(jié)點，找到相同的 key（調(diào)用 key 的 equals 和 hashCode 方法）并刪除，并且返回 value。

擴(kuò)容操作（具體步驟還沒找到）

ConcurrentHashMap不會增加Segment的數(shù)量，而只會增加Segment中鏈表數(shù)組的容量大小，這樣的好處是擴(kuò)容過程不需要對整個ConcurrentHashMap做rehash，而只需要對Segment里面的元素做一次 resize 就可以了。

整個步驟如下：

1. 創(chuàng)建一個大小為原來 HashEntry 兩倍大小的數(shù)組，根據(jù) hash 算法重新將老 table 中的元素放入到新 table 中去。

這里的重點就是：

首先找到一個lastRun，lastRun之后的元素和lastRun是在同一個桶中，所以后面的不需要進(jìn)行變動。然后對開始到lastRun部分的元素，重新計算下設(shè)置到newTable中，每次都是將當(dāng)前元素作為newTable的首元素，之前老的鏈表作為該首元素的next部分。

JDK 1.8

ConcurrentHashMap 在 JDK 1.8 中進(jìn)行了大幅度的改進(jìn)。取消了 Segment 分段鎖的概念。采用了數(shù)組 + 鏈表 + 紅黑樹的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。內(nèi)部存放了一個 Node<K,V>[] table 的 table。 ConcurrentHashMap 在初始化的時候只是設(shè)置了一些變量值，并沒有對整個 table 進(jìn)行初始化，初始化的動作被放入到了第一次 put 元素的時候。

一些重要的變量

/**
 * races. Updated via CAS.
 * 記錄容器的容量大小，通過CAS更新
 */
private transient volatile long baseCount;

/**
 * 這個sizeCtl是volatile的，那么他是線程可見的，一個思考:它是所有修改都在CAS中進(jìn)行，但是sizeCtl為什么不設(shè)計成LongAdder(jdk8出現(xiàn)的)類型呢？
 * 或者設(shè)計成AtomicLong(在高并發(fā)的情況下比LongAdder低效)，這樣就能減少自己操作CAS了。
 *
 * 來看下注釋，當(dāng)sizeCtl小于0說明有多個線程正則等待擴(kuò)容結(jié)果，參考transfer函數(shù)
 *
 * sizeCtl等于0是默認(rèn)值，大于0是擴(kuò)容的閥值
 */
private transient volatile int sizeCtl;

/**
 *  自旋鎖 （鎖定通過 CAS） 在調(diào)整大小和/或創(chuàng)建 CounterCells 時使用。 在CounterCell類更新value中會使用，功能類似顯示鎖和內(nèi)置鎖，性能更好
 *  在Striped64類也有應(yīng)用
 */
private transient volatile int cellsBusy;

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    
    Node(int hash, K key, V val, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.val = val;
        this.next = next;
}

sizeCtl 變量

控制標(biāo)識符，用來控制table初始化和擴(kuò)容操作的，在不同的地方有不同的用途，其值也不同，所代表的含義也不同

• 負(fù)數(shù)代表正在進(jìn)行初始化或擴(kuò)容操作

• -1代表正在初始化

• -N 表示有N-1個線程正在進(jìn)行擴(kuò)容操作

• 正數(shù)或0代表hash表還沒有被初始化，這個數(shù)值表示初始化或下一次進(jìn)行擴(kuò)容的大小

put 操作

1. 首先判斷 key 和 value 是否為 null， 如果為 null 則拋出異常。

2. 然后在判斷 table 是否初始化，如果沒有初始化則通過 CAS 操作將 sizeCtl 的值設(shè)置為 -1，并執(zhí)行 table 的初始化操作。

3. 根據(jù) key 的 hash 定位到 key 所在 table 的位置，如果這個位置上沒有元素，則直接插入元素后返回。

4. 如果當(dāng)前節(jié)點的 hash 值為 -1，說明當(dāng)前的節(jié)點是 forwardingNode 節(jié)點，表示 table 正在擴(kuò)容，當(dāng)前線程需要幫助一起擴(kuò)容。（上面的過程走完之后，說明當(dāng)前的節(jié)點上有元素，需要對當(dāng)前節(jié)點加鎖然后操作）。

5. 如果當(dāng)前節(jié)點的 hash 值大于等于 0，說明是一個鏈表結(jié)構(gòu)，則遍歷鏈表，如果存在當(dāng)前 key 節(jié)點則替換 value，否則插入到鏈表尾部。

6. 如果 f 是 TreeBin 類型節(jié)點，則按照紅黑樹的方法更新或者增加節(jié)點。

7. 若鏈表長度 > TREEIFY_THRESHOLD(默認(rèn)是8)，則將鏈表轉(zhuǎn)換為紅黑樹結(jié)構(gòu)（并不是直接轉(zhuǎn)的，還需要進(jìn)一步判斷，具體的在treeifyBin方法中）。

8. 最后調(diào)用 addCount 方法，將 ConcurrentHashMap 的 size + 1，并判斷是否需要執(zhí)行擴(kuò)容操作，整個 put 過程結(jié)束。

get 操作

get 操作的時候沒有上鎖，如果整個table 為空，則返回null，否則根據(jù) key 的 hash 值找到 table 的 index 位置，然后根據(jù)鏈表或者樹形方式找到相對應(yīng)的節(jié)點，返回其 value 值。

remove 操作

源碼最后調(diào)用的是 replaceNode() 方法。具體沒有詳細(xì)看。

紅黑樹轉(zhuǎn)換

1. 什么時候轉(zhuǎn)換?

鏈表的元素個數(shù)達(dá)到了閾值 8 ，則會調(diào)用 treeifyBin 方法把鏈表轉(zhuǎn)換成紅黑樹，不過在結(jié)構(gòu)轉(zhuǎn)換之前，會對數(shù)組長度進(jìn)行判斷。如果數(shù)組長度n小于閾值 MIN_TREEIFY_CAPACITY ，默認(rèn)是64，則會調(diào)用 tryPresize 方法把數(shù)組長度擴(kuò)大到原來的兩倍，并觸發(fā) transfer 方法，重新調(diào)整節(jié)點的位置。

擴(kuò)容操作

http://www.itdecent.cn/p/487d00afe6ca

整個擴(kuò)容操作分為兩步：

1. 構(gòu)建一個nextTable，其大小為原來大小的兩倍，這個步驟是在單線程環(huán)境下完成的。

2. 將原來table里面的內(nèi)容復(fù)制到nextTable中，這個步驟是允許多線程操作的，所以性能得到提升，減少了擴(kuò)容的時間消耗。

并發(fā)擴(kuò)容的具體步驟如下：

1. 為每個內(nèi)核分任務(wù)，并保證其不小于16

2. 檢查nextTable是否為null，如果是，則初始化 nextTable，使其容量為 table 的兩倍。然后死循環(huán)遍歷節(jié)點，直到finished。節(jié)點從 table 復(fù)制到 nextTable 中，支持并發(fā)，思路如下：

3. 如果節(jié)點 f 為 null，則插入 ForwardingNode（采用 Unsafe.compareAndSwapObject 方法實現(xiàn)），這個是觸發(fā)并發(fā)擴(kuò)容的關(guān)鍵

4. 如果 f 為鏈表的頭節(jié)點（fh >= 0）,則先構(gòu)造一個反序鏈表，然后把他們分別放在nextTable的 i 和 i + n位置，并將 ForwardingNode 插入原節(jié)點位置，代表已經(jīng)處理過了

5. 如果 f 為 TreeBin 節(jié)點，同樣也是構(gòu)造一個反序鏈表 ，==同時需要判斷是否需要進(jìn)行 unTreeify() 操作==，并把處理的結(jié)果分別插入到 nextTable 的 i 和 i+n 位置，并插入 ForwardingNode 節(jié)點

6. 所有節(jié)點復(fù)制完成后，則將 table 指向 nextTable，同時更新 sizeCtl = nextTable 的 0.75 倍，完成擴(kuò)容過程。

在多線程環(huán)境下，ConcurrentHashMap 用兩點來保證正確性：ForwardingNode 和 synchronized。當(dāng)一個線程遍歷到的節(jié)點如果是 ForwardingNode，則繼續(xù)往后遍歷，如果不是，則將該節(jié)點加鎖，防止其他線程進(jìn)入，完成后設(shè)置 ForwardingNode 節(jié)點，以便要其他線程可以看到該節(jié)點已經(jīng)處理過了，如此交叉進(jìn)行，高效而又安全。

更多關(guān)于 ConcurrentHashMap 的問題在這里羅列

1. 為什么 ConcurrentHashMap 的 table 大小是 2 的次冪?

   參見擴(kuò)容機(jī)制的描述。

2. ConcurrentHashMap JDK 8 在什么樣的情況下會擴(kuò)容?

   (1) 當(dāng)前容量超過閾值時擴(kuò)容

   (2) 當(dāng)鏈表中元素個數(shù)超過默認(rèn)設(shè)定（8個），當(dāng)數(shù)組的大小還未超過64的時候，此時進(jìn)行數(shù)組的擴(kuò)容，如果超過則將鏈表轉(zhuǎn)化成紅黑樹。

3. ConcurrentHashMap JDK 8 如何實現(xiàn)線程安全?

   使用 CAS + Synchronized 來保證并發(fā)更新的安全。

4. HashMap 的 hash 算法

   參見擴(kuò)容機(jī)制的描述。

5. ConcurrentHashMap 的弱一致性

   (1) 在 JDK 1.6 的時候，一個線程在 ConcurrentHashMap 里 put 元素時寫 count，另一個線程 get 數(shù)據(jù)的時候不會得到最新的實時數(shù)據(jù)。這是因為源碼中 put 操作的寫 new HashEntry 和 get 操作的 getFirst() 存在 happened-before 關(guān)系。具體可以查看筆記。

   (2) 貌似在 JDK 1.7 的時候也存在同樣的問題。

2. HashMap 實現(xiàn)原理

JDK 1.7

HashMap 在 JDK 7 中的數(shù)據(jù)結(jié)構(gòu)是數(shù)組 + 鏈表的實現(xiàn)。 HashMap 中存儲了一個 Entry[] 類型的數(shù)組，里面存儲了 Entry 對象。Entry 對象的結(jié)構(gòu)如下：

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
}

put

1. 當(dāng)調(diào)用 put 方法的時候，會根據(jù) key 的 hash 值定位到 key 要存到 table 的哪個 index 上

2. 如果 key 為 null，那么就 put 到鏈表的頭結(jié)點上。

3. 如果 key 不為 null，那么遍歷 index 上的鏈表，如果存在相同的 key，那么就更新 value。

4. 如果不存在相同的 key，那么將 key 存到鏈表的頭結(jié)點中。

get

1. 根據(jù) key 的 hash 值計算出 key 在 table 的哪個 index 上。遍歷 index 上的鏈表，找到相同的 key，并返回 value。

2. 如果 key 不存在則返回 null。

擴(kuò)容

什么時候擴(kuò)容?

當(dāng) HashMap 內(nèi)的容量數(shù)超過了閾值（默認(rèn) 12 個）的時候會觸發(fā)擴(kuò)容。整個擴(kuò)容過程如下：

1. 新建一個比原來數(shù)組兩倍大的新數(shù)組。

2. 重算 key 的 hash 值來得到在新數(shù)組的位置，并將 key 放入新數(shù)組中。

死循環(huán)問題

主要是多線程同時put時，如果同時觸發(fā)了rehash操作，會導(dǎo)致HashMap中的鏈表中出現(xiàn)循環(huán)節(jié)點，進(jìn)而使得后面get的時候，會死循環(huán)。而且還會丟失元素。

主要重現(xiàn)過程可以看： http://blog.csdn.net/xuefeng0707/article/details/40797085

JDK 1.8

在 JDK 1.8 中， HashMap 重新設(shè)計了實現(xiàn)。放棄 1.7 中的數(shù)組 + 鏈表的存儲結(jié)構(gòu)，改為了數(shù)組 + 鏈表 + 紅黑樹的實現(xiàn)。

put

1. 根據(jù) key 的 hash 值，計算出 table 中的 index。

2. 如果 index 上沒有元素，那么直接插入元素。

3. 如果 index 上有元素的話，并且是鏈表結(jié)構(gòu)的話，就遍歷鏈表，判斷是否有相同的 key 存在，如果存在則替換 value，如果不存在則新建 Node ==放入鏈表尾部==。同時判斷當(dāng)前鏈表是否過長，如果超過 TREEIFY_THRESHOLD 的話，則需要將鏈表轉(zhuǎn)換成紅黑樹。

4. 如果 index 上的節(jié)點是 TreeNode 類型的話，則用紅黑樹的方式添加元素。

5. 最后判斷 HashMap 中的元素是否超過了閾值，如果超過了需要進(jìn)行 resize 擴(kuò)容。

get

1. 根據(jù) key 的 hash 值定位到 table 中的 index。

2. 如果 index 上沒有元素，則返回 null。

3. 如果 index 上有元素，那么根據(jù)節(jié)點類型的不同，調(diào)用鏈表或紅黑樹的方式獲取 value。

擴(kuò)容

在 JDK 1.8 的實現(xiàn)中，優(yōu)化了高位運算的算法，通過 hashCode() 的高 16 位異或低 16 位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質(zhì)量來考慮的，這么做可以在數(shù)組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷。

經(jīng)過觀測可以發(fā)現(xiàn)，我們使用的是2次冪的擴(kuò)展(指長度擴(kuò)為原來2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動2次冪的位置?？聪聢D可以明白這句話的意思，n為table的長度，圖（a）表示擴(kuò)容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴(kuò)容后key1和key2兩種key確定索引位置的示例，其中hash1是key1對應(yīng)的哈希與高位運算結(jié)果。

image

元素在重新計算hash之后，因為n變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化：

image

因此，我們在擴(kuò)充HashMap的時候，不需要像JDK1.7的實現(xiàn)那樣重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴(kuò)充為32的resize示意圖

image

有一點注意區(qū)別，JDK1.7中rehash的時候，舊鏈表遷移新鏈表的時候，如果在新表的數(shù)組索引位置相同，則鏈表元素會倒置，但是從上圖可以看出，JDK1.8不會倒置。

紅黑樹轉(zhuǎn)換

如果鏈表上的元素大于 8 個，那么需要轉(zhuǎn)換成紅黑樹。不過在結(jié)構(gòu)轉(zhuǎn)換之前，會對數(shù)組長度進(jìn)行判斷。如果數(shù)組長度n小于閾值 MIN_TREEIFY_CAPACITY ，默認(rèn)是64，則會調(diào)用 tryPresize 方法把數(shù)組長度擴(kuò)大到原來的兩倍，并觸發(fā) transfer 方法，重新調(diào)整節(jié)點的位置。

二、多線程