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 操作，整体上还未完成，不过我们要插入的桶的位置已经完成了所有节点的迁移。

由于检测到当前哈希表正在扩容，于是让当前线程去协助扩容。