并发安全ConcurrentHashMap集合深入学习(连续更新)

1.简单相识

ConcurrentHashMap是线程安全的HashMap
ConcurrentHashMap在JDK1.8中是以CAS + synchronized实现的线程安全
CAS：在没有hash冲突时（Node要放在数组上时）
synchronized：在出现hash冲突时（Node存放的位置已经有数据了）
2.存储

2.1存储结构

数组+链表+红黑树

2.2存储利用

2.2.1put方法

1. public V put(K key, V value) {
2.     return putVal(key, value, false);
3. }

复制代码

ConcurrentHashMap的数据是以键值对的情势存在的，所以参数是键值对的情势，
里面调了putVal方法，第三个参数默认fasle什么意思呢，false代表key一致时，直接覆盖数据，true代表key一致时，什么都不利用。

1. public V putIfAbsent(K key, V value) {
2.     return putVal(key, value, true);
3. }

复制代码

假如你想在key存在添加数据想不被覆盖的环境下可以调用putVal方法。
2.2.2putVal方法

这个方法内容有点多拆解成多个部门看
2.2.2.1 前置校验和散列算法

从校验可以看出key和value都不能为空，而HashMap的key和value都可以为空

1. final V putVal(K key, V value, boolean onlyIfAbsent) {
2.     if (key == null || value == null) throw new NullPointerException();
3.     int hash = spread(key.hashCode());
4.     int binCount = 0;
5.     // 省略。。。
6. }
8. // 计算当前Node的hash值的方法
9. static final int spread(int h) {
10.         // ^异或运算 相同为0 不同为1  &与运算 都为1时才为1
11.         // HASH_BITS: 01111111 11111111 11111111 11111111
12.         // 假设h：     00001101 00001101 00101111 10001111
13.         // h >>> 16:  00000000 00000000 00001101 00001101
14.         // ^:         00001101 00001101 00100010 10000010
15.         // &:         00001101 00001101 00100010 10000010
16.         return (h ^ (h >>> 16)) & HASH_BITS;
17. }

复制代码

2.2.2.2 添加数据到数组&&数组初始化

1. final V putVal(K key, V value, boolean onlyIfAbsent) {
2.         // 省略。。。
3.         for (Node<K,V>[] tab = table;;) {
4.                 // f: 当前数组i索引位置的Node对象
5.                 // n: 数组长度
6.                 // i: 当前Node需要存放的索引位置
7.                 // fh: 当前数组i索引位置上数据的hash值
8.                 Node<K,V> f; int n, i, fh;
9.                 // 判断数据是否为空
10.                 if (tab == null || (n = tab.length) == 0)
11.                         // 为空初始化数组长度
12.                     tab = initTable();
13.                 // 基于tabAt获取到i位置的数据
14.                 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
15.                         // i位置数据为空 CAS将数据放到i位置上
16.                     if (casTabAt(tab, i, null,
17.                                  new Node<K,V>(hash, key, value, null)))
18.                         break;                  
19.                 }
20.                 /**
21.                   * static final int MOVED     = -1; // 代表当前hash位置的数据正在扩容！
22.               * static final int TREEBIN   = -2; // 代表当前hash位置下挂载的是一个红黑树
23.               * static final int RESERVED  = -3; // 预留当前索引位置
24.               */
25.                 else if ((fh = f.hash) == MOVED)
26.                         // 帮助数组扩容
27.                     tab = helpTransfer(tab, f);
28.                 // 省略。。。
29.         }
30. }
32. /**
33. * sizeCtl: 数组初始化和扩容操作时的一个变量
34. *  -1  当前数组正在初始化
35. *   0  当前数组还没初始化
36. * <-1  低16位代表当前数组正在扩容线程个数（-2代表1个 -3 2个）
37. * > 0  当前数组的扩容阈值，或者数组的初始化容量
38. **/
39. private final Node<K,V>[] initTable() {
40.     Node<K,V>[] tab; int sc;
41.     // 再次判断数组有无初始化
42.     while ((tab = table) == null || tab.length == 0) {
43.             // 说明数组要么没有初始化 要么就是在扩容 总之就是数组还没准备好
44.         if ((sc = sizeCtl) < 0)
45.             Thread.yield(); // lost initialization race; just spin
46.         // 尝试初始化数组，如果修改成功代表数组没有初始化
47.         else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
48.             try {
49.                     // 再次判断数组有无初始化
50.                 if ((tab = table) == null || tab.length == 0) {
51.                         // 如果sc大于0 数组容量就是sc 不是默认容量16
52.                     int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
53.                     @SuppressWarnings("unchecked")
54.                     Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
55.                     // 将初始化的数组赋值给tab和table
56.                     table = tab = nt;
57.                     // 设置阈值 假设数组长度16 16 - 16 >>> 2 (10000 -> 00100) 16-4 12 阈值 12/16 75%
58.                     sc = n - (n >>> 2);
59.                 }
60.             } finally {
61.                     // 将赋值好的sc，设置给sizeCtl
62.                 sizeCtl = sc;
63.             }
64.             break;
65.         }
66.     }
67.     return tab;
68. }

