ConcurrentHashMap源码深度解析（一）（java8）——不可不知的基本概念（助你拿下源码事半功倍）

public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
    implements ConcurrentMap<K,V>, Serializable {
    private static final long serialVersionUID = 7249069246763182397L;

    /* ---------------- Constants -------------- */

    /**
     * The largest possible table capacity.  This value must be
     * exactly 1<<30 to stay within Java array allocation and indexing
     * bounds for power of two table sizes, and is further required
     * because the top two bits of 32bit hash fields are used for
     * control purposes.
     */
    // 1 * 2^30 = 1073741824
    // 最大容量
    private static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The default initial table capacity.  Must be a power of 2
     * (i.e., at least 1) and at most MAXIMUM_CAPACITY.
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 16;

    /**
     * The default concurrency level for this table. Unused but
     * defined for compatibility with previous versions of this class.
     * 默认并发级别，为了兼容旧版本，java8没有用上
     */
    private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

    /**
     * The load factor for this table. Overrides of this value in
     * constructors affect only the initial table capacity.  The
     * actual floating point value isn't normally used -- it is
     * simpler to use expressions such as {@code n - (n >>> 2)} for
     * the associated resizing threshold.
     * 默认扩容因子，但是用不上。
     */
    private static final float LOAD_FACTOR = 0.75f;

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2, and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     * 链表转为红黑树的阈值，>= TREEIFY_THRESHOLD链表可能转为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * The bin count threshold for untreeifying a (split) bin during a
     * resize operation. Should be less than TREEIFY_THRESHOLD, and at
     * most 6 to mesh with shrinkage detection under removal.
     * 红黑树转为链表的阈值， <= UNTREEIFY_THRESHOLD 时红黑树转为链表，只作用于扩容阶段
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 容量在64以内，即使达到链表转红黑树的阈值也不转换，而是扩容
     * The smallest table capacity for which bins may be treeified.
     * (Otherwise the table is resized if too many nodes in a bin.)
     * The value should be at least 4 * TREEIFY_THRESHOLD to avoid
     * conflicts between resizing and treeification thresholds.
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    /**
     * Minimum number of rebinnings per transfer step. Ranges are
     * subdivided to allow multiple resizer threads.  This value
     * serves as a lower bound to avoid resizers encountering
     * excessive memory contention.  The value should be at least
     * DEFAULT_CAPACITY.
     * 扩容时，给线程分配迁移数组元素任务时的最小步长
     */
    private static final int MIN_TRANSFER_STRIDE = 16;

    /**
     * The number of bits used for generation stamp in sizeCtl.
     * Must be at least 6 for 32bit arrays.
     * 扩容时，在sizeCtl中用于生成戳记的数值
     */
    private static int RESIZE_STAMP_BITS = 16;

    /**
     * The maximum number of threads that can help resize.
     * Must fit in 32 - RESIZE_STAMP_BITS bits.
     * 帮助扩容的最大线程数
     */
    private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;

    /**
     * The bit shift for recording size stamp in sizeCtl.
     * 在sizeCtl中用于生成记录扩容线程个数的戳记的移位数
     */
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

    // MOVED=-1 代表数组正在扩容，forwarding nodes的hash=-1
    // hash for forwarding nodes
    static final int MOVED     = -1;
    // 用于标记 红黑树根节点的hash
    static final int TREEBIN   = -2; // hash for roots of trees
    // 在computeIfAbsent and compute中用到可以先不用管
    static final int RESERVED  = -3; // hash for transient reservations
    // 正常hash值的可用位,在spread中用于保证计算的hash值不超过HASH_BITS
    // 2147483647
    // 1111 1111 1111 1111 1111 1111 1111 111
    static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

/* ---------------- Fields -------------- */

/**
 * The array of bins. Lazily initialized upon first insertion.
 * Size is always a power of two. Accessed directly by iterators.
 * 当前数组
 */
transient volatile Node<K,V>[] table;

/**
 * 扩容后的新数组，只有在数组扩容时不为null。
 * The next table to use; non-null only while resizing.
 */
private transient volatile Node<K,V>[] nextTable;

/**
 * Base counter value, used mainly when there is no contention,
 * but also as a fallback during table initialization
 * races. Updated via CAS.
 * 数组元素基础计数
 */
private transient volatile long baseCount;

/**
 * Table initialization and resizing control.  When negative, the
 * table is being initialized or resized: -1 for initialization,
 * else -(1 + the number of active resizing threads).  Otherwise,
 * when table is null, holds the initial table size to use upon
 * creation, or 0 for default. After initialization, holds the
 * next element count value upon which to resize the table.
 * sizeCtl很重要，不同的值在数组不同状态中起着举足轻重的作用。
 */
private transient volatile int sizeCtl;

/**
 * transferIndex记录了扩容的进度。
 * The next table index (plus one) to split while resizing.
 */
private transient volatile int transferIndex;

/**
 * 简易自旋锁，用于控制多线程统计数组元素的
 * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
 */
private transient volatile int cellsBusy;

/**
 * Table of counter cells. When non-null, size is a power of 2.
 * 当cas修改baseCount失败后的线程会去修改对应counterCells数组中一个计数格子。
 * 所以 想获取数组内元素的总个数就是baseCount+counterCells数组内所有计数格记录值之和。
 */
private transient volatile CounterCell[] counterCells;

public ConcurrentHashMap(int initialCapacity,
                         float loadFactor, int concurrencyLevel) {
    if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    // concurrencyLevel的用处不大，为了兼容java7版本
    if (initialCapacity < concurrencyLevel)   // Use at least as many bins
        initialCapacity = concurrencyLevel;   // as estimated threads
    // initialCapacity和loadFactor都是使用者外部传入，所以可对initialCapacity进行优化
    long size = (long)(1.0 + (long)initialCapacity / loadFactor);
    // 获取一个大于等于且离size最近的2的整数次方的数
    int cap = (size >= (long)MAXIMUM_CAPACITY) ?
        MAXIMUM_CAPACITY : tableSizeFor((int)size);
    // 此时sizeCtl存的是初始容量
    this.sizeCtl = cap;
}

public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    // 1.5倍的初始容量+1，再往上取最接近的2的整数次方
    // 初始化时只是设置了初始值，并没有初始化数组，懒加载，put时在初始化数组
    this.sizeCtl = cap;
}

