1
/**
2
 * 集合最大容量限制.
3
 */
4
private static final int MAXIMUM_CAPACITY = 1 << 30;
5

6
/**
7
 * 默认初始容量。该值必须是 2 的 n 次幂，默认值为 16
8
 */
9
private static final int DEFAULT_CAPACITY = 16;
10

11
/**
12
 * 数组的最大长度
13
 */
14
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
15

16
/**
17
 * 默认的并行度，为了兼容 JDK7 版本中的 Segment
18
 */
19
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
20

21
/**
22
 * 扩容因子，当元素个数达到0.75*数组长度的时候触发扩容，也是jdk1.7使用，jdk1.8直接使用位操作计算出扩容阈值
23
 */
24
private static final float LOAD_FACTOR = 0.75f;
25

26
/**
27
 * 桶中-链表转换为红黑树的阈值
28
 */
29
static final int TREEIFY_THRESHOLD = 8;
30

31
/**
32
 * 桶中-红黑树还原为链表的阈值
33
 */
34
static final int UNTREEIFY_THRESHOLD = 6;
35

36
/**
37
 * 链表转化为红黑树时对集合最小容量的限制值，如果集合容量小于该值则链表不会转换为红黑树
38
 */
39
static final int MIN_TREEIFY_CAPACITY = 64;
40

41
/**
42
 * 并发扩容时每个线程最少处理16个桶
43
 */
44
private static final int MIN_TRANSFER_STRIDE = 16;
45

46
/**
47
 * 这三个常量控制并发扩容的结束，其实就是开始扩容的时候设置sizeCtl成一个负数，每次加入一个线程去扩容就sizeCtl++，
48
 * 每次一个线程扩容结束就sizeCtl–-,那么当所有线程扩容结束后sizeCtl就等于最开始设置的那个负数
49
 */
50
private static int RESIZE_STAMP_BITS = 16;
51
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
52
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
53

54
/**
55
 * 当node节点的hash值 为-1时，表示当前节点为FWD节点
56
 */
57
static final int MOVED = -1;
58

59
/**
60
 * 当node节点的hash值 为-2时， 表示当前节点已经树化,且当前节点为TreeBin对象,TreeBin对象代理操作红黑树
61
 */
62
static final int TREEBIN = -2;
63

64
/**
65
 * 标识为ReservationNode节点（hash=-3），用于map.compute操作
66
 */
67
static final int RESERVED = -3;
68

69
/**
70
 * 可以将一个负数通过位与运算后得到正数，但是不是取绝对值
71
 */
72
static final int HASH_BITS = 0x7fffffff;

1
/**
2
 * 系统CPU的数量
3
 */
4
static final int NCPU = Runtime.getRuntime().availableProcessors();
5

6
/**
7
 * .散列表，长度一定是2次方数
8
 */
9
transient volatile Node<K,V>[] table;
10

11
/**
12
 * 扩容过程中，会将扩容中的新table 赋值给nextTable 保持引用，扩容结束之后，这里会被设置为null
13
 */
14
private transient volatile Node<K,V>[] nextTable;
15

16
/**
17
 * 未发生竞争时，或者当前LongAdder 处于加锁状态时，增量累加到baseCount
18
 */
19
private transient volatile long baseCount;
20

21
/**
22
 * sizeCtl < 0
23
 * 1. -1 表示当前table正在初始化(有线程在创建table数组)，当前线程需要自旋等待
24
 * 2.表达当前map正在进行扩容 高16位表示:扩容的标识戳 低16位: 表示 1+N Thread 当前参与并发扩容的线程数量
25
 *
26
 * sizeCtl = 0;
27
 * 表示创建map时，使用DEFALUT_CAPACITY 为大小
28
 *
29
 * sizeCtl > 0;
30
 * 1.如果table未初始化，表示初始化大小；
31
 * 2.如果table已经初始化了，表示下次扩容时触发条件(阈值）
32
 */
33
private transient volatile int sizeCtl;
34

35
/**
36
 * 扩容过程中，记录当前进度。所有线程都需要从transferIndex中分配区间任务，去执行自己的任务
37
 */
38
private transient volatile int transferIndex;
39

40
/**
41
 * LongAdder中的 cellsBuzy 0表示当前LongAdder对象无锁状态，1表示当前LongAdder对象加锁状态
42
 */
43
private transient volatile int cellsBusy;
44

45
/**
46
 * LongAdder 中的cells数组，当baseCount发生竞争后，会创建cells数组.线程会通过计算hash值取到自己的cell，将增量累加到指定cell中
47
 */
48
private transient volatile CounterCell[] counterCells;

1
/**
2
 * 无参构造方法
3
 */
4
public ConcurrentHashMap() {
5
}

1
/**
2
 * 支持配置初始化容量的构造方法
3
 *
4
 * @param initialCapacity 初始化容量
5
 */
6
public ConcurrentHashMap(int initialCapacity) {
7
    if (initialCapacity < 0)
8
        throw new IllegalArgumentException();
9
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
10
               MAXIMUM_CAPACITY :
11
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
12
    this.sizeCtl = cap;
13
}

1
/**
2
 * 支持配置初始化容量与负载因子的构造方法
3
 *
4
 * @param initialCapacity 初始化容量
5
 * @param loadFactor      负载因子
6
 */
7
public HashMap(int initialCapacity, float loadFactor) {
8
    // 如果初始化容量为负数，则抛出 IllegalArgumentException 异常
9
    if (initialCapacity < 0) {
10
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
11
    }
12
    // 如果初始化容量大于 MAXIMUM_CAPACITY 值，则就设置初始化容量为 MAXIMUM_CAPACITY
13
    if (initialCapacity > MAXIMUM_CAPACITY) {
14
        initialCapacity = MAXIMUM_CAPACITY;
15
    }
16
    // 如果负载因子为负数，或者非数字 (NaN)，则抛出 IllegalArgumentException 异常
17
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
18
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
19
    }
