ConCurrentHashMap原始碼分析，面試常問

都說ConCurrentHashMap是執行緒安全，但又比HashTable效率高，底層實作原理是什么？常用的HashMap為什么執行緒不安全？

HashMap底層是陣列+鏈表結構，既然有陣列，那肯定會涉及到容量不足需要擴容的場景
或是極限情況下的元素覆寫問題，

上圖假如此時有兩個執行緒都通過了if判斷，又恰好他們put元素的哈希值一樣此時就會出現元素的覆寫， 其他HashMap詳細資料，，，，
?
?
?
?

下面主要介紹ConCurrentHashMap實作執行緒安全方式（原始碼分析）

原始碼中幾個比較重要的屬性介紹

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

transient關鍵字說明此屬性不會加入物件序列化，table代表整個哈希表，

private transient volatile Node<K,V>[] nextTable;

這是一個連接表，用于哈希表擴容，擴容完成后會被重置為 null，

private transient volatile long baseCount;

該屬性保存著整個哈希表中存盤的所有的結點的個數總和，有點類似于 HashMap 的 size 屬性，

private transient volatile int sizeCtl;

這是一個重要的屬性，無論是初始化哈希表，還是擴容 rehash 的程序，都是需要依賴這個關鍵屬性的，該屬性有以下幾種取值：

0：默認值
-1：代表哈希表正在進行初始化
大于0：相當于 HashMap 中的 threshold，表示閾值
小于-1：代表有多個執行緒正在進行擴容
該屬性的使用還是有點復雜的，在我們分析擴容原始碼的時候再給予更加詳盡的描述，此處了解其可取的幾個值都分別代表著什么樣的含義即可，

?
?
?
?
?
下面先關注put方法：
?
putVal 的方法比較多，我們分兩個部分進行分析，

//第一部分
final V putVal(K key, V value, boolean onlyIfAbsent) {
    //對傳入的引數進行合法性判斷
    if (key == null || value == null) throw new NullPointerException();
    //計算鍵所對應的 hash 值
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        //如果哈希表還未初始化，那么初始化它
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        //根據鍵的 hash 值找到哈希陣列相應的索引位置
        //如果為空，那么以CAS無鎖式向該位置添加一個節點
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   
        }

其中initTable()方法在下面展開說明，這是一個初始化哈希表的操作，它同時只允許一個執行緒進行初始化操作，

private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    //如果表為空才進行初始化操作
    while ((tab = table) == null || tab.length == 0) {
        //sizeCtl 小于零說明已經有執行緒正在進行初始化操作
        //當前執行緒應該放棄 CPU 的使用
        if ((sc = sizeCtl) < 0)
            Thread.yield(); // lost initialization race; just spin
        //否則說明還未有執行緒對表進行初始化，那么本執行緒就來做這個作業
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            //保險起見，再次判斷下表是否為空
            try {
                if ((tab = table) == null || tab.length == 0) {
                    //sc 大于零說明容量已經初始化了，否則使用默認容量
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    //根據容量構建陣列
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    //計算閾值，等效于 n*0.75
                    sc = n - (n >>> 2);
                }
            } finally {
                //設定閾值
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

關于 initTable 方法的每一步實作都已經給出注釋，該方法的核心思想就是，只允許一個執行緒對表進行初始化，
如果不巧有其他執行緒進來了，那么會讓其他執行緒交出 CPU 等待下次系統調度，這樣，保證了表同時只會被一個執行緒初始化，

接著，我們回到 putVal 方法，這樣的話，我們第一部分的 putVal 原始碼就分析結束了，下面我們看后一部分的原始碼：

//檢測到桶結點是 ForwardingNode 型別，協助擴容
else if ((fh = f.hash) == MOVED)
     tab = helpTransfer(tab, f);
//桶結點是普通的結點，鎖住該桶頭結點并試圖在該鏈表的尾部添加一個節點
else {
       V oldVal = null;
       synchronized (f) {
           if (tabAt(tab, i) == f) {
              //向普通的鏈表中添加元素，無需贅述
              if (fh >= 0) {
                 binCount = 1;
                 for (Node<K,V> e = f;; ++binCount) {
                     K ek;
                     if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {
                         oldVal = e.val;
                         if (!onlyIfAbsent)
                            e.val = value;
                            break;
                      }
                      Node<K,V> pred = e;
                      if ((e = e.next) == null) {
                         pred.next = new Node<K,V>(hash, key,value, null);
                         break;
                      }
                 }
           }
           //向紅黑樹中添加元素，TreeBin 結點的hash值為TREEBIN（-2）
           else if (f instanceof TreeBin) {
               Node<K,V> p;
               binCount = 2;
                 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,                                      value)) != null) {
                   oldVal = p.val;
                   if (!onlyIfAbsent)
                      p.val = value;
                }
           }
       }
   }
  //binCount != 0 說明向鏈表或者紅黑樹中添加或修改一個節點成功
  //binCount  == 0 說明 put 操作將一個新節點添加成為某個桶的首節點
  if (binCount != 0) {
         //鏈表深度超過 8 轉換為紅黑樹
         if (binCount >= TREEIFY_THRESHOLD)
             treeifyBin(tab, i);
         //oldVal != null 說明此次操作是修改操作
         //直接回傳舊值即可，無需做下面的擴容邊界檢查
         if (oldVal != null)
             return oldVal;
           break;
        }
    }
}
//CAS 式更新baseCount，并判斷是否需要擴容
addCount(1L, binCount);
//程式走到這一步說明此次 put 操作是一個添加操作，否則早就 return 回傳了
return null;

首先需要介紹一下，ForwardingNode 這個節點型別，

static final class ForwardingNode<K,V> extends Node<K,V> {
        final Node<K,V>[] nextTable;
        ForwardingNode(Node<K,V>[] tab) {
            //注意這里
            super(MOVED, null, null, null);
            this.nextTable = tab;
        }
    //省略其 find 方法
}

這個節點內部保存了一 nextTable 參考，它指向一張 hash 表，在擴容操作中，我們需要對每個桶中的結點進行分離和轉移，如果某個桶結點中所有節點都已經遷移完成了（已經被轉移到新表 nextTable 中了），那么會在原 table 表的該位置掛上一個 ForwardingNode 結點，說明此桶已經完成遷移，

ForwardingNode 繼承自 Node 結點，并且它唯一的建構式將構建一個鍵，值，next 都為 null 的結點，反正它就是個標識，無需那些屬性，但是 hash 值卻為 MOVED，

所以，我們在 putVal 方法中遍歷整個 hash 表的桶結點，如果遇到 hash 值等于 MOVED，說明已經有執行緒正在擴容 rehash 操作，整體上還未完成，不過我們要插入的桶的位置已經完成了所有節點的遷移，

由于檢測到當前哈希表正在擴容，于是讓當前執行緒去協助擴容，