复制代码

为什么长度为2的次幂?
因为要计算数据存放的索引位置 i = (n - 1) & hash
假如数组长度2的3次幂，-1之后变成0111，&之后得到的数，就会完备的得到原hashcode 值的低位值，不会受到与运算对数据的变化影响。
假如数组长度为7，-1之后变成0110 无论怎么与哈希值，就会发现下标为1，3，5，7的位置不绝存不上去数据，就会导致数组分散不均匀。
2.2.2.3 添加数据到链表

1. final V putVal(K key, V value, boolean onlyIfAbsent) {
2.     // 省略部分代码…………
3.     int binCount = 0;
4.     for (Node<K,V>[] tab = table;;) {
5.             //  n: 数组长度
6.         //  i: 当前Node需要存放的索引位置
7.         //  f: 当前数组i索引位置的Node对象
8.         // fh：当前数组i索引位置上数据的hash值
9.         Node<K,V> f; int n, i, fh;
10.         // 省略部分代码…………
11.         else {
12.             V oldVal = null;
13.             // 基于当前索引位置的Node，作为锁对象……
14.             synchronized (f) {
15.                 // 判断当前位置的数据还是之前的f么……（避免并发操作的安全问题）
16.                 if (tabAt(tab, i) == f) {
17.                     // 再次判断hash值是否大于0（不是树）
18.                     if (fh >= 0) {
19.                         // binCount设置为1（在链表情况下，记录链表长度的一个标识）
20.                         binCount = 1;
21.                         // 死循环，每循环一次，对binCount进行+1
22.                         for (Node<K,V> e = f;; ++binCount) {
23.                             K ek;
24.                             // 当前i索引位置的数据，是否和当前put的key的hash值一致
25.                             if (e.hash == hash &&
26.                                 // 如果当前i索引位置数据的key和put的key == 返回为true
27.                                 // 或者equals相等
28.                                 ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
29.                                 // key一致，可能需要覆盖数据！
30.                                 // 当前i索引位置数据的value复制给oldVal
31.                                 oldVal = e.val;
32.                                 // 如果传入的是false，代表key一致，覆盖value
33.                                 // 如果传入的是true，代表key一致，什么都不做！
34.                                 if (!onlyIfAbsent)
35.                                     // 覆盖value
36.                                     e.val = value;
37.                                 break;
38.                             }
39.                             // 拿到当前指定的Node对象
40.                             Node<K,V> pred = e;
41.                             // 将e指向下一个Node对象,如果next指向的是一个null，可以挂在当前Node下面
42.                             if ((e = e.next) == null) {
43.                                 // 将hash，key，value封装为Node对象，挂在pred的next上
44.                                 pred.next = new Node<K,V>(hash, key,
45.                                                           value, null);
46.                                 break;
47.                             }
48.                         }
49.                     }
50.                     // 省略部分代码…………
51.                 }
52.             }
53.             // binCount长度不为0
54.             if (binCount != 0) {
55.                 // binCount是否大于8（链表长度是否 >= 8）
56.                 if (binCount >= TREEIFY_THRESHOLD)
57.                     // 尝试转为红黑树或者扩容
58.                     // 基于treeifyBin方法和上面的if判断，可以得知链表想要转为红黑树，必须保证数组长度大于等于64，并且链表长度大于等于8
59.                     // 如果数组长度没有达到64的话，会首先将数组扩容
60.                     treeifyBin(tab, i);
61.                 // 如果出现了数据覆盖的情况，
62.                 if (oldVal != null)
63.                     // 返回之前的值
64.                     return oldVal;
65.                 break;
66.             }
67.         }
68.     }
69.     // 省略部分代码…………
70. }
72. // 为什么链表长度为8转换为红黑树，不是能其他数值嘛？
73. // 因为布松分布
74. The main disadvantage of per-bin locks is that other update
75. * operations on other nodes in a bin list protected by the same
76. * lock can stall, for example when user equals() or mapping
77. * functions take a long time.  However, statistically, under
78. * random hash codes, this is not a common problem.  Ideally, the
79. * frequency of nodes in bins follows a Poisson distribution
80. * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
81. * parameter of about 0.5 on average, given the resizing threshold
82. * of 0.75, although with a large variance because of resizing
83. * granularity. Ignoring variance, the expected occurrences of
84. * list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)). The
85. * first values are:
86. *
87. * 0:    0.60653066
88. * 1:    0.30326533
89. * 2:    0.07581633
90. * 3:    0.01263606
91. * 4:    0.00157952
92. * 5:    0.00015795
93. * 6:    0.00001316
94. * 7:    0.00000094
95. * 8:    0.00000006
96. * more: less than 1 in ten million

