深入浅出 JAVA 之集合 - ConcurrentHashMap
文章目录
!版权声明：本博客内容均为原创,每篇博文作为知识积累,写博不易,转载请注明出处。
系统环境:
- JDK 版本: OpenJDK 8
一、ConcurrentHashMap 概述
ConcurrentHashMap 和 HashMap 一样，是一个实现了 Map 接口，用于存储键值对数据的集合。
不过 ConcurrentHashMap 和 HashMap 又不完全相同，比如 ConcurrentHashMap 相对于 HashMap 具有更好的线程安全性和并发性能，并提供了一些额外的并发操作方法和迭代器的一致性保证，可以在多线程环境下保证集合的线程安全。然而也正是由于引入了额外的同步机制，ConcurrentHashMap 的性能可能略低于 HashMap。
所有，ConcurrentHashMap 可以简单的认为是一个和 HashMap 类似的线程安全的集 Map 集合，在选择使用 ConcurrentHashMap 还是 HashMap 时，可以根据具体的使用场景和并发需求进行综合考虑。
二、ConcurrentHashMap 底层结构
在 JDK 8 中，ConcurrentHashMap 底层结构和 HashMap 相同，都是采用了 数组 (table)、链表 和 红黑树 组成。其结构如下图所示:
数组 table 是由一个个 桶 组成，所以也常称数组为 桶数组。并且每个 桶 都关联了一个 链表 或者 红黑树 结构，这主要是用于解决哈希表结构中的哈希冲突。其中链表使用 Node 类型节点组成，红黑树则使用 TreeNode 节点组成，两种类型节点中都存储了键值对的 key、value 以及 hash 信息，并且每个节点还使用 next 属性进行关联。
三、ConcurrentHashMap 属性
3.1 ConcurrentHashMap 中的默认常量值
1/**
2 * 集合最大容量限制.
3 */
4private static final int MAXIMUM_CAPACITY = 1 << 30;
5
6/**
7 * 默认初始容量。该值必须是 2 的 n 次幂，默认值为 16
8 */
9private static final int DEFAULT_CAPACITY = 16;
10
11/**
12 * 数组的最大长度
13 */
14static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
15
16/**
17 * 默认的并行度，为了兼容 JDK7 版本中的 Segment
18 */
19private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
20
21/**
22 * 扩容因子，当元素个数达到0.75*数组长度的时候触发扩容，也是jdk1.7使用，jdk1.8直接使用位操作计算出扩容阈值
23 */
24private static final float LOAD_FACTOR = 0.75f;
25
26/**
27 * 桶中-链表转换为红黑树的阈值
28 */
29static final int TREEIFY_THRESHOLD = 8;
30
31/**
32 * 桶中-红黑树还原为链表的阈值
33 */
34static final int UNTREEIFY_THRESHOLD = 6;
35
36/**
37 * 链表转化为红黑树时对集合最小容量的限制值，如果集合容量小于该值则链表不会转换为红黑树
38 */
39static final int MIN_TREEIFY_CAPACITY = 64;
40
41/**
42 * 并发扩容时每个线程最少处理16个桶
43 */
44private static final int MIN_TRANSFER_STRIDE = 16;
45
46/**
47 * 这三个常量控制并发扩容的结束，其实就是开始扩容的时候设置sizeCtl成一个负数，每次加入一个线程去扩容就sizeCtl++，
48 * 每次一个线程扩容结束就sizeCtl–-,那么当所有线程扩容结束后sizeCtl就等于最开始设置的那个负数
49 */
50private static int RESIZE_STAMP_BITS = 16;
51private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
52private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
53
54/**
55 * 当node节点的hash值 为-1时，表示当前节点为FWD节点
56 */
57static final int MOVED = -1;
58
59/**
60 * 当node节点的hash值 为-2时， 表示当前节点已经树化,且当前节点为TreeBin对象,TreeBin对象代理操作红黑树
61 */
62static final int TREEBIN = -2;
63
64/**
65 * 标识为ReservationNode节点（hash=-3），用于map.compute操作
66 */
67static final int RESERVED = -3;
68
69/**
70 * 可以将一个负数通过位与运算后得到正数，但是不是取绝对值
71 */
72static final int HASH_BITS = 0x7fffffff;
3.2 ConcurrentHashMap 中的成员变量
1/**
2 * 系统CPU的数量
3 */
4static final int NCPU = Runtime.getRuntime().availableProcessors();
5
6/**
7 * .散列表，长度一定是2次方数
8 */
9transient volatile Node<K,V>[] table;
10
11/**
12 * 扩容过程中，会将扩容中的新table 赋值给nextTable 保持引用，扩容结束之后，这里会被设置为null
13 */
14private transient volatile Node<K,V>[] nextTable;
15
16/**
17 * 未发生竞争时，或者当前LongAdder 处于加锁状态时，增量累加到baseCount
18 */
19private 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 */
33private transient volatile int sizeCtl;
34
35/**
36 * 扩容过程中，记录当前进度。所有线程都需要从transferIndex中分配区间任务，去执行自己的任务
37 */
38private transient volatile int transferIndex;
39
40/**
41 * LongAdder中的 cellsBuzy 0表示当前LongAdder对象无锁状态，1表示当前LongAdder对象加锁状态
42 */
43private transient volatile int cellsBusy;
44
45/**
46 * LongAdder 中的cells数组，当baseCount发生竞争后，会创建cells数组.线程会通过计算hash值取到自己的cell，将增量累加到指定cell中
47 */
48private transient volatile CounterCell[] counterCells;
四、ConcurrentHashMap 关键方法
4.1 构造方法 ConcurrentHashMap
(1) 无参构造方法
1/**
2 * 无参构造方法
3 */
4public ConcurrentHashMap() {
5}
(2) 支持配置初始化容量的构造方法
1/**
2 * 支持配置初始化容量的构造方法
3 *
4 * @param initialCapacity 初始化容量
5 * @throws IllegalArgumentException 非法参数异常
6 */
7public ConcurrentHashMap(int initialCapacity) {
8 if (initialCapacity < 0)
9 throw new IllegalArgumentException();
10 int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
11 MAXIMUM_CAPACITY :
12 tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
13 this.sizeCtl = cap;
14}
(3) 支持配置初始化容量与负载因子的构造方法
支持配置初始化容量与负载因子的构造方法，可以配置 初始化容量 和 负载因子，不过在对参数进行配置前需要对参数进行一系列校验。
HashMap(int initialCapacity, float loadFactor)
1/**
2 * 支持配置初始化容量与负载因子的构造方法
3 *
4 * @param initialCapacity 初始化容量
5 * @param loadFactor 负载因子
6 * @throws IllegalArgumentException 非法参数异常 (如果初始容量为负数或者负载因子为负数，则抛出该异常)
7 */
8public HashMap(int initialCapacity, float loadFactor) {
9 // 如果初始化容量为负数，则抛出 IllegalArgumentException 异常
10 if (initialCapacity < 0) {
11 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
12 }
13 // 如果初始化容量大于 MAXIMUM_CAPACITY 值，则就设置初始化容量为 MAXIMUM_CAPACITY
14 if (initialCapacity > MAXIMUM_CAPACITY) {
15 initialCapacity = MAXIMUM_CAPACITY;
16 }
17 // 如果负载因子为负数，或者非数字 (NaN)，则抛出 IllegalArgumentException 异常
18 if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
19 throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
20 }
21 // 设置【负载因子】和【扩容阈值】变量
22 this.loadFactor = loadFactor;
23 this.threshold = tableSizeFor(initialCapacity);
24}
tableSizeFor(int c)
1/**
2 * 返回一个大于等于且最接近 cap 的 2 的幂次方:
3 * - 比如传入初始化容量 cap = 9，则返回 2^4，即 16
4 * - 比如传入初始化容量 cap = 25，则返回 2^5，即 32
5 *
6 * @param cap 传入构造方法中初始化容量
7 * @return 传入初始化容量 cap 的 2 的幂次方
8 */
9private 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}
(4) 支持根据已有 Map 集合创建新集合的构造方法
ConcurrentHashMap(Map<? extends K, ? extends V> m)
1/**
2 * 支持根据已有 Map 集合创建新集合的构造方法
3 *
4 * @param m 已有的 Map 集合
5 * @throws NullPointerException 空指针异常
6 */
7public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
8 this.sizeCtl = DEFAULT_CAPACITY;
9 putAll(m);
10}
putAll(Map<? extends K, ? extends V> m)
1/**
2 * 将插入的 Map 集合中的数据转移到当前集合中
3 *
4 * @param m 需要将数据插入到新集合中的 Map 集合
5 */
6public 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}
4.2 初始化数组方法 initTable()
initTable()
1/**
2 * 初始化数组
3 *
4 * @return 初始后的数组
5 */
6private 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}
tabAt(Node<K,V>[] tab, int i)
1/**
2 * 获取 tab 数组中下标为 i 的元素。
3 *
4 * 这里之所以使用 getObjectVolatile() 方法获取数组中指定位置的元素，这是因为该方法属于 volatile 类型方法，
5 * 可以保证数组中数据的可见性，其它线程对当前数组进行修改后，当前线程可以马上观察到最新的改动。
6 *
7 * @param tab 待操作的数组
8 * @param i 数组的下标位置
9 * @return 数组指定下标位置的元素
10 */
11static 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}
casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v)
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 */
12static 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}
4.3 插入方法 putVal(K key, V value)
put(K key, V value)
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 * @throws NullPointerException 空指针异常
10 */
11public V put(K key, V value) {
12 return putVal(key, value, false);
13}
putVal(K key, V value, boolean onlyIfAbsent)
1/**
2 * 实现 Map.put() 和相关方法。
3 *
4 * @param key 待插入的键
5 * @param value 待插入的值
6 * @param onlyIfAbsent 如果为 true 则不更改现有的值
7 * @return 如果插入的 Key 已经存在，则返回已存在 Key 的节点值，否则返回 null
8 */
9final 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}
4.4 删除方法 remove(Object key)
remove(Object key)
1/**
2 * 从集合中删除指定 key 对应的键值对数据
3 *
4 * @param key 待删除的键值对 key
5 * @return 判断集合中存在指定的 key 对应的键值对数据，不存在则返回 null，存在则返回键值对的 value
6 * @throws NullPointerException 空指针异常
7 */
8public V remove(Object key) {
9 return replaceNode(key, null, null);
10}
replaceNode(Object key, V value, Object cv)
1/**
2 * 替换/删除方法
3 * - 如果传入参数 value 为空，则执行删除操作；
4 * - 如果传入参数 value 不为空，则执行替换操作，将 cv 替换为 value；
5 *
6 * @param key 键值对 key
7 * @param value 键值对 value
8 * @param cv 待替换的旧值
9 * @return 如果执行删除操作则返回 null，如果执行替换操作则返回旧值
10 */
11final 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}
4.5 协助扩容方法 helpTransfer(Node<K,V>[] tab, Node<K,V> f)
1 /**
2 * 协助扩容
3 *
4 * @param tab 待操作的数组
5 * @param f 需要查找的节点
6 * @return 如果扩容结束则返回当前 tabel 数组，否则返回新的 table 数组
7 */
8final 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}
4.6 链表转红黑树方法 treeifyBin(Node<K,V>[] tab, int index)
1/**
2 * 链表转换为红黑树
3 *
4 * @param tab 数组 table
5 * @param index 数组索引位置
6 */
7private 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}
4.7 红黑树转链表方法 untreeify(Node<K,V> b)
1/**
2 * 取消树化，将红黑树转换为链表
3 *
4 * @param b 待转换的红黑树节点
5 * @return 链表
6 */
7static <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}
4.8 尝试扩容方法 tryPresize(int size)
1/**
2 * 尝试调整当前集合数组 table 的大小，以容纳给定数量的元素。
3 *
4 * @param size 带插入集合的大小
5 */
6private 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}
4.9 扩容方法 transfer(Node<K,V>[] tab, Node<K,V>[] nextTab)
1/**
2 * 扩容方法
3 *
4 * @param tab 当前 table
5 * @param nextTab 扩容后的 table
6 */
7private 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}
--- END ---
!版权声明：本博客内容均为原创,每篇博文作为知识积累,写博不易,转载请注明出处。