一、集合

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

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

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)用戶(hù)調(diào)用 put 方法的時(shí)候诅愚，首先根據(jù) key 的 hash 值找到具體的 Segment 在 table 中的位置。

3. 如果這個(gè)位置上的 Segment 沒(méi)有初始化劫映，則進(jìn)行初始化的操作违孝。

4. 最后委托給 Segment 的 put 方法。此方法中會(huì)根據(jù)計(jì)算出的 (tab.length - 1) & hash 的 index 定位到 HashEntry泳赋， 如果這個(gè)位置上的節(jié)點(diǎn)為null雌桑，則新建一個(gè) HashEntry并返回 。如果不為 null祖今，則遍歷 HashEntry 的每一個(gè)節(jié)點(diǎn)校坑，如果有相同的 key 存在則更新 value拣技， 如果沒(méi)有則新建一個(gè) HashEntry 放入鏈表頭部的位置。

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

get 操作

get 操作的時(shí)候沒(méi)有對(duì) ConcurrentHashMap 進(jìn)行上鎖邪驮，

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

2. 然后遍歷 HashEntry 的所有節(jié)點(diǎn)，如果找到 key耕捞，那么就返回對(duì)應(yīng)的 value衔掸，如果 key 沒(méi)有找到，就返回 null俺抽。

remove 操作

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

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

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

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

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

整個(gè)步驟如下：

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

這里的重點(diǎn)就是：

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

JDK 1.8

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

一些重要的變量

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

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

