1.引言
网上已经有很多关于ConcurrentHashMap1.8源码的解析，像putval()，get()等方法的源码也不是很复杂，在这就不再赘述了。但是很多文章的tryPresize()扩容方法讲的晦涩难懂，我今天就讲讲我对tryPresize()方法的理解
2.源码解析
首先，tryPresize()方法是在树化桶的链表时调用的，解析见注解
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
//当某个桶个节点数大于，但table[]的长度小于最小的长度时（默认64）
// 进行扩容，调整某个桶中结点数量过多的问题
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)TREEIFY_THRESHOLD
tryPresize(n << 1);
......省略
}
接下来看看tryPresize()方法
private final void tryPresize(int size) {
//size在传入之前就已经翻倍了，最终c是一个大于等于（size * 1.5 + 1）的2的幂次方数
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
//此时的sizeCtl是cap * 0.75，扩容阈值
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
//如果此时tab为空，则进行初始化，将sizeCtl设为-1
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
//sc = n * 0.75
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
//tab == table说明还没开始迁移节点
else if (tab == table) {
int rs = resizeStamp(n);
//开始迁移原tab[] 中的数据，此时将sizeCtl设置为一个很大的负值，(rs << RESIZE_STAMP_SHIFT) + 2)必为一个负值
if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
//第一个发起迁移的线程，传入nextTable为null
transfer(tab, null);
}
}
}
在说明transfer()方法前，先说明一下helpTransfer()方法,跟中该方法在源码中的使用，发现只有在桶的头节点的hash值为Moved时才会调用，功能是帮助迁移节点
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
//只有f的hash为MOVED，才会执行该方法，说明f节点是ForwardingNode
//如果nextTable为null,则表示迁移完成了，详见transfer()
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;
//每有一个线程来帮助迁移，sizeCtl就+1，初始值为(rs << RESIZE_STAMP_SHIFT) + 2)（ps:在tryPresize()设置），之后再transfer中会用到
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
弄明白上面几个方法逻辑的同学恭喜你，可以挑战最晦涩的transfer()方法啦，不多说，上code,巨长，不过不要被吓到，我已经写明注释了
//该方法通过全局的transferIndex来控制每个线程的迁移任务
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
//n为旧tab的长度，stride为步长(就是每个线程迁移的节点数)
int n = tab.length, stride;
//单核步长为1，多核为（n>>>3）/ NCPU,最小值为16
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
//nextTable为全局属性
nextTable = nextTab;
//transferIndex也为全局属性，用于控制迁移位置
transferIndex = n;
}
int nextn = nextTab.length;
//ForwardingNode是正在被迁移的Node，它的key，value，next都为null
//hash为MOVED，其中有个nextTable属性指向新tab[]
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
//advance为true，可以继续迁移下一个节点，false则停止迁移
boolean advance = true;
//是否结束迁移
boolean finishing = false; // to ensure sweep before committing nextTab
//i是当前迁移位置的索引，bound是迁移的边界，是从后往前的顺序
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
//while循环迁移的--（减减）条件，第一个条件一直为true，finishing为true则迁移任务结束
if (--i >= bound || finishing)
advance = false;
//transferIndex（上一次迁移的边界）赋值给nextIndex（必执行），这里transferIndex一旦小于等于0
//则说明原数组的所有位置的迁移都有相应的线程去处理了，该线程可以不用迁移了
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
//将nextBound赋值给transferIndex，nextBound = nextIndex - stride（上一个边界减去步长）
//i = nextIndex - 1（上一个边界-1变成开始迁移的位置）
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;
//所有迁移完成，将nextTable设为空，sizeCtl为新tab.length * 0.75
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
//该线程完成迁移，sizeCtl - 1，对应之前helpTransfer()中+1
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
//不相等说明还有其他线程没完成迁移，该线程结束任务
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
//如果相等，则说明说有线程都完成任务了，设置finish为true
finishing = advance = true;
i = n; // recheck before commit
}
}
//如果旧tab[i]为null，则放入ForwardingNode
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
//如果该节点为ForwardingNode，则说明已经被迁移过了，就可以开始迁移下一个节点了
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
//迁移开始加锁，这部分和1.8HashMap差不多，将一条链表拆分成两条
//建议去看看1.8HashMap的扩容代码，好懂一点
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
//fh >= 0,说明是链表结构
//这个涉及到spread()方法，得到的hash值最高位必为0，则是正数
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;
}
}
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);
setTabAt(nextTab, i + n, hn);
//将该位置放入ForwardingNode
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) :
(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);
//将该位置放入ForwardingNode
setTabAt(tab, i, fwd);
//advance设置为true，说明该位置的迁移已经完成了
advance = true;
}
}
}
}
}
}
要是以上注释都看懂了，那么对于tryPresize()和transfer()的执行逻辑也就大概明白了，要是有错误或者不明白的地方，欢迎留言讨论