20
    // 设置【负载因子】和【扩容阈值】变量
21
    this.loadFactor = loadFactor;
22
    this.threshold = tableSizeFor(initialCapacity);
23
}

1
/**
2
 * 返回一个大于等于且最接近 cap 的 2 的幂次方:
3
 *  - 比如传入初始化容量 cap = 9，则返回 2^4，即 16
4
 *  - 比如传入初始化容量 cap = 25，则返回 2^5，即 32
5
 *
6
 * @param c 传入构造方法中初始化容量
7
 * @return 传入初始化容量 cap 的 2 的幂次方
8
 */
9
private static final int tableSizeFor(int c) {
10
    int n = c - 1;
11
    n |= n >>> 1;
12
    n |= n >>> 2;
13
    n |= n >>> 4;
14
    n |= n >>> 8;
15
    n |= n >>> 16;
16
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
17
}

1
/**
2
 * 支持根据已有 Map 集合创建新集合的构造方法
3
 *
4
 * @param m 已有的 Map 集合
5
 */
6
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
7
    this.sizeCtl = DEFAULT_CAPACITY;
8
    putAll(m);
9
}

1
/**
2
 * 将插入的 Map 集合中的数据转移到当前集合中
3
 *
4
 * @param m 需要将数据插入到新集合中的 Map 集合
5
 */
6
public void putAll(Map<? extends K, ? extends V> m) {
7
    tryPresize(m.size());
8
    for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
9
        putVal(e.getKey(), e.getValue(), false);
10
    }
11
}

1
/**
2
 * 初始化数组
3
 *
4
 * @return 初始后的数组
5
 */
6
private final Node<K,V>[] initTable() {
7
    Node<K,V>[] tab;  // 记录待初始的数组的变量
8
    int sc;           // 记录 sizeCtl 值的变量
9

10
    // 循环执行初始化操作
11
    while ((tab = table) == null || tab.length == 0) {
12
        // 设置变量 sc = sizeCtl，然后判断 sc 变量大小是否小于 0:
13
        //  - 如果 sc = -1，则说明有其他线程在执行初始化，为了保证线程安全，使当前线程先让出 CPU 时间片；
14
        //  - 如果 sc > 0，则说明没有其它线程执行初始化，当前线程可以执行初始化操作；
15
        if ((sc = sizeCtl) < 0) {
16
            Thread.yield();
17
        }
18
        // 使用 CAS 方法，将当前对象中的 SIZECTL 属性值与 sc 进行比较:
19
        //  - 如果值相等，则将 SIZECTL 的值更新为 -1，然后执行 if 中的逻辑；
20
        //  - 如果值不相等，不执行 if 中的逻辑；
21
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
22
            try {
23
                // 设置变量 tab = table，然后判断 table 是否为空，是则执行初始化操作。
24
                if ((tab = table) == null || tab.length == 0) {
25
                    // 如果初始化容量了，则设置为 sc，否则设置为默认容量 16
26
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
27
                    @SuppressWarnings("unchecked")
28
                    // 初始化 table 数组
29
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
30
                    table = tab = nt;
31
                    // 计算下次扩容的大小,实际就是当前容量的 0.75 倍，这里使用了右移来计算
32
                    sc = n - (n >>> 2);
33
                }
34
            } finally {
35
                // 设置 sizeCtl 为 sc,如果默认是 16 的话，则 sc 为 16*0.75=12
36
                sizeCtl = sc;
37
            }
38
            break;
39
        }
40
    }
41
    // 返回初始后的表
42
    return tab;
43
}

1
/**
2
 * 获取 tab 数组中下标为 i 的元素。
3
 *
4
 * 这里之所以使用 getObjectVolatile() 方法获取数组中指定位置的元素，这是因为该方法属于 volatile 类型方法，
5
 * 可以保证数组中数据的可见性，其它线程对当前数组进行修改后，当前线程可以马上观察到最新的改动。
6
 *
7
 * @param tab 待操作的数组
8
 * @param i   数组的下标位置
9
 * @return    数组指定下标位置的元素
10
 */
11
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
12
    // ABASE 表示数组地址，(long)i << ASHIFT 表示偏移量
13
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
14
}

1
/**
2
 * 将 tab 数组中下标为 i 的元素与预期值 c 进行比较，如果相同则将 i 位置元素更新为 v，否则不更新。
3
 *
4
 * 使用 compareAndSwapObject 方法进行更新，可以保证多线程环境下的操作的线程安全。
5
 *
6
 * @param tab 待操作的数组
7
 * @param i   数组的下标位置
8
 * @param c   预期值
9
 * @param v   如果符合预期进行更新的值
10
 * @return    如果 tab 数组中下标为 i 的元素与预期值 c 相同，则返回 ture，否则返回 false
11
 */
12
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
13
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
14
}

1
/**
2
 * 将指定的键值对插入到 ConcurrentHashMap 集合中。 (不允许插入null键和null值)
3
 *
4
 * @param key   待插入的键
5
 * @param value 待插入的值
6
 * @return 返回与 Key 关联的旧值，分两种情况:
7
 *   - 如果集合中不存在对应的 key，即插入一个新的 key，则返回 null；
8
 *   - 如果集合中已经存在一个相同的 key，则新 value 覆盖旧 value，然后返回旧 value；
9
 */
10
public V put(K key, V value) {
11
    return putVal(key, value, false);
12
}

1
/**
2
 * 实现 Map.put() 和相关方法。
3
 *
4
 * @param key   待插入的键
5
 * @param value 待插入的值
6
 * @param onlyIfAbsent 如果为 true 则不更改现有的值
7
 * @return 如果插入的 Key 已经存在，则返回已存在 Key 的节点值，否则返回 null
8
 */