/**
 *  自旋鎖 （鎖定通過(guò) CAS） 在調(diào)整大小和/或創(chuàng)建 CounterCells 時(shí)使用壹粟。 在CounterCell類(lèi)更新value中會(huì)使用，功能類(lèi)似顯示鎖和內(nèi)置鎖宿百，性能更好
 *  在Striped64類(lèi)也有應(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)識(shí)符趁仙，用來(lái)控制table初始化和擴(kuò)容操作的，在不同的地方有不同的用途垦页，其值也不同雀费，所代表的含義也不同

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

• -1代表正在初始化

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

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

put 操作

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

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

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

4. 如果當(dāng)前節(jié)點(diǎn)的 hash 值為 -1，說(shuō)明當(dāng)前的節(jié)點(diǎn)是 forwardingNode 節(jié)點(diǎn)到逊，表示 table 正在擴(kuò)容铣口，當(dāng)前線(xiàn)程需要幫助一起擴(kuò)容。（上面的過(guò)程走完之后蕾管，說(shuō)明當(dāng)前的節(jié)點(diǎn)上有元素枷踏，需要對(duì)當(dāng)前節(jié)點(diǎn)加鎖然后操作）。

5. 如果當(dāng)前節(jié)點(diǎn)的 hash 值大于等于 0掰曾，說(shuō)明是一個(gè)鏈表結(jié)構(gòu)旭蠕，則遍歷鏈表，如果存在當(dāng)前 key 節(jié)點(diǎn)則替換 value旷坦，否則插入到鏈表尾部掏熬。

6. 如果 f 是 TreeBin 類(lèi)型節(jié)點(diǎn)，則按照紅黑樹(shù)的方法更新或者增加節(jié)點(diǎn)秒梅。

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

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

get 操作

get 操作的時(shí)候沒(méi)有上鎖，如果整個(gè)table 為空呢蔫，則返回null切心，否則根據(jù) key 的 hash 值找到 table 的 index 位置，然后根據(jù)鏈表或者樹(shù)形方式找到相對(duì)應(yīng)的節(jié)點(diǎn)片吊，返回其 value 值绽昏。

remove 操作

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

紅黑樹(shù)轉(zhuǎn)換

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

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

擴(kuò)容操作

http://www.reibang.com/p/487d00afe6ca

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

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

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

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

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

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

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

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

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

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

在多線(xiàn)程環(huán)境下蜂怎，ConcurrentHashMap 用兩點(diǎn)來(lái)保證正確性：ForwardingNode 和 synchronized穆刻。當(dāng)一個(gè)線(xiàn)程遍歷到的節(jié)點(diǎn)如果是 ForwardingNode，則繼續(xù)往后遍歷杠步，如果不是氢伟，則將該節(jié)點(diǎn)加鎖，防止其他線(xiàn)程進(jìn)入幽歼，完成后設(shè)置 ForwardingNode 節(jié)點(diǎn)朵锣，以便要其他線(xiàn)程可以看到該節(jié)點(diǎn)已經(jīng)處理過(guò)了，如此交叉進(jìn)行甸私，高效而又安全诚些。

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

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

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

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

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

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

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

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

4. HashMap 的 hash 算法

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

5. ConcurrentHashMap 的弱一致性

   (1) 在 JDK 1.6 的時(shí)候唬格，一個(gè)線(xiàn)程在 ConcurrentHashMap 里 put 元素時(shí)寫(xiě) count家破，另一個(gè)線(xiàn)程 get 數(shù)據(jù)的時(shí)候不會(huì)得到最新的實(shí)時(shí)數(shù)據(jù)。這是因?yàn)樵创a中 put 操作的寫(xiě) new HashEntry 和 get 操作的 getFirst() 存在 happened-before 關(guān)系购岗。具體可以查看筆記员舵。

   (2) 貌似在 JDK 1.7 的時(shí)候也存在同樣的問(wèn)題。

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

JDK 1.7

HashMap 在 JDK 7 中的數(shù)據(jù)結(jié)構(gòu)是數(shù)組 + 鏈表的實(shí)現(xiàn)藕畔。 HashMap 中存儲(chǔ)了一個(gè) Entry[] 類(lèi)型的數(shù)組马僻，里面存儲(chǔ)了 Entry 對(duì)象。Entry 對(duì)象的結(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 方法的時(shí)候注服，會(huì)根據(jù) key 的 hash 值定位到 key 要存到 table 的哪個(gè) index 上

2. 如果 key 為 null韭邓，那么就 put 到鏈表的頭結(jié)點(diǎn)上措近。

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

4. 如果不存在相同的 key鸭你，那么將 key 存到鏈表的頭結(jié)點(diǎn)中屈张。

get

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

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

擴(kuò)容

什么時(shí)候擴(kuò)容?

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

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

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

死循環(huán)問(wèn)題

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

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

JDK 1.8

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

put

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

2. 如果 index 上沒(méi)有元素，那么直接插入元素譬正。

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

4. 如果 index 上的節(jié)點(diǎn)是 TreeNode 類(lèi)型的話(huà)稚晚，則用紅黑樹(shù)的方式添加元素崇堵。

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

get

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

2. 如果 index 上沒(méi)有元素，則返回 null也搓。

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

擴(kuò)容

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

經(jīng)過(guò)觀測(cè)可以發(fā)現(xiàn)，我們使用的是2次冪的擴(kuò)展(指長(zhǎng)度擴(kuò)為原來(lái)2倍)匾乓，所以捞稿，元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置拼缝∮榫郑看下圖可以明白這句話(huà)的意思，n為table的長(zhǎng)度咧七，圖（a）表示擴(kuò)容前的key1和key2兩種key確定索引位置的示例衰齐，圖（b）表示擴(kuò)容后key1和key2兩種key確定索引位置的示例，其中hash1是key1對(duì)應(yīng)的哈希與高位運(yùn)算結(jié)果继阻。

image

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

image

因此抹缕，我們?cè)跀U(kuò)充HashMap的時(shí)候，不需要像JDK1.7的實(shí)現(xiàn)那樣重新計(jì)算hash墨辛，只需要看看原來(lái)的hash值新增的那個(gè)bit是1還是0就好了卓研，是0的話(huà)索引沒(méi)變，是1的話(huà)索引變成“原索引+oldCap”睹簇，可以看看下圖為16擴(kuò)充為32的resize示意圖

image

有一點(diǎn)注意區(qū)別鉴分，JDK1.7中rehash的時(shí)候哮幢，舊鏈表遷移新鏈表的時(shí)候，如果在新表的數(shù)組索引位置相同志珍，則鏈表元素會(huì)倒置橙垢，但是從上圖可以看出，JDK1.8不會(huì)倒置伦糯。

紅黑樹(shù)轉(zhuǎn)換

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

二监嗜、多線(xiàn)程