HashMap

结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
transient Node<K,V>[] table;

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
...
}
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev;
boolean red;
...
}

HashMap在JDK1.8中的结构为数组(默认长度:16)+ 单向链表 + 红黑树,在JDK1.7中没有红黑树。

Hash算法

Hash算法是用于得到数组的下标位置的前戏

①根据hash算法得到一个整形数
②控制在数组的长度之间(默认长度16,则为0-15)之间
③Key.hashCode int 32位,高16位和低16位异或运算。得到的结果就是hash算法。

1
2
3
4
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

put()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断table是否为空,为空则初始化
if ((tab = table) == null || (n = tab.length) == 0)
//初始化
n = (tab = resize()).length;
//判断数组的节点位置是否为空,为空则将新节点插入
if ((p = tab[i = (n - 1) & hash]) == null)
//将新节点加入数组
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//判断数组的下标位置上有节点存在,且key相同,则覆盖节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果节点是红黑树结构,则加入树中
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//将节点加入链表中
else {
//循环链表
for (int binCount = 0; ; ++binCount) {
//将不同的key插入链表尾部
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表长度超过8,则转为红黑树结构
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
//判断链表中是否有相同的key,如果有则替换
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
}
...
//判断数组大小是否需要扩容
if (++size > threshold)
resize();
...
}
  1. 判断table是否为空,调用resize()方法进行初始化
  2. 计算出下标的位置,hash值&(数组长度-1),如果这个位置没有节点则直接插入节点
  3. 如果下标的位置有节点,则判断key是否相同,相同覆盖节点,否则插入节点
  4. 插入节点时,如果是红黑树结构,则插入红黑树中;如果是链表结构,则插入链表尾部,如果链表的长度大于8,则将链表转为红黑树结构;如果删除节点时,红黑树的结构小于6,则重新转为链表结构
  5. 插入节点后判断数组大小是否需要扩容,是否扩容由扩容因子决定,当前大小/16=扩容因子,扩容按默认容量的2的倍数扩容,扩容后将原来的数组数据移到当前数组中
  6. 数组扩容后转移部分链表中的数据,判断hash倒数第5位为0即要移动到新的位置,否则不变,并且只可能在原来的位置或原来的位置+原来数组长度。

并发缺陷

resize()调整 HashMap 大小的时候,存在条件竞争。

因为如果两个线程都发现 HashMap 需要重新调整大小了,它们会同时试着调整大小。

在调整大小的过程中,存储在链表中的元素的次序会反过来。因为移动到新的 bucket 位置的时候,HashMap 并不会将元素放在链表的尾部,而是放在头部。如果条件竞争发生了,会造成链表出现环形。

所以在多线程并发的环境下不能使用 HashMap,推荐使用ConcurrentHashmap。

知识点

为何HashMap的数组长度一定是2的次幂?

hashMap的数组长度保持2的次幂,比如16的二进制表示为 10000,那么length-1就是15,二进制为01111,同理扩容后的数组长度为32,二进制表示为100000,length-1为31,二进制表示为011111。这样会保证低位全为1,而扩容后只有一位差异,也就是多出了最左位的1,这样在通过 h&(length-1)的时候,只要h对应的最左边的那一个差异位为0,就能保证得到的新的数组索引和老数组索引一致。

以及,数组长度保持2的次幂,length-1的低位都为1,会使得获得的数组索引index更加均匀。

上面的&运算,高位是不会对结果产生影响的,我们只关注低位bit,如果低位全部为1,那么对于h低位部分来说,任何一位的变化都会对结果产生影响,也就是说,要得到index=21这个存储位置,h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。

如果不是2的次幂,也就是低位不是全为1此时,要使得index=21,h的低位部分不再具有唯一性了,哈希冲突的几率会变的更大,同时,index对应的这个bit位无论如何不会等于1了,而对应的那些数组位置也就被白白浪费了。

HashMap的链表是从头插入还是从尾部插入的

在jdk1.8之前是插入头部的,在jdk1.8中是插入尾部的。

ConcurrentHashmap

JDK1.7使用Segment 分段锁技术,这里就不过多讨论了,下面主要介绍在JDK1.8进行优化后的源码实现。

JDK1.8中的CocurrentHashMap 抛弃了原有的 Segment 分段锁,采用了 CAS + synchronized 来保证并发安全性。其中的 val nexttable都用了 volatile 修饰,保证了可见性。