9
final V putVal(K key, V value, boolean onlyIfAbsent) {
10
    // 如果插入的 key 或者 value 为 null，则抛出空指针异常
11
    if (key == null || value == null) {
12
        throw new NullPointerException();
13
    }
14
    // 计算 hash 值
15
    int hash = spread(key.hashCode());
16
    // 创建变量 binCount，使用改变量记录，当数组下标位置关联的为链表或红黑树时:
17
    //  - 如果是链表，则设置 binCount 值为链表的节点数量，后续用于判断是否需要将链表转换为红黑树；
18
    //  - 如果是红黑树，则设置 binCount 值为固定值 2，表示在红黑树中插入或者替换了值，用于后续判断是否需要返回旧值；
19
    int binCount = 0;
20

21
    // 死循环执行循环代码块中的逻辑 (自旋操作)
22
    for (Node<K,V>[] tab = table;;) {
23
        // f:  记录待插入 key 经计算找到在 table 数组中的下标位置节点的变量
24
        // n:  记录 table 数组长度的变量
25
        // i:  记录待插入 key 经计算找到在 table 数组中的下标位置的变量
26
        // fh: 记录 table 数组中的下标位置节点 hash 值的变量
27
        Node<K,V> f; int n, i, fh;
28

29
        // --- 1、判断 table 数组是否初始化 ---
30
        // 判断 table 数组是否为空，如果是则调用 initTable() 方法进行初始化操作
31
        if (tab == null || (n = tab.length) == 0) {
32
            tab = initTable();
33
        }
34
        // --- 2、判断 table 数组下标位置是否哈希冲突 ---
35
        // 调用 tabAt() 方法获取插入 key 在 table 数组中下标位置的节点，并赋给变量 f，然后判断节点是否为 null:
36
        //  - 如果为 null，则说明当前数组下标位置为空，则执行 else if 条件中的代码逻辑；
37
        //  - 如果不为 null，则说明当前数组下标位置已经存在数据，发生了哈希冲突，不执行 else if 条件中的代码逻辑；
38
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
39
            // 如果数组下标位置的节点为 null，则使用 CAS 方法，判断当前数组下标位置是否为 null:
40
            //  - 如果当前数组下标位置为 null，则将新创建的键值对 Node 节点加入到该位置；
41
            //  - 如果当前数组下标位置不为 null，则不进行任何操作；
42
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) {
43
                break; // no lock when adding to empty bin
44
            }
45
        }
46
        // --- 3、判断当前集合是否正在执行扩容 ---
47
        // 获取数组下标位置节点的 hash 值并赋给变量 fh，然后判断 hash 值是否为 MOVED(-1):
48
        // - 如果 hash 值为 -1，则说明有其它线程正在对当前集合进行扩容，当前桶位置的节点为 ForwardingNode 转移节点，
49
        //   这时当前线程就会执行 helpTransfer() 方法协助其它线程进行扩容操作，然后将插入的数据加入扩容后的新数组中；
50
        // - 如果 hash 值不为 -1，则说明当前结合没有进行扩容，不执行 if 中的代码逻辑；
51
        else if ((fh = f.hash) == MOVED) {
52
            tab = helpTransfer(tab, f);
53
        }
54
        // --- 4、将插入的键值对加入到链表或者红黑树中 ---
55
        else {
56
            // 记录找到的节点的原先 value 值的变量
57
            V oldVal = null;
58
            // 使用 synchronized 进行加锁，并以当前数组下标位置节点 f 作为锁对象
59
            synchronized (f) {
60
                // 再次判断当前数组下标位置的节点是否为 f，只所以需要再次判断，这是因为在添加元素的时候，
61
                // 有可能同时又有其它线程在移除元素，这种情况需要自旋操作来重新插入。
62
                if (tabAt(tab, i) == f) {
63
                    // 判断数组下标位置节点的 hash 值是否大于等于 0:
64
                    //  - 如果 hash >= 0，则说明当前数组下标位置关联的是链表；
65
                    //  - 如果 hash < 0，则说明当前数组下标位置关联的是红黑树；
66
                    if (fh >= 0) {
67
                        // 遍历链表，寻找是否存在与插入 key 相同的节点，并且使 binCount 值 +1
68
                        binCount = 1;
69
                        for (Node<K,V> e = f;; ++binCount) {
70
                            // 记录遍历过程中当前节点的 key 的变量
71
                            K ek;
72
                            // 如果找到插入 key 的节点，则记录当前节点的值赋给变量 oldVal，然后将插入的新 value 替换掉旧值，
73
                            // 最后执行 break 指令终止继续遍历链表。
74
                            if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
75
                                oldVal = e.val;
76
                                if (!onlyIfAbsent) {
77
                                    e.val = value;
78
                                }
79
                                break;
80
                            }
81
                            // 记录前驱节点
82
                            Node<K,V> pred = e;
83
                            // 记录后继节点，并判断当前遍历到的位置是否到了链表末尾节点，如果是就创建新的节点加入到链表末尾
84
                            if ((e = e.next) == null) {
85
                                pred.next = new Node<K,V>(hash, key, value, null);
86
                                break;
87
                            }
88
                        }
89
                    }
90
                    // 如果数组下标位置的节点 f 为红黑树节点，则将键值对数据加入到红黑树中
91
                    else if (f instanceof TreeBin) {
92
                        // 记录调用 putTreeVal() 方法的返回结果
93
                        Node<K,V> p;
94
                        // 设置 binCount 为 2
95
                        binCount = 2;
96
                        // 调用 putTreeVal() 方法将键值对数据加入到红黑树中，并且判断方法返回结果:
97
                        //  - 如果方法返回结果为 null，则说明执行了添加操作，不用记录老值；
98
                        //  - 如果方法返回结果不为 null，则说明执行了替换操作，需要记录老值赋给变量 oldVal，
99
                        //    然后将插入的新 value 替换掉旧值；
100
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
101
                            oldVal = p.val;
102
                            if (!onlyIfAbsent) {
103
                                p.val = value;
104
                            }
105
                        }
106
                    }
107
                }
