ConcurrentHashMap JDK 1.8 源码分析（自用）

如果有不对的地方还请大家指点，一起学习一起进步

线程安全的 HashMap

HashMap 是根据散列表来设计的，有着很快的存取速度，但是它存在着线程安全的问题。所以出现个一个新的线程安全的散列表集合：ConcurrentHashMap

ConcurrentHashMap 的底层数据结构为数据+链表+红黑树，并发控制使用 Synchronized 和 CAS 来操作

1、字段属性介绍

关键常量解释：

/**
     * 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.
     * 最大容量
     */
    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 largest possible (non-power of two) array size.
     * Needed by toArray and related methods.
     * toArray 方法生成数组的最大长度
     */
    static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * The default concurrency level for this table. Unused but
     * defined for compatibility with previous versions of this class.
     * 1.7 遗留下来的（表示并发级别），1.8 只在初始化时有用到（并不代表并发级别）
     */
    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.
     * 链表树化阈值
     */
    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.
     * 红黑树退化链表阈值
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
     * 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.
     * 扩容时一个线程被分配的最小任务步长 (分配最少完成 16 个桶位 (连续) 的数据迁移)
     */
    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.
     * 用于生成扩容的唯一标识戳 (用于识别线程是否为当前扩容工作, 同一次扩容的线程的标识戳都相等)
     */
    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.
     * 表示戳左移 RESIZE_STAMP_SHIFT 位 + (1 + 线程数) = sizeCtl
     */
    private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

    /*
     * Encodings for Node hash fields. See above for explanation.
     */
    // -1 表示该节点为 FWD (集合正在扩容, 该桶位的数据已迁移到新数组) 节点
    static final int MOVED     = -1; // hash for forwarding nodes（FWD 节点）
    // -2 表示树化节点
    static final int TREEBIN   = -2; // hash for roots of trees（树化节点）
    static final int RESERVED  = -3; // hash for transient reservations
    // 节点 hash 值的有效位数
    static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

    /** Number of CPUS, to place bounds on some sizings */
    // cpu 数量
    static final int NCPU = Runtime.getRuntime().availableProcessors();

    /** For serialization compatibility. */
    // 为兼容 1.7 而保留的
    private static final ObjectStreamField[] serialPersistentFields = {
        new ObjectStreamField("segments", Segment[].class),
        new ObjectStreamField("segmentMask", Integer.TYPE),
        new ObjectStreamField("segmentShift", Integer.TYPE)
    };







    // Unsafe mechanics
    private static final sun.misc.Unsafe U;
    /** 表示 sizeCtl 属性在 ConcurrentHashMap 在内存中的偏移地址 */
    private static final long SIZECTL;
    /** 表示 transferIndex 属性在 ConcurrentHashMap 在内存中的偏移地址 */
    private static final long TRANSFERINDEX;
    /** 表示 transferIndex 属性在 ConcurrentHashMap 在内存中的偏移地址 */
    private static final long BASECOUNT;
    /** 表示 cellBusy 属性在 ConcurrentHashMap 在内存中的偏移地址 */
    private static final long CELLSBUSY;
    /** 表示 cellValue 属性在 ConcurrentHashMap 在内存中的偏移地址 */
    private static final long CELLVALUE;
    /** 表示数组第一个元素的偏移地址 */
    private static final long ABASE;
    private static final int ASHIFT;

    static {
        try {
            U = sun.misc.Unsafe.getUnsafe();
            Class<?> k = ConcurrentHashMap.class;
            SIZECTL = U.objectFieldOffset
                (k.getDeclaredField("sizeCtl"));
            TRANSFERINDEX = U.objectFieldOffset
                (k.getDeclaredField("transferIndex"));
            BASECOUNT = U.objectFieldOffset
                (k.getDeclaredField("baseCount"));
            CELLSBUSY = U.objectFieldOffset
                (k.getDeclaredField("cellsBusy"));
            Class<?> ck = CounterCell.class;
            CELLVALUE = U.objectFieldOffset
                (ck.getDeclaredField("value"));
            Class<?> ak = Node[].class;
            ABASE = U.arrayBaseOffset(ak);
            // 表示数组单元所占用空间大小，scale 表示 Node[] 数组中每一个单元所占用空间大小
            int scale = U.arrayIndexScale(ak);
            // 判断 scale 是否为 2 的幂次方
            // 例:   10 & 01 = 0
            //      100 & 011 = 0
            //      1000 & 0111 = 0
            if ((scale & (scale - 1)) != 0)
                throw new Error("data type scale not a power of two");
            // numberOfLeadingZeros 方法返回当前数值转换为二进制后，从高位到低位开始统计，看有多少个 0 连续在一起
            // ASHIFT 算出来结果为 scale 右边 0 的个数
            // 例:   4 -> 100 scale 为 2
            // Node[] 中某一个元素的位置偏移量为 ABASE + n * scale
            // n * scale 可以替换为 n << ASHIFT
            // Node[] 中某一个元素的位置偏移量就可以表示为 ABASE + n << ASHIFT
            ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
        } catch (Exception e) {
            throw new Error(e);
        }
    }