复制代码

2.3 扩容利用

1. // 在链表长度大于等于8时，尝试将链表转为红黑树
2. private final void treeifyBin(Node<K,V>[] tab, int index) {
3.     Node<K,V> b; int n, sc;
4.     // 数组不能为空
5.     if (tab != null) {
6.         // 数组的长度n，是否小于64
7.         if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
8.             // 如果数组长度小于64，不能将链表转为红黑树，先尝试扩容操作
9.             tryPresize(n << 1);
10.         // 省略部分代码……
11.     }
12. }

复制代码

2.3.1 扩容利用tryPresize初始化

1. // size是将之前的数组长度 左移 1位得到的结果
2. private final void tryPresize(int size) {
3.     // 如果扩容的长度达到了最大值，就使用最大值
4.     // 否则需要保证数组的长度为2的n次幂
5.     // 这块的操作，是为了初始化操作准备的，因为调用putAll方法时，也会触发tryPresize方法
6.     // 如果刚刚new的ConcurrentHashMap直接调用了putAll方法的话，会通过tryPresize方法进行初始化
7.     int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
8.         tableSizeFor(size + (size >>> 1) + 1);
9.     // 这些代码和initTable一模一样
10.     // 声明sc
11.     int sc;
12.     // 将sizeCtl的值赋值给sc，并判断是否大于0，这里代表没有初始化操作，也没有扩容操作
13.     while ((sc = sizeCtl) >= 0) {
14.         // 将ConcurrentHashMap的table赋值给tab，并声明数组长度n
15.         Node<K,V>[] tab = table; int n;
16.         // 数组是否需要初始化
17.         if (tab == null || (n = tab.length) == 0) {
18.             // 进来执行初始化
19.             // sc是初始化长度，初始化长度如果比计算出来的c要大的话，直接使用sc，如果没有sc大，
20.             // 说明sc无法容纳下putAll中传入的map，使用更大的数组长度
21.             n = (sc > c) ? sc : c;
22.             // 设置sizeCtl为-1，代表初始化操作
23.             if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
24.                 try {
25.                     // 再次判断数组的引用有没有变化
26.                     if (table == tab) {
27.                         // 初始化数组
28.                         Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
29.                         // 数组赋值
30.                         table = nt;
31.                         // 计算扩容阈值
32.                         sc = n - (n >>> 2);
33.                     }
34.                 } finally {
35.                     // 最终赋值给sizeCtl
36.                     sizeCtl = sc;
37.                 }
38.             }
39.         }
40.         // 如果计算出来的长度c如果小于等于sc，直接退出循环结束方法
41.         // 数组长度大于等于最大长度了，直接退出循环结束方法
42.         else if (c <= sc || n >= MAXIMUM_CAPACITY)
43.             break;
44.         // 省略部分代码
45.     }
46. }
48. // 将c这个长度设置到最近的2的n次幂的值，   15 - 16     17 - 32
49. // c == size + (size >>> 1) + 1
50. // size = 17
51. 00000000 00000000 00000000 00010001
52. +
53. 00000000 00000000 00000000 00001000
54. +
55. 00000000 00000000 00000000 00000001
56. // c = 26
57. 00000000 00000000 00000000 00011010
58. private static final int tableSizeFor(int c) {
59.     // 00000000 00000000 00000000 00011001
60.     int n = c - 1;
61.     // 00000000 00000000 00000000 00011001
62.     // 00000000 00000000 00000000 00001100
63.     // 00000000 00000000 00000000 00011101
64.     n |= n >>> 1;
65.     // 00000000 00000000 00000000 00011101
66.     // 00000000 00000000 00000000 00000111
67.     // 00000000 00000000 00000000 00011111
68.     n |= n >>> 2;
69.     // 00000000 00000000 00000000 00011111
70.     // 00000000 00000000 00000000 00000001
71.     // 00000000 00000000 00000000 00011111
72.     n |= n >>> 4;
73.     // 00000000 00000000 00000000 00011111
74.     // 00000000 00000000 00000000 00000000
75.     // 00000000 00000000 00000000 00011111
76.     n |= n >>> 8;
77.     // 00000000 00000000 00000000 00011111
78.     n |= n >>> 16;
79.     // 00000000 00000000 00000000 00100000
80.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
82. }