108
            }
109
            // 如果 binCount 不为 0 则说明在链表或者红黑树中进行了插入或替换操作，则执行 if 中的代码逻辑
110
            if (binCount != 0) {
111
                // 判断变量 binCount 是否大于等于 TREEIFY_THRESHOLD(8)，如果是则尝试将链表转换为红黑树，不过:
112
                //  - 如果当前集合大小 < 64 树化最小限制容量 MIN_TREEIFY_CAPACITY(64)，则不会转换为红黑树，
113
                //    只会对当前集合进行一次扩容操作；
114
                //  - 如果当前集合大小 ≥ 树化最小限制容量 IN_TREEIFY_CAPACITY(64)，则就将链表转换为红黑树；
115
                if (binCount >= TREEIFY_THRESHOLD) {
116
                    treeifyBin(tab, i);
117
                }
118
                // 判断老值是否不为空，是则返回老值
119
                if (oldVal != null) {
120
                    return oldVal;
121
                }
122
                break;
123
            }
124
        }
125
    }
126
    // 执行到这里说明进行了添加操作，而没有进行替换操作，添加数据就使结合大小 +1，然后判断是否达到了库容阈值，是就进行扩容
127
    addCount(1L, binCount);
128
    return null;
129
}

1
/**
2
 * 从集合中删除指定 key 对应的键值对数据
3
 *
4
 * @param key 待删除的键值对 key
5
 * @return 判断集合中存在指定的 key 对应的键值对数据，不存在则返回 null，存在则返回键值对的 value
6
 */
7
public V remove(Object key) {
8
    return replaceNode(key, null, null);
9
}

1
/**
2
 * 替换/删除方法
3
 * - 如果传入参数 value 为空，则执行删除操作；
4
 * - 如果传入参数 value 不为空，则执行替换操作，将 cv 替换为 value；
5
 *
6
 * @param key   键值对 key
7
 * @param value 键值对 value
8
 * @param cv    待替换的旧值
9
 * @return 如果执行删除操作则返回 null，如果执行替换操作则返回旧值
10
 */