在JDK1.8中的CocurrentHashMap最大的特点是引入了 cas(Compare And Swap),简单的说就是比较并交换。

cas有3个操作数,内存值 V、旧的预期值 A、要修改的新值 B。当且仅当预期值 A 和内存值 V 相同时,将内存值V修改为 B,否则什么都不做。

结构

结构与Hashmap基本相同,但是ConcurrentHashmap的table字段加了volatile关键字修饰保证可见性。

1
transient volatile Node<K,V>[] table;

同时,ConcurrentHashmap的Node中的val和next也用了 volatile 修饰。

1
2
3
4
5
6
7
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
...
}

字段sizeCtl用来控制表初始化和扩容,默认值为0,功能如下

1
private transient volatile int sizeCtl;
  • 当sizeCtl为-1时,表示table正在初始化
  • 当sizeCtl小于-1时为 -(1+n),n表示有n个线程正在进行扩容操作
  • 如果 table 未初始化,表示table需要初始化的大小
  • 如果 table 初始化完成,表示table的容量,默认是table大小的0.75倍

put()方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
//非空判断
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode()); //计算hash值
int binCount = 0; //用来记录链表长度
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//检查table是否为空,为空则进行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//判断节点是否为空,为空则使用cas存储节点
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果该下标的节点为空,则cas插入即可;如果cas失败,说明存在竞争,则进入下一次循环
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break;
}
//如果节点正在扩容,则协助扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//对节点加锁
synchronized (f) {
//如果table[i]为树节点,则将此节点插入树中即可。
//如果table[i]的节点是链表节点,则插入链表中。
...
}
//检查是否需要转化为树,如果需要则进行转化
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//调用addCount()方法增加元素个数
addCount(1L, binCount);
return null;
}
  1. 检查table是否初始化了,如果没有,则调用initTable()方法进行初始化
  2. 根据key的hash值计算出其应该在table中储存的位置i,取出table[i]的节点用f表示。有以下三种情况:
    1. 如果table[i]位置的节点为空,没有发生碰撞, 则利用cas操作直接存储在该位置,如果cas操作成功则退出死循环,如果cas操作失败则进入下一次循环。
    2. 如果table[i]已经有其它节点,发生碰撞,则检查table[i]的节点的hash是否等于MOVED,如果等于,则检测到正在扩容,则帮助其扩容。如果table[i]的节点的hash值不等于MOVED,如果table[i]为链表节点,则将此节点插入链表中即可。
    3. 如果table[i]为树节点,则将此节点插入树中即可。如果table[i]的节点是链表节点,则插入链表中,然后检查是否需要转化为树,如果需要则进行转化

addCount()方法

在putVal()方法完成后,会调用addCount()方法来增加ConcurrentHashMap中元素的个数,并且可能会触发扩容操作。putVal()方法调用addCount()方法传递的两个参数值分别是1 和 binCount(链表长度)。

addCount()方法有两个参数x和check,x 表示这次需要在表中增加的元素个数,check 参数表示是否需要进行扩容检查,大于等于 0 都需要进行检查 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
//判断 counterCells 是否为空
//如果为空,则通过cas操作修改baseCount变量,进行原子增加操作
//如果不为空或cas失败,则通过CounterCell记录元素数量
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true; //标识是否没有冲突,默认没有冲突
//如果counterCells为空则直接调用fullAddCount()方法
//从counterCells中随机取出一个数组的位置为空,直接调用fullAddCount()方法
//cas修改CounterCell随机位置的值,修改失败调用fullAddCount()方法
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))){
//调用fullAddCount()方法
fullAddCount(x, uncontended);
return;
}
//如果链表长度小于等于 1,不需要考虑扩容
if (check <= 1)
return;
//统计 ConcurrentHashMap 元素个数
s = sumCount();
}
...
}

CounterCells介绍

ConcurrentHashMap 采用 CounterCell 数组来记录元素个数,也就是分片的方法来记录元素数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//标识当前cell数组是否在初始化或扩容中的cas标志位
private transient volatile int cellsBusy;

// counterCells 数组,元素的数量分别存在每个CounterCell中
private transient volatile CounterCell[] counterCells;

@sun.misc.Contended static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}