复制代码

2.3.2 tryPreSize方法-计算扩容戳而且检察BUG

1. private final void tryPresize(int size) {
2.     // n：数组长度
3.     while ((sc = sizeCtl) >= 0) {
4.         // 判断当前的tab是否和table一致，
5.         else if (tab == table) {
6.             // 计算扩容表示戳，根据当前数组的长度计算一个16位的扩容戳
7.             // 第一个作用是为了保证后面的sizeCtl赋值时，保证sizeCtl为小于-1的负数
8.             // 第二个作用用来记录当前是从什么长度开始扩容的
9.             int rs = resizeStamp(n);
10.             // BUG --- sc < 0，永远进不去~
11.             // 如果sc小于0，代表有线程正在扩容。
12.             if (sc < 0) {
13.                 // 省略部分代码……协助扩容的代码（进不来~~~~）
14.             }
15.             // 代表没有线程正在扩容，我是第一个扩容的。
16.             else if (U.compareAndSwapInt(this, SIZECTL, sc,
17.                                          (rs << RESIZE_STAMP_SHIFT) + 2))
18.                 // 省略部分代码……第一个扩容的线程……
19.         }
20.     }
21. }
22. // 计算扩容表示戳
23. // 32 =  00000000 00000000 00000000 00100000
24. // Integer.numberOfLeadingZeros(32) = 26
25. // 1 << (RESIZE_STAMP_BITS - 1)
26. // 00000000 00000000 10000000 00000000
27. // 00000000 00000000 00000000 00011010
28. // 00000000 00000000 10000000 00011010
29. static final int resizeStamp(int n) {
30.     return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
31. }

复制代码

2.3.3 tryPreSize方法-对sizeCtl的修改以及条件判定的BUG

1. private final void tryPresize(int size) {
2.     // sc默认为sizeCtl
3.     while ((sc = sizeCtl) >= 0) {
4.         else if (tab == table) {
5.             // rs：扩容戳  00000000 00000000 10000000 00011010
6.             int rs = resizeStamp(n);
7.             if (sc < 0) {
8.                 // 说明有线程正在扩容，过来帮助扩容
9.                 Node<K,V>[] nt;
10.                 // 依然有BUG
11.                 // 当前线程扩容时，老数组长度是否和我当前线程扩容时的老数组长度一致
12.                 // 00000000 00000000 10000000 00011010
13.                 if ((sc >>> RESIZE_STAMP_SHIFT) != rs  
14.                     // 10000000 00011010 00000000 00000010
15.                     // 00000000 00000000 10000000 00011010
16.                     // 这两个判断都是有问题的，核心问题就应该先将rs左移16位，再追加当前值。
17.                     // 这两个判断是BUG
18.                     // 判断当前扩容是否已经即将结束
19.                     || sc == rs + 1   // sc == rs << 16 + 1 BUG
20.                     // 判断当前扩容的线程是否达到了最大限度
21.                     || sc == rs + MAX_RESIZERS   // sc == rs << 16 + MAX_RESIZERS BUG
22.                     // 扩容已经结束了。
23.                     || (nt = nextTable) == null
24.                     // 记录迁移的索引位置，从高位往低位迁移，也代表扩容即将结束。
25.                     || transferIndex <= 0)
26.                     break;
27.                 // 如果线程需要协助扩容，首先就是对sizeCtl进行+1操作，代表当前要进来一个线程协助扩容
28.                 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
29.                     // 上面的判断没进去的话，nt就代表新数组
30.                     transfer(tab, nt);
31.             }
32.             // 是第一个来扩容的线程
33.             // 基于CAS将sizeCtl修改为  10000000 00011010 00000000 00000010
34.             // 将扩容戳左移16位之后，符号位是1，就代码这个值为负数
35.             // 低16位在表示当前正在扩容的线程有多少个,
36.             // 为什么低位值为2时，代表有一个线程正在扩容
37.             // 每一个线程扩容完毕后，会对低16位进行-1操作，当最后一个线程扩容完毕后，减1的结果还是-1，
38.             // 当值为-1时，要对老数组进行一波扫描，查看是否有遗漏的数据没有迁移到新数组
39.             else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))
40.                 // 调用transfer方法，并且将第二个参数设置为null，就代表是第一次来扩容！
41.                 transfer(tab, null);
42.         }
43.     }
44. }