11
final V replaceNode(Object key, V value, Object cv) {
12
    int hash = spread(key.hashCode());
13
    for ( Node<K,V>[] tab = table;;) {
14
        Node<K,V> f;  // 记录数组下标位置节点的变量
15
        int n;        // 记录数组 table 长度的变量
16
        int i;        // 记录数组下标位置索引的变量
17
        int fh;       // 记录数组下标位置哈希值的变量
18

19
        // 如果当前数组 table 为空，或者数组下标位置为空，则表示数据已经被删除，直接结束循环
20
        if (tab == null || (n = tab.length) == 0 || (f = tabAt(tab, i = (n - 1) & hash)) == null) {
21
            break;
22
        }
23
        // 获取数组下标位置节点的 hash 值并赋给变量 fh，然后判断 hash 值是否为 MOVED(-1):
24
        // - 如果 hash 值为 -1，则说明有其它线程正在对当前集合进行扩容，当前桶位置的节点为 ForwardingNode 转移节点，
25
        //   这时当前线程就会执行 helpTransfer() 方法协助其它线程进行扩容操作，然后将插入的数据加入扩容后的新数组中；
26
        // - 如果 hash 值不为 -1，则说明当前结合没有进行扩容，不执行 if 中的代码逻辑；
27
        else if ((fh = f.hash) == MOVED) {
28
            tab = helpTransfer(tab, f);
29
        }
30
        else {
31
            V oldVal = null;            // 记录找到的节点的原先 value 值的变量
32
            boolean validated = false;  // 记录是否处理过当前数组下标位置关联的链表或者红黑树
33

34
            // 使用 synchronized 进行加锁，并以当前数组下标位置节点 f 作为锁对象
35
            synchronized (f) {
36
                // 再次判断当前数组下标位置的节点是否为 f，只所以需要再次判断，这是因为在添加元素的时候，
37
                // 有可能同时又有其它线程在移除元素，这种情况需要自旋操作来重新操作。
38
                if (tabAt(tab, i) == f) {
39
                    // 判断数组下标位置节点的 hash 值是否大于等于 0:
40
                    //  - 如果 hash >= 0，则说明当前数组下标位置关联的是链表；
41
                    //  - 如果 hash < 0，则说明当前数组下标位置关联的是红黑树；
42
                    if (fh >= 0) {
43
                        // 标记为 true，表示处理过
44
                        validated = true;
45
                        // 从链表头结点开始遍历链表
46
                        for (Node<K,V> e = f, pred = null;;) {
47
                            // 记录遍历过程中当前节点的 key 的变量
48
                            K ek;
49
                            // 如果找到指定 key 的节点，则记录当前节点的值赋给变量 oldVal，然后将插入的新 value 替换掉旧值，
50
                            // 最后执行 break 指令终止继续遍历链表。
51
                            if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
52
                                // 记录当前节点的 value 值
53
                                V ev = e.val;
54
                                // 判断是否传入 cv:
55
                                //  - 如果传入的旧值 cv 为 null 则执行下面替换/删除逻辑；
56
                                //  - 如果当前节点 value 和传入旧值 cv 相同，则执行下面替换/删除逻辑；
57
                                if (cv == null || cv == ev || (ev != null && cv.equals(ev))) {
58
                                    // 将旧值赋给变量 oldVal
59
                                    oldVal = ev;
60
                                    // 判断 value 是否为空:
61
                                    //  - 如果 value 不为空，则说明要执行替换操作；
62
                                    //  - 如果 value 为空，则说明要执行删除操作；
63
                                    if (value != null) {
64
                                        // 将旧值替换为 value
65
                                        e.val = value;
66
                                    }
67
                                    // 判断将当前节点是否有前驱节点:
68
                                    //  - 如果有前驱节点，则设置 pred.next = e.next 来进行删除当前节点；
69
                                    //  - 如果没有前驱节点，则说明当前节点是头结点，设置 setTabAt(tab, i, e.next) 直接删除当前节点；
70
                                    else if (pred != null) {
71
                                        pred.next = e.next;
72
                                    }
73
                                    else {
74
                                        setTabAt(tab, i, e.next);
75
                                    }
76
                                }
77
                                break;
78
                            }
79
                            // 设置前驱节点为当前节点
80
                            pred = e;
81
                            // 将后继节点赋给变量 e，然后判断其是否为 null，如果是则说明已经遍历到尾节点，直接结束循环
82
                            if ((e = e.next) == null) {
83
                                break;
84
                            }
85
                        }
86
                    }
87
                    // 判断当前节点是否为树节点
88
                    else if (f instanceof  TreeBin) {
89
                        // 标记为 true，表示处理过
90
                        validated = true;
91
                        // 将节点 Node 强转为 TreeBin
92
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
93
                        TreeNode<K,V> r;  // 记录树 root 节点的变量
94
                        TreeNode<K,V> p;  // 记录接收 findTreeNode 方法返回结果的变量
95
                        // 将 root 节点赋给变量 r，然后调用 findTreeNode 方法遍历树查找指定 key 节点:
96
                        // - 如果调用 findTreeNode() 方法返回找到的指定 key 的树节点，则执行下面逻辑；
97
                        // - 如果调用 findTreeNode() 方法返回 null，则没有找到，不执行下面逻辑；
98
                        if ((r = t.root) != null && (p = r.findTreeNode(hash, key, null)) != null) {
99
                            // 将找到的树节点赋给变量 pv
100
                            V pv = p.val;
101
                            // 判断是否传入 cv:
102
                            //  - 如果传入的旧值 cv 为 null 则执行下面替换/删除逻辑；
103
                            //  - 如果当前节点 value 和传入旧值 cv 相同，则执行下面替换/删除逻辑；
104
                            if (cv == null || cv == pv || (pv != null && cv.equals(pv))) {
105
                                // 将旧值赋给变量 oldVal
106
                                oldVal = pv;
107
                                // 判断 value 是否为空:
108
                                //  - 如果 value 不为空，则说明要执行替换操作；
109
                                //  - 如果 value 为空，则说明要执行删除操作；
110
                                if (value != null) {
111
                                    p.val = value;
112
                                }
113
                                // 执行到这里说明 value 为空，执行删除操作，调用 t.removeTreeNode(p) 方法删除当前节点，
114
                                // 然后判断方法返回结果:
115
                                //  - 如果方法返回 true，则表示删除节点后树的元素个数较少，则将红黑树转换为链表；；
116
                                //  - 如果方法返回 false，则表示删除节点后树的元素个数依旧很多，则不将红黑树转换为链表；
117
                                else if (t.removeTreeNode(p)) {
118
                                    setTabAt(tab, i, untreeify(t.first));
119
                                }
120
                            }
121
                        }
122
                    }
123
                }
124
            }
125
            // 如果处理过，不管有没有找到元素都返回
126
            if (validated) {
127
                // 判断变量 oldVal 是否为空:
128
                //  - 如果不为 null 则说明存在旧值，返回结果将旧值返回；
129
                //  - 如果为 null 则说明不存在旧值，返回结果返回 null;
130
                if (oldVal != null) {
131
                    // 判断 value 是否为空:
132
                    //  - 如果 value 不为空，则说明要执行替换操作；
133
                    //  - 如果 value 为空，则说明要执行删除操作，这里执行 addCount 方法减小集合大小；
134
                    if (value == null) {
135
                        addCount(-1L, -1);
136
                    }
137
                    return oldVal;
138
                }
139
                break;
140
            }
141
        }
142
    }
143
    return null;
144
}

1
 /**
2
 * 协助扩容
3
 *
4
 * @param tab 待操作的数组
5
 * @param f   需要查找的节点
6
 * @return 如果扩容结束则返回当前 tabel 数组，否则返回新的 table 数组
7
 */
8
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
9
    Node<K,V>[] nextTab; // 下一个节点
10
    int sc;              // 记录 sizeCtl 的变量
11

12
    // 如果旧 table 不为空，并且要查找的节点是转移节点，则判断新 table 是否为空:
13
    //  - 如果新 table 为空，则说明扩容已经结束；
14
    //  - 如果新 table 不为空，则说明扩容正在进行，当前线程协助集合进行扩容操作；
15
    if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
16
        // 根据数组长度得到一个扩容戳
17
        int rs = resizeStamp(tab.length);
18
        // 循环判断是否扩容完成
19
        while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {
20
            // 判断你是否符合下面条件，如果符合则说明扩容结束，则直接退出循环，判断条件如下:
21
            // - sc >>> RESIZE_STAMP_SHIFT != rs 表示同一轮扩容中 sc 无符号右移比较高位和 rs 的值应该是相等的，
22
            //   如果不相等说明扩容结束；
23
            // - rs + 1 表示扩容结束;
24
            // - rs + MAX_RESIZERS 表示扩容线程数达到最大扩容线程数；
25
            // - transferIndex <= 0 表示所有的 Node 都已经分配了线程；
26
            if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0) {
27
                break;
28
            }