//CounterCell数组的每个元素,都存储一个元素个数,循环累加得到最终的总数
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}

fullAddCount()方法

fullAddCount()方法主要用来初始化 CounterCell,记录元素个数,包含扩容,初始化等操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
//获取当前线程的probe的值,如果值为0,则初始化当前线程的prob 的值,probe就是随机数
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true; // 重新生成probe,未冲突标志位设置为 true
}
boolean collide = false;
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
//如果counterCells已经被初始化了
if ((as = counterCells) != null && (n = as.length) > 0) {
//通过当前线程probe进行与运算,获得cells 的下标元素
if ((a = as[(n - 1) & h]) == null) {
//cellsBusy为0表示 counterCells 不在初始化或者扩容状态下
if (cellsBusy == 0) {
CounterCell r = new CounterCell(x); //传入元素个数
//通过cas设置 cellsBusy 标识,防止并发处理
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try {
CounterCell[] rs; int m, j;
//将初始化的对象的元素个数放在对应下标的位置
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
rs[j] = r;
created = true;
}
} finally {
cellsBusy = 0; //恢复标志位
}
//创建成功则退出循环
if (created)
break;
continue; //创建未成功说明指定下标位置的数据不为空,进行下一次循环
}
}
collide = false;
}
//说明在addCount()方法中 cas 失败了,并且获取 probe 的值不为空
else if (!wasUncontended)
wasUncontended = true; //设置为未冲突标识,进入下一次自旋
//指定下标位置的不为空,则直接通过 cas 进行原子累加,如果成功,则直接退出
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
break;
//如果已经有其他线程建立了新的 counterCells 或者 CounterCells 大于 CPU 核心数
else if (counterCells != as || n >= NCPU)
collide = false; //设置当前线程的循环失败不进行扩容
//恢复 collide 状态,标识下次循环会进行扩容
else if (!collide)
collide = true;
//如果竞争较大,设置正在扩容标识,进行扩容
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
if (counterCells == as) {
//扩容一倍
CounterCell[] rs = new CounterCell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
counterCells = rs;
}
}finally {
cellsBusy = 0;//恢复标识
}
collide = false;
continue; //继续下一次循环
}
h = ThreadLocalRandom.advanceProbe(h);//更新随机数的值
}
//如果counterCells还没被初始化,则进行初始化操作
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try {
if (counterCells == as) {
CounterCell[] rs = new CounterCell[2]; //初始化容量为 2
rs[h & 1] = new CounterCell(x); //将元素的个数放在指定的数组下标位置
counterCells = rs; //赋值给 counterCells
init = true;//设置初始化完成标识
}
} finally {
cellsBusy = 0;//恢复标识
}
if (init)
break;
}
//其它线程占据 cell 数组,直接累加在 basecount 变量中
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break;
}
}

并发扩容

在调用addCount()方法时,会根据传入的数量标识是否需要检查扩容,也就是当更新后的键值对总数大于阈值时,进行扩容。

如果当前正处于扩容阶段,则当前线程会加入并且协助扩容;如果当前没有在扩容,则直接触发扩容操作。

addCount()方法检查扩容代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//如果传入的check大于等于0,则需要检查扩容
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
//如果集合大小大于或等于扩容阈值,并且 table 不为空且长度小于最大容量
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n); //生成一个唯一的扩容戳,这里划个重点
//如果sizeCtl小于0,说明已经有别的线程正在扩容了
if (sc < 0) {
//判断是否能帮助进行此次扩容
//具体判断逻辑请看注1
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
//当前线程帮助此次扩容,如果cas成功,则调用transfer()方法进行扩容
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
//如果当前没有在扩容,将sc设置为一个负数,+2 表示有一个线程在执行扩容
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();// 重新计数,判断是否需要开启下一轮扩容
}
}

注1:

当前线程判断是否能帮助进行此次扩容时,需先判断(sc >>> RESIZE_STAMP_SHIFT)的高位值与rs相等,如果相等,则还需满足以下4个条件:

  • 如果sc = rs+1,则表示扩容结束
  • 如果sc = rs+MAX_RESIZERS,则表示帮助线程线程已经达到最大值了
  • 如果nt = nextTable,则表示扩容已经结束
  • 如果transferIndex <= 0,表示所有的 transfer 任务都被领取完了

