CHM-扩容-transfer
2020-04-09 本文已影响0人
01010100
扩容最终要通过transfer方法来执行复制，扩容的目的就是将老table中的元素复制到新的更大的nextTable。
大概流程
我们知道transfer是支持多线程并发扩容的，扩容过程第一个线程从table.length开始领取一段区间的任务，后续线程依次递减领取，每个线程负责一段区间的复制，互不干扰。
当线程完成这一段区间任务后，继续领取下一段待处理的区间，如所有任务区间都被领取完，进入退出流程，最后一个退出的线程负责再复查一遍。
主要4个步骤
1、初始化：第一个扩容的线程负责初始化
初始化不需要加锁因为调用transfer之前都会通过compareAndSwap sizeCtl来判断，U.compareAndSwapInt(this, SIZECTL, sc, xxx)
2、任务执行控制和任务领取
3、结束判断流程
4、处理扩容复制
比较难理解的
1、第2步的while循环，通常要循环两遍，开始都是true，进入while循环之后才会赋值false
2、第3步的recheck，最后结束扩容的线程还要再复查一遍
3、第4步的链表拆分，挂靠到新nextTable的高低位
变量
成员变量
- table
老的table - nextTable
新的table - transferIndex
The next table index (plus one) to split while resizing.
transferIndex就是控制任务区间的游标，表示当前待领取的任务区间的下标，初始值transferIndex=table.length，每领取一次就递减：transferIndex = transferIndex - stride
当transferIndex<=0，说明所有任务区间都领取完毕，当前线程准备退出流程
本地变量
- advance
控制任务的推进 - finishing
扩容结束标志，只有最后一个完成扩容的线程才能设置为true - i
当前任务游标
执行任务时在区间bound~nextIndex-1，从右边界往左执行。
当i<bound说明当前区间任务执行完毕。
当transferIndex<=0，i=-1，从而进入结束流程 - bound
当前任务区间左边界：成功领取任务时赋值：bound=nextBound=nextIndex-stride - nextIndex
临时变量，准备领取任务时赋值：nextIndex=transferIndex，区间右边界 - nextBound
临时变量，成功领取任务时赋值：nextBound=nextIndex-stride，区间左边界
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
*/
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range //每个线程划分的范围
if (nextTab == null) { // initiating //1、初始化。第一个扩容的线程负责初始化
try { //初始化不需要加锁因为调用transfer之前都会通过compareAndSwap sizeCtl来判断，U.compareAndSwapInt(this, SIZECTL, sc, xxx)
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1]; //扩容至2倍
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n; //初始化，设置transferIndex=tab.length
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab); //占位节点，表示当前桶已有线程扩容，也可以用来表示当前table正在扩容
boolean advance = true; //是否推进
boolean finishing = false; // to ensure sweep before committing nextTab //结束标志
for (int i = 0, bound = 0;;) { //进入table循环，领取扩容任务：i 当前任务游标，bound 当前任务区间最小下标
Node<K,V> f; int fh;
while (advance) { //2、任务执行控制和任务领取。while循环，通常要循环两遍，第一遍都是true，走入其中3步之一，会赋值false跳出循环
int nextIndex, nextBound;
if (--i >= bound || finishing) //2.1、判断当前区间任务是否完成或扩容是否结束：当前任务区间未完成和扩容结束，都不需要再走第2/3步
advance = false; // 当前任务区间未完成：继续完成区间任务，扩容结束：进入结束流程
else if ((nextIndex = transferIndex) <= 0) { //2.2、判断任务区间是否被领用完
i = -1; // transferIndex<=0，所有任务区间都被领完，将i改成负数，好进入结束判断流程
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) { //2.3、领用任务区间: transferIndex = transferIndex - stride
bound = nextBound; //任务区间：bound~nextIndex-1
i = nextIndex - 1; //游标，从nextIndex-1开始，递减至bound
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) { //3、结束判断流程。 i<0 说明所有任务区间都已被领用
int sc;
if (finishing) { //只有最后一个结束的线程finishing才有可能为true，其他线程的finishing始终为false
nextTable = null; //正式结束扩容，nextTable重新赋空，并给table/sizeCtl赋值
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { //所有任务区间都已领完，扩容线程计数减一，当前线程准备退出扩容流程
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) //判断所有线程是否已扩容完成：第一个线程在扩容时：U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)，即sc == rs << RESIZE_STAMP_SHIFT + 2
return; //不想等说明还有其他线程未完成，当前直接退出
finishing = advance = true; //当前线程已是最后一个线程，将finishing设置为true，并且将advance=true需要负责再检查一遍才能退出
i = n; // recheck before commit //i=n，重新遍历，再次复查整个table
}
}
else if ((f = tabAt(tab, i)) == null) //当前桶为空，直接设为已处理
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED) //当前桶已处理
advance = true; // already processed
else { //4、处理扩容复制
synchronized (f) { //给头节点上锁
if (tabAt(tab, i) == f) { //double check
Node<K,V> ln, hn; //高低位，重新迁移的节点会分成高低位，拆开到新table不同的桶里
if (fh >= 0) { //hash >0，说明是链表
int runBit = fh & n; //首节点和length取余，取余后结果只能为1或0，length=2^n（只有一位是1，其余都是0，格式如0001000）
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不同，则更新runBit，并更新lastRun
runBit = b;
lastRun = p;
}
}
if (runBit == 0) { //最后更新的runBit==0，则将其放入低位节点
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) { //再循环一遍将链表拆分成2个，取余是0的在低位，取余是1的高位
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);
advance = true;
}
else if (f instanceof TreeBin) { //红黑树，同样的拆分
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : //节点数<6，转成链表，否则继续使用红黑树
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
参考：
https://www.jianshu.com/p/2829fe36a8dd
https://www.jianshu.com/p/487d00afe6ca
