摘要：如下代碼省略相關代碼省略相關代碼可以看到在里面，是直接采用數組鏈表紅黑樹來實現，時間復雜度在和之間，如果鏈表轉化為紅黑樹了，那么就是到。

在JDK1.8里面，ConcurrentHashMap在put方法里面已經將分段鎖移除了，轉而是CAS鎖和synchronized

ConcurrentHashMap是Java里面同時兼顧性能和線程安全的一個鍵值對集合，同屬于鍵值對的集合還有HashTable以及HashMap，
HashTable是一個線程安全的類，因為它的所有public方法都被synchronized修飾，這樣就導致了一個問題，就是效率太低。

雖然HashMap在JDK1.8的并發場景下觸發擴容時不會出現成環了，但是會出現數據丟失的情況。
所以如果需要在多線程的情況下(多讀少寫))使用Map集合的話，ConcurrentHashMap是一個不錯的選擇。

ConcurrentHashMap在JDK1.8的時候將put()方法中的分段鎖Segment移除，轉而采用一種CAS鎖和synchronized來實現插入方法的線程安全。
如下代碼：

/** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
       //省略相關代碼
        for (Node[] tab = table;;) {
            Node f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                if (casTabAt(tab, i, null,
                             new Node(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                V oldVal = null;
                synchronized (f) {
                    //省略相關代碼
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

可以看到在JDK1.8里面，ConcurrentHashMap是直接采用數組+鏈表+紅黑樹來實現，時間復雜度在O(1)和O(n)之間，如果鏈表轉化為紅黑樹了，那么就是O(1)到O(nlogn)。
在這里值得一提的是，ConcurrentHashMap會判斷tabAt(tab, i = (n - 1) & hash)是不是 null，是的話就直接采用CAS進行插入，而如果不為空的話，則是synchronized鎖住當前Node的首節點，這是因為當該Node不為空的時候，證明了此時出現了Hash碰撞，就會涉及到鏈表的尾節點新增或者紅黑樹的節點新增以及紅黑樹的平衡，這些操作自然都是非原子性的。

從而導致無法使用CAS，當Node的當前下標為null的時候，由于只是涉及數組的新增，所以用CAS即可。

因為CAS是一種基于版本控制的方式來實現，而碰撞之后的操作太多，所以直接用synchronized比較合適。

當一個集合在迭代的時候如果動態的添加或者刪除元素，那么就會拋出Concurrentmodificationexception，但是在ConcurrentHashMap里面卻不會，例如如下代碼:

public static void main(String[] args) {
    Map map = new ConcurrentHashMap();
    map.put("a","a1");
    map.put("b","b1");
    map.put("c","c1");
    map.put("d","d1");
    map.put("e","e1");
    Iterator iterator = map.keySet().iterator();
    while (iterator.hasNext()){
        String it = iterator.next();
        if("b".equals(it)){
            map.remove("d");
        }
        System.out.println(it);
    }
}

控制臺打印如下：
a
b
c
e

而當你把ConcurrentHashMap換成HashMap的時候，控制臺就會拋出一個異常:

Exception in thread "main" a
b
java.util.ConcurrentModificationException
    at java.util.HashMap$HashIterator.nextNode(HashMap.java:1442)
    at java.util.HashMap$KeyIterator.next(HashMap.java:1466)
    at xyz.somersames.ListTest.main(ListTest.java:22)

原因在于ConcurrentHashMap的next方法并不會去檢查modCount和expectedModCount，但是會檢查下一個節點是不是為空

  if ((p = next) == null)
    throw new NoSuchElementException();

當我們進行remove的時候，ConcurrentHashMap會直接通過修改指針的方式來進行移除操作，同樣的，也會鎖住數組的頭節點直至移除結束，所以在同一個時刻，只會有一個線程對當前數組下標的所有節點進行操作。

但是在HashMap里面，next方法會進行一個check，而remove操作會修改modCount，導致modCount和expectedModCount不相等，所以就會導致
ConcurrentModificationException

稍微修改下代碼:

public static void main(String[] args) {
    Map map = new ConcurrentHashMap();
    map.put("a","a1");
    map.put("b","b1");
    map.put("c","c1");
    map.put("d","d1");
    map.put("e","e1");
    Iterator iterator = map.keySet().iterator();
    while (iterator.hasNext()){
        if("b".equals(iterator.next())){
            map.remove("d");
        }
        System.out.println(iterator.next());
    }
}
控制臺打印如下:
b
d
Exception in thread "main" java.util.NoSuchElementException
    at java.util.concurrent.ConcurrentHashMap$KeyIterator.next(ConcurrentHashMap.java:3416)
    at com.xzh.ssmtest.ListTest.main(ListTest.java:25)

由于每一個Node的首節點都會被synchronized修飾，從而將一個元素的新增轉化為一個原子操作，同時Node的value和next都是由volatile關鍵字進行修飾，從而可以保證可見性。