私有变量解释:

/**
     * 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;

    /**
     * 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.
     * 集合元素数量, 通过 CAS 的方式更新数量, 发生并发修改 baseCount 的时候,
     * 创建 counterCells 数组, 用 CounterCell 来统计数据, 集合元素数量为所有 CounterCell
     * 中统计的数量之和 + baseCount
     */
    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.
     * -1 时, 表示当前的 table 正在初始化
     * < -1 时, 表示正在初始化，高 16 位扩容的标示戳，低 16 位表示扩容的线程数
     * 0 时, 表示创建
     * > 0 时,  1.如果 table 未初始化，表示初始话大小
     *          2.如果 table 已初始化，表示下次扩容时的阈值
     */
    private transient volatile int sizeCtl;

    /**
     * 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.
     * 0 无锁，1 加锁
     */
    private transient volatile int cellsBusy;

    /**
     * Table of counter cells. When non-null, size is a power of 2.
     * 发生并发修改 baseCount 的时候, 创建 counterCells 数组, 用 CounterCell 来统计数据,
     * 集合元素数量为所有 CounterCell 中统计的数量之和 + baseCount
     */
    private transient volatile CounterCell[] counterCells;

2、 put 方法

public V put(K key, V value) {
        return putVal(key, value, false);
    }

    /** Implementation for put and putIfAbsent */
    // onlyIfAbsent true 直接替换
    //              false 如果已存在 value 则不替换
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        // 扰动减少哈希冲突, 生成 hash
        int hash = spread(key.hashCode());
        // 节点标识
        // 等于 2 表示为树节点或链表中第 2 个节点
        // 大于零表示链表中的第 n 个节点
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            // f 头节点
            // n 散列表数组长度
            // i 寻址后的数组下标
            // fh 头节点哈希
            Node<K,V> f; int n, i, fh;
            // 当 table 未初始化的时候, 初始化集合
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            // 当前桶位没有数据时, 直接尝试 put 数据
            // tabAt() 获取当前桶位数据
            // (n - 1) & hash 寻址算法
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                // 如果发生并发竞争设置失败, 则继续自旋
                // casTabAt() 修改当前桶位数据
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
            // 如果当前节点为 FWD 节点, 则参与帮助集合进行扩容
            else if ((fh = f.hash) == MOVED)
                // 集合扩容方法
                tab = helpTransfer(tab, f);
            // 剩下的为发生哈希冲突的情况 (桶位已有数据)
            else {
                // 旧值临时值
                V oldVal = null;
                // 锁住该桶位的数据
                synchronized (f) {
                    // 防止头节点的值被其他线程修改
                    // tabAt(tab, i) 为获取当前桶位的头节点
                    if (tabAt(tab, i) == f) {
                        // 头节点哈希大于等于 0 表示为链表节点
                        // -1 表示该节点为 FWD (集合正在扩容, 该桶位的数据已迁移到新数组) 节点
                        // MOVED = -1;
                        // -2 表示树化节点
                        // TREEBIN   = -2;
                        // RESERVED  = -3;
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                // 当前节点的 key
                                K ek;
                                // 当前节点的 key 等于要插入的 key
                                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;
                                }
                            }
                        }
                        // 如果当前节点为红黑树节点
                        else if (f instanceof TreeBin) {
                            // 与要插入的 key 哈希相等的节点
                            Node<K,V> p;
                            binCount = 2;
                            // 调用 TreeBin 的方法设置 value
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                // 保存当前节点的值
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    // 覆盖当前节点的值
                                    p.val = value;
                            }
                        }
                    }
                }
                // 不等于 0 表示插入成功, 等于 0 表示还没插入, 继续自旋
                if (binCount != 0) {
                    // 满足树化条件, 将链表树化
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    // 表示发生哈希冲突, 进行的是替换操作, 直接返回, oldVal, 不同将集合元素数加一
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        // 加减集合元素数的方法, 集合元素数加一
        addCount(1L, binCount);
        // 没有哈希冲突, 返回 null
        return null;
    }

    @SuppressWarnings("unchecked")
    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
        // ASHIFT 表示为 Node[] 数组一个元素的偏移量(必为 2 的 n 次方)的 2 的几次方数
        // Node[] 中某第 n 个元素的位置偏移量为 ABASE + n << ASHIFT
        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
    }

    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                        Node<K,V> c, Node<K,V> v) {
        // ASHIFT 表示为 Node[] 数组一个元素的偏移量(必为 2 的 n 次方)的 2 的几次方数
        // Node[] 中某第 n 个元素的位置偏移量为 ABASE + n << ASHIFT
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
    }

    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
        // ASHIFT 表示为 Node[] 数组一个元素的偏移量(必为 2 的 n 次方)的 2 的几次方数
        // Node[] 中某第 n 个元素的位置偏移量为 ABASE + n << ASHIFT
        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
    }

    final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
        // nextTab 扩容临时表
        // sc sizeCtl
        Node<K,V>[] nextTab; int sc;
        // 如果 tab 不为空, 当前节点为 FWD 节点, nextTable 也不为空
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
            // 计算获得当前扩容的标识戳, 计算出来的数 < 0
            int rs = resizeStamp(tab.length);
            // 满足条件表示扩容仍然在进行中
            // sizeCtl < 0 表示正在扩容
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
                // (sc >>> RESIZE_STAMP_SHIFT) != rs, 表示生成的标识戳与当前扩容标识戳不符, sc 表示 sizeCtl, sizeCtl 小于 0 时, 高 16 位表示标识戳, 低 16 位表示 1 + 参与扩容的线程数
                // transferIndex <= 0 表示扩容已完成, transferIndex 从数组的最后开始向前标记做数据迁移
                // sc == rs + 1 源码中写错了, bug jira 中已经提出来应为 sc == (rs << 16) + 1, 表示扩容完毕
                // sc == rs + MAX_RESIZERS, 也写错了, 应为 sc == (rs << 16) + MAX_RESIZERS, 表示已经达到最大扩容线程数量
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                // 尝试将扩容线程数 + 1, 进入扩容方法
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);
                    break;
                }
            }
            // 返回扩容后的表
            return nextTab;
        }
        return table;
    }

    /**
     * Returns the stamp bits for resizing a table of size n.
     * Must be negative when shifted left by RESIZE_STAMP_SHIFT.
     */
    static final int resizeStamp(int n) {
        // 保证生成的标识戳第一位为 1, 即为负数
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }

3、 addCount 方法

持续更新

参考文献：
① https://www.jianshu.com/p/865c813f2726