29
            // 每增加一个线程来协助迁移就使 sizeCtl 值 +1, 然后当前线程协助扩容
30
            if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
31
                transfer(tab, nextTab);
32
                break;
33
            }
34
        }
35
        // 返回新的 table 数组
36
        return nextTab;
37
    }
38
    // 返回当前 table 数组
39
    return table;
40
}

1
/**
2
 * 链表转换为红黑树
3
 *
4
 * @param tab   数组 table
5
 * @param index 数组索引位置
6
 */
7
private final void treeifyBin(Node<K,V>[] tab, int index) {
8
    Node<K,V> b; // 记录数组指定索引位置节点的变量
9
    int n, sc;   // 记录数组长度
10

11
    // 如果数组 table 不为空，则执行 if 中的代码逻辑
12
    if (tab != null) {
13
        // 判断当前数组长度是否达到了转换为红黑树要求的最小容量:
14
        //  - 如果当前数组长度 < 转换为红黑树要求的最小容量，则不转换为红黑树，只对 table 数组进行扩容；
15
        //  - 如果当前数组长度 ≥ 转换为红黑树要求的最小容量，则将数组指定索引位置关联的链表转换为红黑树；
16
        if ((n = tab.length) < MIN_TREEIFY_CAPACITY) {
17
            tryPresize(n << 1);
18
        }
19
        else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
20
            // 使用同步锁，并且以数组索引下标位置的节点作为锁对象
21
            synchronized (b) {
22
                // 再次验证数组下标索引下标位置的节点是否和变量 b 记录的节点相同，是则执行链表转换为红黑树的逻辑
23
                if (tabAt(tab, index) == b) {
24
                    TreeNode<K,V> hd = null, tl = null;
25
                    for (Node<K,V> e = b; e != null; e = e.next) {
26
                        TreeNode<K,V> p = new TreeNode<K,V>(e.hash, e.key, e.val, null, null);
27
                        if ((p.prev = tl) == null) {
28
                            hd = p;
29
                        } else {
30
                            tl.next = p;
31
                        }
32
                        tl = p;
33
                    }
34
                    setTabAt(tab, index, new TreeBin<K,V>(hd));
35
                }
36
            }
37
        }
38
    }
39
}

1
/**
2
 * 取消树化，将红黑树转换为链表
3
 *
4
 * @param b 待转换的红黑树节点
5
 * @return 链表
6
 */
7
static <K,V> Node<K,V> untreeify(Node<K,V> b) {
8
    Node<K,V> hd = null; // 记录链表头节点的变量
9
    Node<K,V> tl = null; // 记录链表尾节点的变量
10

11
    // 遍历 Node 节点
12
    for (Node<K,V> q = b; q != null; q = q.next) {
13
        // 根据已有的节点创建的数据，创建新节点
14
        Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);
15
        // 如果为遍历的第一次，则记录链表的头结点
16
        if (tl == null) {
17
            hd = p;
18
        }
19
        // 将上一个节点的下一个节点指向当前这个节点
20
        else {
21
            tl.next = p;
22
        }
23
        // 将 tl 节点指向 p
24
        tl = p;
25
    }
26
    // 返回链表的头结点
27
    return hd;
28
}

1
/**
2
 * 尝试调整当前集合数组 table 的大小，以容纳给定数量的元素。
3
 *
4
 * @param size 带插入集合的大小
5
 */
6
private final void tryPresize(int size) {
7
    // 判断集合大小 size 是否大于等于 2^29:
8
    //  - 如果是，则设置变量 c 为集合大小为集合最大容量 MAXIMUM_CAPACITY；
9
    //  - 如果不是，则设置变量 c 为调用 tableSizeFor 方法的结果；
10
    int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1);
11
    int sc; // 记录 sizeCtl 的变量
12

13
    // 循环执行，并且判断 sizeCtl >= 0:
14
    //  - 如果 sizeCtl < 0 则表示其它线程正在对当前集合进行初始化或扩容；
15
    //  - 如果 sizeCtl ≥ 0 则表示集合已经扩容完成，则执行下面 while 代码块中的逻辑；
16
    while ((sc = sizeCtl) >= 0) {
17
        Node<K,V>[] tab = table; // 记录数组 table 的变量
18
        int n;                   // 记录数组 table 长度的变量
19

20
        // 如果数组 table 当前为空，则说明数组 table 还没有初始化，先执行初始化操作
21
        if (tab == null || (n = tab.length) == 0) {
22
            n = (sc > c) ? sc : c;
23
            if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
24
                try {
25
                    if (table == tab) {
26
                        @SuppressWarnings("unchecked")
27
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
28
                        table = nt;
29
                        // 相当于执行 n*0.75，即计算扩容阈值
30
                        sc = n - (n >>> 2);
31
                    }
32
                } finally {
33
                    // 设置 sizeCtl 值为 sc 值
34
                    sizeCtl = sc;
35
                }
36
            }
37
        }
38
        // 数组容量已经最大或足够了，不需要扩容
39
        // size 大小 ≤ 扩容阈值，或者 ≥ 最大容量限制值时，不需要进行扩容
40
        else if (c <= sc || n >= MAXIMUM_CAPACITY) {
41
            break;
42
        }
43
        // 验证 tab 记录的变量是否为 table 数组，如果是就进行扩容操作