/**
 * 找到大于等于c的最近2的整数次的数
 * @param c
 * @return
 */
private static final int tableSizeFor(int c) {
    // 为什么要减1呢?
    int n = c - 1;
    // 向右移1位，与旧值|，逻辑上可得到2个1
    n |= n >>> 1;
    // 向右移2位，与旧值|，逻辑上可得到4个1
    n |= n >>> 2;
    // 向右移4位，与旧值|，逻辑上可得到8个1
    n |= n >>> 4;
    // 向右移8位，与旧值|，逻辑上可得到16个1
    n |= n >>> 8;
    // 向右移16位，与旧值|，逻辑上可得到32个1
    n |= n >>> 16;
    // n+1 得到大于等于c的最近2的整数次的数
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    ... ...
    /**
     * Virtualized support for map.get(); overridden in subclasses.
     * 遍历链表 寻找哈希和key都相同的节点
     */
    Node<K,V> find(int h, Object k) {
        Node<K,V> e = this;
        if (k != null) {
            do {
                K ek;
                if (e.hash == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
            } while ((e = e.next) != null);
        }
        return null;
    }
}

static final class TreeBin<K,V> extends Node<K,V> {
    // 红黑树根节点
    TreeNode<K,V> root;
    // 红黑树按链表遍历的第一个节点
    volatile TreeNode<K,V> first;
    // 阻塞等待的线程
    volatile Thread waiter;
    // 锁的状态
    volatile int lockState;
    // values for lockState
    // 二进制低位第一位用来标识写线程持有锁的状态 （不可重入锁）
    static final int WRITER = 1; // set while holding write lock
    // 二进制低位第二位用来标识阻塞状态
    static final int WAITER = 2; // set when waiting for write lock
    // 二进制低位第三位之后都是用来标识读线程持有锁的状态
    static final int READER = 4; // increment value for setting read lock

    /**
     * Creates bin with initial set of nodes headed by b.
     *
     *  hash=TREEBIN < 0 && f instanceof TreeBin 可判断是红黑树
     */
    TreeBin(TreeNode<K,V> b) {
        super(TREEBIN, null, null, null);
        this.first = b;
        ... ...
    }

    /**
     * Acquires write lock for tree restructuring.
     */
    private final void lockRoot() {
        if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
            // 获取写锁失败，则竞争加锁，可能会阻塞
            contendedLock(); // offload to separate method
    }

    /**
     * Releases write lock for tree restructuring.
     */
    private final void unlockRoot() {
        lockState = 0;
    }

    /**
     * Possibly blocks awaiting root lock.
     */
    private final void contendedLock() {
        boolean waiting = false;
        for (int s;;) {
            // ~WAITER = - (WAITER + 1)  11111111111111111111111111111101
            if (((s = lockState) & ~WAITER) == 0) {
                // 没有线程还有锁，lockState=0 or 2，则获取写锁
                if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
                    if (waiting)
                        waiter = null;
                    return;
                }
            }
            // != 0, s有可能=1 or 4，8,12... 即有线程持有写锁or读锁，则当前线程需要阻塞
            else if ((s & WAITER) == 0) {
                if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
                    waiting = true;
                    waiter = Thread.currentThread();
                }
            }
            else if (waiting)
                LockSupport.park(this);
        }
    }

    /**
     * Returns matching node or null if none. Tries to search
     * using tree comparisons from root, but continues linear
     * search when lock not available.
     */
    final Node<K,V> find(int h, Object k) {
        if (k != null) {
            for (Node<K,V> e = first; e != null; ) {
                int s; K ek;
                // 二进制的低位1位是标识写锁，2位标识阻塞
                if (((s = lockState) & (WAITER|WRITER)) != 0) {
                    // 可能有线程持有写锁or阻塞，说明正在做平衡算法，不能使用红黑树来遍历节点
                    // 但是可以像普通链表一样遍历节点
                    if (e.hash == h &&
                        ((ek = e.key) == k || (ek != null && k.equals(ek))))
                        return e;
                    e = e.next;
                }
                // == 0 说明没有线程持有写锁和阻塞，则可获取读锁
                // 读线程间是不互斥的，所以读线程累加READER
                else if (U.compareAndSwapInt(this, LOCKSTATE, s,
                                             s + READER)) {

                    TreeNode<K,V> r, p;
                    try {
                        // 遍历红黑树
                        p = ((r = root) == null ? null :
                             r.findTreeNode(h, k, null));
                    } finally {
                        Thread w;
                        // 释放读锁，-READER，释放锁的同时，若有线程在阻塞则唤醒他（一般就是写线程在等待）
                        // 这里会有不必要的唤醒，因为若不是最后一个读线程释放锁唤醒阻塞的写线程的话，
                        // 此时还有读线程持有锁，则写线程继续阻塞。
                        if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
                            (READER|WAITER) && (w = waiter) != null)
                            LockSupport.unpark(w);
                    }
                    return p;
                }
            }
        }
        return null;
    }

    /**
     * 返回值是已经存在的节点，所以可以根据返回值判断是替换还是新增
     * Finds or adds a node.
     * @return null if added
     */
    final TreeNode<K,V> putTreeVal(int h, K k, V v) {
        Class<?> kc = null;
        ... ...
    }

    /**
     * 返回值 true为当前树比较小，需要退化为链表
     * @return true if now too small, so should be untreeified
     */
    final boolean removeTreeNode(TreeNode<K,V> p) {
        ... ...
    }

    /* ------------------------------------------------------------ */
    // Red-black tree methods, all adapted from CLR
    /**
     * 平衡算法过程中的左旋
     */
    static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                          TreeNode<K,V> p) {
        ... ...
    }
    /**
     * 平衡算法过程中的右旋
     */
    static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                           TreeNode<K,V> p) {
        ... ...
    }

    /**
     * 插入平衡算法，每插入一个节点就要维护红黑树的结构特性，而这个过程是需要上锁的
     * @param root
     * @param x
     * @param <K>
     * @param <V>
     * @return
     */
    static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                TreeNode<K,V> x) {
        ... ...
    }

    static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                               TreeNode<K,V> x) {
      ... ...
    }
}