复制代码

2.3.4 transfer方法-计算每个线程迁徙的长度

1. // 开始扩容   tab=oldTable
2. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
3.     // n = 数组长度
4.     // stride = 每个线程一次性迁移多少数据到新数组
5.     int n = tab.length, stride;
6.     // 基于CPU的内核数量来计算，每个线程一次性迁移多少长度的数据最合理
7.     // NCPU = 4
8.     // 举个栗子：数组长度为1024 - 512 - 256 - 128 / 4 = 32
9.     // MIN_TRANSFER_STRIDE = 16,为每个线程迁移数据的最小长度
10.     if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
11.         stride = MIN_TRANSFER_STRIDE;
12.     // 根据CPU计算每个线程一次迁移多长的数据到新数组，如果结果大于16，使用计算结果。 如果结果小于16，就使用最小长度16
13. }

复制代码

2.3.5 transfer方法-构建新数组并检察标识属性

1. // 以32长度数组扩容到64位例子
2. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
3.     // n = 老数组长度   32
4.     // stride = 步长   16
5.     // 第一个进来扩容的线程需要把新数组构建出来
6.     if (nextTab == null) {
7.         try {
8.             // 将原数组长度左移一位，构建新数组长度
9.             Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
10.             // 赋值操作
11.             nextTab = nt;
12.         } catch (Throwable ex) {   
13.             // 到这说明已经达到数组长度的最大取值范围
14.             sizeCtl = Integer.MAX_VALUE;
15.             // 设置sizeCtl后直接结束
16.             return;
17.         }
18.         // 将成员变量的新数组赋值
19.         nextTable = nextTab;
20.         // 迁移数据时，用到的标识，默认值为老数组长度
21.         transferIndex = n;   // 32
22.     }
23.     // 新数组长度
24.     int nextn = nextTab.length;  // 64
25.     // 在老数组迁移完数据后，做的标识
26.     ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
27.     // 迁移数据时，需要用到的标识
28.     boolean advance = true;
29.     boolean finishing = false;
30.     // 省略部分代码
31. }

复制代码

2.3.6 transfer方法-线程领取迁徙任务

1. // 以32长度扩容到64位为例子
2. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
3.     // n：32
4.     // stride：16
5.     int n = tab.length, stride;
6.     if (nextTab == null) {
7.         // 省略部分代码…………
8.         // nextTable：新数组
9.         nextTable = nextTab;
10.         // transferIndex：0
11.         transferIndex = n;
12.     }
13.     // nextn：64
14.     int nextn = nextTab.length;
15.     ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
16.     // advance：true，代表当前线程需要接收任务，然后再执行迁移，  如果为false，代表已经接收完任务
17.     boolean advance = true;
18.     // finishing：false，是否迁移结束！
19.     boolean finishing = false;
20.     // 循环……
21.     // i = 15     代表当前线程迁移数据的索引值！！
22.     // bound = 0
23.     for (int i = 0, bound = 0;;) {
24.         // f = null
25.         // fh = 0
26.         Node<K,V> f; int fh;
27.         // 当前线程要接收任务
28.         while (advance) {
29.             // nextIndex = 16
30.             // nextBound = 16
31.             int nextIndex, nextBound;
32.             // 第一次进来，这两个判断肯定进不去。
33.             // 对i进行--，并且判断当前任务是否处理完毕！
34.             if (--i >= bound || finishing)
35.                 advance = false;
36.             // 判断transferIndex是否小于等于0，代表没有任务可领取，结束了。
37.             // 在线程领取任务会，会对transferIndex进行修改，修改为transferIndex - stride
38.             // 在任务都领取完之后，transferIndex肯定是小于等于0的，代表没有迁移数据的任务可以领取
39.             else if ((nextIndex = transferIndex) <= 0) {
40.                 i = -1;
41.                 advance = false;
42.             }
43.             // 当前线程尝试领取任务
44.             else if (U.compareAndSwapInt
45.                      (this, TRANSFERINDEX, nextIndex,
46.                       nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
47.                 // 对bound赋值
48.                 bound = nextBound;
49.                 // 对i赋值
50.                 i = nextIndex - 1;
51.                 // 设置advance设置为false，代表当前线程领取到任务了。
52.                 advance = false;
53.             }
54.         }
55.         // 开始迁移数据，并且在迁移完毕后，会将advance设置为true
56.   
57.     }
58. }