44
        else if (tab == table) {
45
            // 根据数组长度得到一个扩容戳
46
            // (注: 每次扩容时都会生成一个类似时间戳的校验标记，上一次扩容和下一次扩容都不一样，这个值由当前数组的长度决定)
47
            int rs = resizeStamp(n);
48
            // 判断变量 sizeCtl 的值是否小于 0:
49
            //  - 如果 sizeCtl ≥ 0 则表示集合已经扩容完成；
50
            //  - 如果 sizeCtl < 0 则表示其它线程正在对当前集合进行初始化或扩容，则当前线程进行协助扩容；
51
            // (注: 扩容时 sizeCtl 高 16 位表示扩容戳(校验标记)，低 16 位表示(正在参与扩容的线程数+1))
52
            if (sc < 0) {
53
                Node<K,V>[] nt;
54
                // 判断你是否符合下面条件，如果符合则说明扩容结束，则直接退出循环，判断条件如下:
55
                // - sc >>> RESIZE_STAMP_SHIFT != rs 表示同一轮扩容中 sc 无符号右移比较高位和 rs 的值应该是相等的，
56
                //   如果不相等说明扩容结束；
57
                // - rs + 1 表示扩容结束;
58
                // - rs + MAX_RESIZERS 表示扩容线程数达到最大扩容线程数；
59
                // - (nt = nextTable) == null 表示 nextTable 还没有初始化或者正在进行初始化；
60
                // - transferIndex <= 0 表示所有的 Node 都已经分配了线程；
61
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs
62
                        || sc == rs + 1
63
                        || sc == rs + MAX_RESIZERS
64
                        || (nt = nextTable) == null
65
                        || transferIndex <= 0) {
66
                    break;
67
                }
68
                // 每增加一个线程来协助迁移，就使用 CAS 方法使 sizeCtl 值 +1, 然后当前线程协助扩容
69
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
70
                    transfer(tab, nt);
71
                }
72
            }
73
            // 如果当前没有在扩容，那么 rs 肯定是一个正数
74
            // 通过 rs<<RESIZE_STAMP_SHIFT 将 sc 设置为一个负数，+2 表示有一个线程在执行扩容
75
            else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) {
76
                transfer(tab, null);
77
            }
78
        }
79
    }
80
}

1
/**
2
 * 扩容方法
3
 *
4
 * @param tab     当前 table
5
 * @param nextTab 扩容后的 table
6
 */
7
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
8
    // 记录当前数组 tabel 的长度
9
    int n = tab.length, stride;
10
    // 如果处 CPU 数量大于 1，则通过当前 table 中 Node 总量和 CPU 的数量来计算步长，即每个线程所允许处理的桶的数量
11
    // 注:
12
    // - NCPU 表示可以使用的 CPU 的数量；
13
    // - MIN_TRANSFER_STRIDE 表示并发扩容时每个线程最少处理16个桶；
14
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) {
15
        stride = MIN_TRANSFER_STRIDE;
16
    }
17
    // 如果 nextTab 为 null，则说明是第一个线程进行转移，执行下面 if 中的逻辑。
18
    if (nextTab == null) {
19
        try {
20
            // 创建一个容量为当前数组容量两倍的新数组，并赋给变量 nextTab，
21
            @SuppressWarnings("unchecked")
22
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
23
            nextTab = nt;
24
        } catch (Throwable ex) {
25
            // 如果执行过程中发生异常，则设置 sizeCtl = Integer.MAX_VALUE，然后直接退出不转移了
26
            sizeCtl = Integer.MAX_VALUE;
27
            return;
28
        }
29
        // 将新数组赋值给 nextTable，此时数组为一个没有数据的空数组
30
        nextTable = nextTab;
31
        // 使变量 transferIndex 记录当前数组的长度 n，表示转移开始的索引值
32
        transferIndex = n;
33
    }
34
    // 将新数组的长度赋给变量 nextn
35
    int nextn = nextTab.length;
36
    // 变量 fwd 是于来标识某个桶处正在转移，其存储了新数组
37
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
38
    // 变量 advance 标记用于确认是否需要在区间内继续往前前进处理
39
    boolean advance = true;
40
    // 变量 finishing 用于标记是否将所有的区间都迁移完成了
41
    boolean finishing = false;
42
    // 将 i 和 bound 的值初始化为 0，然后进行自旋，直到数据转移成功后再退出循环
43
    for (int i = 0, bound = 0;;) {
44
        Node<K,V> f; // 记录当前数组指定位置节点的变量
45
        int fh;      // 记录当前数组指定位置节点哈希值的变量
46
        // 控制 --i，遍历原数组中的节点
47
        while (advance) {
48
            int nextIndex, nextBound;
49
            // 某个线程的第二次循环时候才会走到这里来，说明 i 还在该线程需要转移的区间内，即 [bound <--> i <--> transferIndex)
50
            if (--i >= bound || finishing) {
51
                advance = false;
52
            }
53
            // transferIndex ≤ 0 说明已经到最前面了，当前 table 中所有数组元素都已经有其他线程负责扩容
54
            else if ((nextIndex = transferIndex) <= 0) {
55
                i = -1;
56
                advance = false;
57
            }
58
            // 走到这里说明 i < bound 且 transferIndex > 0 (即整个当前 table 数组中的桶的转移还没处理完成)
59
            // 通过 CAS 继续认领一段区间进行转移，计算出当前线程所需要处理的区间，nextBound 就是下一个线程的下边界，
60
            // 也是当线程的上边界
61
            else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,
62
                nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
63
                bound = nextBound;
64
                i = nextIndex - 1;
65
                advance = false;
66
            }
67
        }
68
        // 如果 i < 0 或者 i >= n 说明已经超出了所需要处理的区间了
69
        if (i < 0 || i >= n || i + n >= nextn) {
70
            int sc;
71
            // 判断遍历 finishing 的值:
72
            //  - 如果 finishing 为 true，则说明所有的桶都处理完了，执行下面 if 中的代码逻辑；
73
            //  - 如果 finishing 为 false，则说明害有桶没有处理完成，不执行 if 中的代码逻辑；
74
            if (finishing) {
75
                // 将 nextTable 置为空，并将新的数组赋值给变量 table
76
                nextTable = null;
77
                table = nextTab;
78
                // 设置新的阈值，新数组的长度为 2n，所以阈值应该为 0.75 * 2n，即 2n - 0.5n
79
                sizeCtl = (n << 1) - (n >>> 1);
80
                // 跳出循环
81
                return;
82
            }
83
            // CAS 更扩容阈值，在这里面 sizeCtl 值减 -1，说明新加入一个线程参与到扩容操作
84
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
85
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) {
86
                    return;
87
                }
