JDK1.8下ConcurrentHashMap的一些理解(一)

摘要：如下代码省略相关代码省略相关代码可以看到在里面，是直接采用数组链表红黑树来实现，时间复杂度在和之间，如果链表转化为红黑树了，那么就是到。

在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关键字进行修饰，从而可以保证可见性。