复制代码

2.3.7 transfer方法-迁徙竣事利用

1. // 以32长度扩容到64位为例子
2. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
3.     for (int i = 0, bound = 0;;) {
4.         while (advance) {
5.         // 判断扩容是否已经结束！
6.         // i < 0：当前线程没有接收到任务！
7.         // i >= n: 迁移的索引位置，不可能大于数组的长度，不会成立
8.         // i + n >= nextn：因为i最大值就是数组索引的最大值，不会成立
9.         if (i < 0 || i >= n || i + n >= nextn) {
10.             // 如果进来，代表当前线程没有接收到任务
11.             int sc;
12.             // finishing为true，代表扩容结束
13.             if (finishing) {
14.                 // 将nextTable新数组设置为null
15.                 nextTable = null;
16.                 // 将当前数组的引用指向了新数组~
17.                 table = nextTab;
18.                 // 重新计算扩容阈值    64 - 16 = 48
19.                 sizeCtl = (n << 1) - (n >>> 1);
20.                 // 结束扩容
21.                 return;
22.             }
23.             // 当前线程没有接收到任务，让当前线程结束扩容操作。
24.             // 采用CAS的方式，将sizeCtl - 1，代表当前并发扩容的线程数 - 1
25.             if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
26.                 // sizeCtl的高16位是基于数组长度计算的扩容戳，低16位是当前正在扩容的线程个数
27.                 if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
28.                     // 代表当前线程并不是最后一个退出扩容的线程，直接结束当前线程扩容
29.                     return;
30.                 // 如果是最后一个退出扩容的线程，将finishing和advance设置为true
31.                 finishing = advance = true;
32.                 // 将i设置为老数组长度，让最后一个线程再从尾到头再次检查一下，是否数据全部迁移完毕。
33.                 i = n;
34.             }
35.         }
36.         // 开始迁移数据，并且在迁移完毕后，会将advance设置为true
37.     }
38. }

复制代码

2.3.8 transfer方法-迁徙数据（链表）