88
                // 设置变量 finishing 和 advance 状态为 true
89
                finishing = advance = true;
90
                i = n;
91
            }
92
        }
93
        // 如果索引为 i 的桶处为 null，则通过 CAS 方法将 fwd 转移节点放在原数组 i 索引的下标位置，
94
        // 然后将 advance 设置为 true，然后退出循环继续往前
95
        else if ((f = tabAt(tab, i)) == null) {
96
            advance = casTabAt(tab, i, null, fwd);
97
        }
98
        // 获取当前数组 table 中 i 索引下标位置节点的 hash 值并赋给变量 fh，然后判断 hash 值是否为 MOVED(-1):
99
        // - 如果 hash 值为 -1，则说明有其它线程正在对当前集合进行扩容，当前桶位置的节点为 ForwardingNode 转移节点，
100
        //   这时就会将 advance 设置为 true，然后退出循环继续往前；
101
        // - 如果 hash 值不为 -1，则说明当前结合没有进行扩容，不执行 if 中的代码逻辑；
102
        else if ((fh = f.hash) == MOVED) {
103
            advance = true;
104
        } else {
105
            // 使用 synchronized 进行加锁，并以当前数组下标位置节点 f 作为锁对象
106
            synchronized (f) {
107
                // 再次判断当前数组下标位置的节点是否为 f，只所以需要再次判断，这是因为在添加元素的时候，
108
                // 有可能同时又有其它线程在移除元素，这种情况需要自旋操作来重新插入。
109
                if (tabAt(tab, i) == f) {
110
                    // 判断数组下标位置节点的 hash 值是否大于等于 0:
111
                    //  - 如果 hash >= 0，则说明当前数组下标位置关联的是链表；
112
                    //  - 如果 hash < 0，则说明当前数组下标位置关联的是红黑树；
113
                    if (fh >= 0) {
114
                        // 遍历链表，找到第一个后面全部为相同的 runBit 的节点
115
                        int runBit = fh & n;
116
                        Node<K,V> lastRun = f;
117
                        for (Node<K,V> p = f.next; p != null; p = p.next) {
118
                            int b = p.hash & n;
119
                            if (b != runBit) {
120
                                runBit = b;
121
                                lastRun = p;
122
                            }
123
                        }
124
                        // 如果 runBit == 0，则说明这些节点还要放在相同 index 的桶里，赋给变量 ln
125
                        if (runBit == 0) {
126
                            ln = lastRun;
127
                            hn = null;
128
                        }
129
                        // 否则 runBit == n，则说明这些节点还要放在相同 index + n 的桶里，赋给变量 hn
130
                        else {
131
                            hn = lastRun;
132
                            ln = null;
133
                        }
134
                        // 如果节点只有单个数据则直接拷贝，如果是链表则对链表进行遍历拷贝
135
                        for (Node<K,V> p = f; p != lastRun; p = p.next) {
136
                            int ph = p.hash; K pk = p.key; V pv = p.val;
137
                            if ((ph & n) == 0) {
138
                                ln = new Node<K,V>(ph, pk, pv, ln);
139
                            } else {
140
                                hn = new Node<K,V>(ph, pk, pv, hn);
141
                            }
142
                        }
143
                        // 将节点 ln 插入新数组 table 的 i 处
144
                        setTabAt(nextTab, i, ln);
145
                        // 将节点 hn 插入新数组 table 的 i+n 处
146
                        setTabAt(nextTab, i + n, hn);
147
                        // 在原先 table 数组 i 位置设置 ForwardingNode 节点，表示该节点已经处理过了
148
                        // 将原数组 table 的索引 i 位置的节点设置为 fwd 节点
149
                        setTabAt(tab, i, fwd);
150
                        // 更新 advance 为 true，准备下次 for 循环
151
                        advance = true;
152
                    }
153
                    // 如果是 TreeBin，则按照红黑树进行处理，处理逻辑与上面一致
154
                    else if (f instanceof TreeBin) {
155
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
156
                        TreeNode<K,V> lo = null, loTail = null;
157
                        TreeNode<K,V> hi = null, hiTail = null;
158
                        int lc = 0, hc = 0;
159
                        for (Node<K,V> e = t.first; e != null; e = e.next) {
160
                            int h = e.hash;
161
                            TreeNode<K,V> p = new TreeNode<K,V>(h, e.key, e.val, null, null);
162
                            if ((h & n) == 0) {
163
                                if ((p.prev = loTail) == null) {
164
                                    lo = p;
165
                                } else {
166
                                    loTail.next = p;
167
                                }
168
                                loTail = p;
169
                                ++lc;
170
                            }
171
                            else {
172
                                if ((p.prev = hiTail) == null) {
173
                                    hi = p;
174
                                } else {
175
                                    hiTail.next = p;
176
                                }
177
                                hiTail = p;
178
                                ++hc;
179
                            }
180
                        }
181
                        // 扩容后树节点个数比较少的话，将红黑树转换为链表
182
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin<K,V>(lo) : t;
183
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin<K,V>(hi) : t;
184
                        setTabAt(nextTab, i, ln);
185
                        setTabAt(nextTab, i + n, hn);
186
                        setTabAt(tab, i, fwd);
187
                        advance = true;
188
                    }
189
                }
190
            }
191
        }
192
    }
193
}