/**
 * 红黑树中保存key-value的节点
 * Nodes for use in TreeBins
 */
static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;

    TreeNode(int hash, K key, V val, Node<K,V> next,
             TreeNode<K,V> parent) {
        super(hash, key, val, next);
        this.parent = parent;
    }

    Node<K,V> find(int h, Object k) {
        return findTreeNode(h, k, null);
    }

    /**
     * Returns the TreeNode (or null if not found) for the given key
     * starting at given root.
     */
    final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
        // 遍历红黑树，找节点
        ... ...
    }
}

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;
    }
    // 转发到nextTable中继续检索
    Node<K,V> find(int h, Object k) {
        // loop to avoid arbitrarily deep recursion on forwarding nodes
        outer: for (Node<K,V>[] tab = nextTable;;) {
            Node<K,V> e; int n;
            if (k == null || tab == null || (n = tab.length) == 0 ||
                (e = tabAt(tab, (n - 1) & h)) == null)
                // 新数组 映射的槽是空的则返回null
                return null;
            for (;;) {
                int eh; K ek;
                if ((eh = e.hash) == h &&
                    ((ek = e.key) == k || (ek != null && k.equals(ek))))
                    return e;
                if (eh < 0) {
                    if (e instanceof ForwardingNode) {
                        tab = ((ForwardingNode<K,V>)e).nextTable;
                        // 又遇到另一个转发节点，跳过一次外围循环，从新的tab检索，
                        // 不会在扩容阶段又在新数组上扩容把？有待后续验证
                        continue outer;
                    }
                    else
                        // 这里就是红黑树了，去树上找
                        return e.find(h, k);
                }
                if ((e = e.next) == null)
                    // 到最后了还没找到则返回null
                    return null;
            }
        }
    }
}

int h = spread(key.hashCode());

static final int spread(int h) {
    // 高低位扰动
    return (h ^ (h >>> 16)) & HASH_BITS;
}