1. // 以32长度扩容到64位为例子
2. private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
3.     // 省略部分代码…………
4.     for (int i = 0, bound = 0;;) {
5.         // 省略部分代码…………
6.         if (i < 0 || i >= n || i + n >= nextn) {   
7.              // 省略部分代码…………
8.         }
9.         // 开始迁移数据，并且在迁移完毕后，会将advance设置为true
10.         // 获取指定i位置的Node对象，并且判断是否为null
11.         else if ((f = tabAt(tab, i)) == null)
12.             // 当前桶位置没有数据，无需迁移，直接将当前桶位置设置为fwd
13.             advance = casTabAt(tab, i, null, fwd);
14.         // 拿到当前i位置的hash值，如果为MOVED，证明数据已经迁移过了。
15.         else if ((fh = f.hash) == MOVED)
16.             // 一般是给最后扫描时，使用的判断，如果迁移完毕，直接跳过当前位置。
17.             advance = true; // already processed
18.         else {
19.             // 当前桶位置有数据，先锁住当前桶位置。
20.             synchronized (f) {
21.                 // 判断之前取出的数据是否为当前的数据。
22.                 if (tabAt(tab, i) == f) {
23.                     // ln：null  - lowNode
24.                     // hn：null  - highNode
25.                     Node<K,V> ln, hn;
26.                     // hash大于0，代表当前Node属于正常情况，不是红黑树，使用链表方式迁移数据
27.                     if (fh >= 0) {
28.                         // lastRun机制
29.                         //   000000000010000
30.                         // 这种运算结果只有两种，要么是0，要么是n
31.                         int runBit = fh & n;
32.                         // 将f赋值给lastRun
33.                         Node<K,V> lastRun = f;
34.                         // 循环的目的就是为了得到链表下经过hash & n结算，结果一致的最后一些数据
35.                         // 在迁移数据时，值需要迁移到lastRun即可，剩下的指针不需要变换。
36.                         for (Node<K,V> p = f.next; p != null; p = p.next) {
37.                             int b = p.hash & n;
38.                             if (b != runBit) {
39.                                 runBit = b;
40.                                 lastRun = p;
41.                             }
42.                         }
43.                         // runBit == 0，赋值给ln
44.                         if (runBit == 0) {
45.                             ln = lastRun;
46.                             hn = null;
47.                         }
48.                         // rubBit == n,赋值给hn
49.                         else {
50.                             hn = lastRun;
51.                             ln = null;
52.                         }
53.                         // 循环到lastRun指向的数据即可，后续不需要再遍历
54.                         for (Node<K,V> p = f; p != lastRun; p = p.next) {
55.                             // 获取当前Node的hash值，key值，value值。
56.                             int ph = p.hash; K pk = p.key; V pv = p.val;
57.                             // 如果hash&n为0，挂到lowNode上
58.                             if ((ph & n) == 0)
59.                                 ln = new Node<K,V>(ph, pk, pv, ln);
60.                             // 如果hash&n为n，挂到highNode上
61.                             else
62.                                 hn = new Node<K,V>(ph, pk, pv, hn);
63.                         }
64.                         // 采用CAS的方式，将ln挂到新数组的原位置
65.                         setTabAt(nextTab, i, ln);
66.                         // 采用CAS的方式，将hn挂到新数组的原位置 + 老数组长度
67.                         setTabAt(nextTab, i + n, hn);
68.                         // 采用CAS的方式，将当前桶位置设置为fwd
69.                         setTabAt(tab, i, fwd);
70.                         // advance设置为true，保证可以进入到while循环，对i进行--操作
71.                         advance = true;
72.                     }
73.                     // 省略迁移红黑树的操作
74.                 }
75.             }
76.         }
77.     }
78. }

复制代码

2.3.9 helpTransfer方法-帮助扩容

1. // 在添加数据时，如果插入节点的位置的数据，hash值为-1，代表当前索引位置数据已经被迁移到了新数组
2. // tab：老数组
3. // f：数组上的Node节点
4. final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
5.     // nextTab：新数组
6.     // sc：给sizeCtl做临时变量
7.     Node<K,V>[] nextTab; int sc;
8.     // 第一个判断：老数组不为null
9.     // 第二个判断：新数组不为null  （将新数组赋值给nextTab）
10.     if (tab != null &&
11.         (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
12.         // ConcurrentHashMap正在扩容
13.         // 基于老数组长度计算扩容戳
14.         int rs = resizeStamp(tab.length);
15.         // 第一个判断：fwd中的新数组，和当前正在扩容的新数组是否相等。    相等：可以协助扩容。不相等：要么扩容结束，要么开启了新的扩容
16.         // 第二个判断：老数组是否改变了。     相等：可以协助扩容。不相等：扩容结束了
17.         // 第三个判断：如果正在扩容，sizeCtl肯定为负数，并且给sc赋值
18.         while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) {
19.             // 第一个判断：将sc右移16位，判断是否与扩容戳一致。 如果不一致，说明扩容长度不一样，退出协助扩容
20.             // 第二个、三个判断是BUG：
21.             /*
22.                 sc == rs << 16 + 1 ||      如果+1和当前sc一致，说明扩容已经到了最后检查的阶段
23.                 sc == rs << 16 + MAX_RESIZERS ||    判断协助扩容的线程是否已经达到了最大值
24.             */
25.             // 第四个判断：transferIndex是从高索引位置到低索引位置领取数据的一个核心属性，如果满足 小于等于0，说明任务被领光了。
26.             if ((sc >>> RESIZE_STAMP_SHIFT) != rs ||
27.                 sc == rs + 1 ||
28.                 sc == rs + MAX_RESIZERS ||
29.                 transferIndex <= 0)
30.                 // 不需要协助扩容
31.                 break;
32.             // 将sizeCtl + 1，进来协助扩容
33.             if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
34.                 // 协助扩容
35.                 transfer(tab, nextTab);
36.                 break;
37.             }
38.         }
39.         return nextTab;
40.     }
41.     return table;
42. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。