Java 容器源码分析之ConcurrentHashMap（2）

look_w

JDK1.8分析1.8的实现已经抛弃了Segment分段锁机制，利用CAS+Synchronized来保证并发更新的安全，底层依然采用数组+链表+红黑树的存储结构。

Paste_Image.png

重要概念在开始之前，有些重要的概念需要介绍一下：

• table：默认为null，初始化发生在第一次插入操作，默认大小为16的数组，用来存储Node节点数据，扩容时大小总是2的幂次方。
• nextTable：默认为null，扩容时新生成的数组，其大小为原数组的两倍。
• sizeCtl ：默认为0，用来控制table的初始化和扩容操作，具体应用在后续会体现出来。
  • -1 代表table正在初始化
  • -N 表示有N-1个线程正在进行扩容操作
  • 其余情况：
    1、如果table未初始化，表示table需要初始化的大小。
    2、如果table初始化完成，表示table的容量，默认是table大小的0.75倍，居然用这个公式算0.75（n - (n >>> 2)）。
• Node：保存key，value及key的hash值的数据结构。class Node<K,V> implements Map.Entry<K,V> {  final int hash;  final K key;  volatile V val;  volatile Node<K,V> next;  ... 省略部分代码}其中value和next都用volatile修饰，保证并发的可见性。
• ForwardingNode：一个特殊的Node节点，hash值为-1，其中存储nextTable的引用。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;  }}只有table发生扩容的时候，ForwardingNode才会发挥作用，作为一个占位符放在table中表示当前节点为null或则已经被移动。

实例初始化实例化ConcurrentHashMap时带参数时，会根据参数调整table的大小，假设参数为100，最终会调整成256，确保table的大小总是2的幂次方，算法如下：
ConcurrentHashMap<String, String> hashMap = new ConcurrentHashMap<>(100);private static final int tableSizeFor(int c) {    int n = c - 1;    n |= n >>> 1;    n |= n >>> 2;    n |= n >>> 4;    n |= n >>> 8;    n |= n >>> 16;    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}注意，ConcurrentHashMap在构造函数中只会初始化sizeCtl值，并不会直接初始化table，而是延缓到第一次put操作。
table初始化前面已经提到过，table初始化操作会延缓到第一次put行为。但是put是可以并发执行的，Doug Lea是如何实现table只初始化一次的？让我们来看看源码的实现。
private final Node<K,V>[] initTable() {    Node<K,V>[] tab; int sc;    while ((tab = table) == null || tab.length == 0) {//如果一个线程发现sizeCtl<0，意味着另外的线程执行CAS操作成功，当前线程只需要让出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) {                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;                    @SuppressWarnings("unchecked")                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];                    table = tab = nt;                    sc = n - (n >>> 2);                }            } finally {                sizeCtl = sc;            }            break;        }    }    return tab;}sizeCtl默认为0，如果ConcurrentHashMap实例化时有传参数，sizeCtl会是一个2的幂次方的值。所以执行第一次put操作的线程会执行Unsafe.compareAndSwapInt方法修改sizeCtl为-1，有且只有一个线程能够修改成功，其它线程通过Thread.yield()让出CPU时间片等待table初始化完成。