resizeStamp()方法

resizeStamp()方法用来生成一个和扩容有关的扩容戳,其代码如下:

1
2
3
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}

Integer.numberOfLeadingZeros()方法是返回无符号整数 n 最高位非 0 位前面的 0 的个数。

如果n等于16,那么resizeStamp(16)的值为32796

将32796转换为二进制则为 [0000 0000 0000 0000 1000 0000 0001 1100]

当第一个线程进行尝试扩容时,会执行以下代码:

1
2
3
//如果当前没有在扩容,将sc设置为一个负数,+2 表示有一个线程在执行扩容
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))

RESIZE_STAMP_SHIFT的值为16,那么将rs左移16位,变成了[1000 0000 0001 1100 0000 0000 0000 0000]

之后在+2,则值为[1000 0000 0001 1100 0000 0000 0000 0010]

高 16 位代表扩容的标记、低 16 位代表并行扩容的线程数

transfer()方法

transfer()方法就是进行扩容的方法,其代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
//让每个CPU处理的桶一样多,默认一个线程处理16个桶
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE;
//如果nextTab为空,初始化nextTab,用来扩容
if (nextTab == null) {
try {
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt; //新建一个 n<<1 table大小的nextTab
} catch (Throwable ex) {
sizeCtl = Integer.MAX_VALUE; //扩容失败,sizeCtl使用int的最大值
return;
}
nextTable = nextTab; //赋值成员变量
transferIndex = n; //表示转移时的下标
}
int nextn = nextTab.length; //新的 tab 的长度
// 创建一个 fwd 节点,表示一个正在被迁移的 Node
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true; //如果等于 true,则处理下一个下标
boolean finishing = false; //扩容是否完成的标记
//循环处理每个槽位中的链表元素,i为当前槽位,bound为槽位边界
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
//循环分配任务
while (advance) {
int nextIndex, nextBound;
//--i为下一个待处理的桶,如果它>=bound,表示当前线程已经分配过桶
if (--i >= bound || finishing)
advance = false;
//表示所有桶已经被分配完毕
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
//通过cas修改TRANSFERINDEX,为当前线程分配任务
//如果扩容的大小是32,则nextIndex=32,nextBound=16
//则处理的节点区间为(bound,i)->(16,31)
//那么下一个进来的线程分配的区间就为(0,15)
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
//i小于0 说明当前线程已经处理完所有负责的桶
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
//如果完成了扩容
if (finishing) {
nextTable = null;
table = nextTab;//更新 table 数组
sizeCtl = (n << 1) - (n >>> 1);//更新阈值
return;
}
//使用cas操作对 sizeCtl 的低16位进行减1,表示完成了自己的任务
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
//如果还有线程在进行扩容,则扩容未结束
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true; //如果扩容结束,更新finishing变量
i = n; //再次检查
}
}
//如果位置i处是空的,那么放入ForwardingNode节点
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
//MOVED节点表示该位置已经完成了迁移
else if ((fh = f.hash) == MOVED)
advance = true;
else {
//对该节点位置加锁,开始迁移
synchronized (f) {
//再次校验
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;//ln 表示低位,hn 表示高位;
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
//遍历当前节点的链表
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
//如果runBit 是 0,设置低位节点
if (runBit == 0) {
ln = lastRun;
hn = null;
}
//否则设置高位节点
else {
hn = lastRun;
ln = null;
}
//构造高位以及低位的链表
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);//将低位的链表放在i位置
setTabAt(nextTab, i + n, hn);//将高位链表放在 i+n 位置
setTabAt(tab, i, fwd); //将旧table的节点i设置为MOVED节点
advance = true;
}
//红黑树部分省略
...
}
}
}
}
}

协助扩容

在执行put()方法时,如果table[i]已经有其它节点,发生碰撞,且table[i]的节点的hash等于MOVED,则线程帮助其扩容

1
2
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);

helpTransfer()方法协助扩容,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
//判断此时是否仍然在执行扩容,如果nextTab为则扩容已经结束
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);//生成扩容戳
//如果扩容还未完成,则循环尝试将当前线程加入到扩容操作中
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
//如果扩容已经结束,则退出循环
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break; //退出循环
//在低16位中增加扩容线程数
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab); //调用扩容方法协助扩容
break;
}
}
return nextTab;
}
return table;
}