摘要：如下代碼省略相關(guān)代碼省略相關(guān)代碼可以看到在里面，是直接采用數(shù)組鏈表紅黑樹來實(shí)現(xiàn)，時(shí)間復(fù)雜度在和之間，如果鏈表轉(zhuǎn)化為紅黑樹了，那么就是到。

在JDK1.8里面，ConcurrentHashMap在put方法里面已經(jīng)將分段鎖移除了，轉(zhuǎn)而是CAS鎖和synchronized

ConcurrentHashMap是Java里面同時(shí)兼顧性能和線程安全的一個(gè)鍵值對(duì)集合，同屬于鍵值對(duì)的集合還有HashTable以及HashMap，
HashTable是一個(gè)線程安全的類，因?yàn)樗乃?b>public方法都被synchronized修飾，這樣就導(dǎo)致了一個(gè)問題，就是效率太低。

雖然HashMap在JDK1.8的并發(fā)場(chǎng)景下觸發(fā)擴(kuò)容時(shí)不會(huì)出現(xiàn)成環(huán)了，但是會(huì)出現(xiàn)數(shù)據(jù)丟失的情況。
所以如果需要在多線程的情況下(多讀少寫))使用Map集合的話，ConcurrentHashMap是一個(gè)不錯(cuò)的選擇。

ConcurrentHashMap在JDK1.8的時(shí)候?qū)ut()方法中的分段鎖Segment移除，轉(zhuǎn)而采用一種CAS鎖和synchronized來實(shí)現(xiàn)插入方法的線程安全。
如下代碼：

/** Implementation for put and putIfAbsent */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
       //省略相關(guān)代碼
        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) {
                    //省略相關(guān)代碼
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        addCount(1L, binCount);
        return null;
    }

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

從而導(dǎo)致無法使用CAS，當(dāng)Node的當(dāng)前下標(biāo)為null的時(shí)候，由于只是涉及數(shù)組的新增，所以用CAS即可。

因?yàn)镃AS是一種基于版本控制的方式來實(shí)現(xiàn)，而碰撞之后的操作太多，所以直接用synchronized比較合適。

當(dāng)一個(gè)集合在迭代的時(shí)候如果動(dòng)態(tài)的添加或者刪除元素，那么就會(huì)拋出Concurrentmodificationexception，但是在ConcurrentHashMap里面卻不會(huì)，例如如下代碼:

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

控制臺(tái)打印如下：
a
b
c
e

而當(dāng)你把ConcurrentHashMap換成HashMap的時(shí)候，控制臺(tái)就會(huì)拋出一個(gè)異常:

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方法并不會(huì)去檢查modCount和expectedModCount，但是會(huì)檢查下一個(gè)節(jié)點(diǎn)是不是為空

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

當(dāng)我們進(jìn)行remove的時(shí)候，ConcurrentHashMap會(huì)直接通過修改指針的方式來進(jìn)行移除操作，同樣的，也會(huì)鎖住數(shù)組的頭節(jié)點(diǎn)直至移除結(jié)束，所以在同一個(gè)時(shí)刻，只會(huì)有一個(gè)線程對(duì)當(dāng)前數(shù)組下標(biāo)的所有節(jié)點(diǎn)進(jìn)行操作。

但是在HashMap里面，next方法會(huì)進(jìn)行一個(gè)check，而remove操作會(huì)修改modCount，導(dǎo)致modCount和expectedModCount不相等，所以就會(huì)導(dǎo)致
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());
    }
}
控制臺(tái)打印如下:
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)

由于每一個(gè)Node的首節(jié)點(diǎn)都會(huì)被synchronized修飾，從而將一個(gè)元素的新增轉(zhuǎn)化為一個(gè)原子操作，同時(shí)Node的value和next都是由volatile關(guān)鍵字進(jìn)行修飾，從而可以保證可見性。