英文:
In ConcurrentHashMap's transfer method, I don't understand the meaning of these two conditions "i >= n" and "i + n >= nextn"
问题
在转移方法中,判断扩展终止的条件(或帮助传输线程完成)是 if (i < 0 || i >= n || i + n >= nextn) {。我知道 i < 0 这个条件表示所有的存储桶都已经分配,但我不理解另外两个条件的意思:i >= n 和 i + n >= nextn。
i >= n 是否考虑了数据溢出?(-2147483648 - 1 = 2147483647);
i + n >= nextn 和 i >= n 是一样的吗?(我认为不是)
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    //...
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    boolean advance = true;
    boolean finishing = false; // 确保在提交 nextTab 之前进行扫描
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
            if (--i >= bound || finishing)
                advance = false;
            else if ((nextIndex = transferIndex) <= 0) {
                i = -1;
                advance = false;
            }
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;
            }
        }
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {
                nextTable = null;
                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)
                    return;
                finishing = advance = true;
                i = n; // 在提交之前重新检查
            }
        }
        //...
}
英文:
In the transfer method,the condition for judging the termination of the expansion (or the helping transfer threads finish) is if (i < 0 || i >= n || i + n >= nextn) {. I know i < 0 this condition means that all bins have been allocated, but I don't understand the meaning of other two conditions:  i >= n and i + n >= nextn
Is i >= n considering a data overflow?(-2147483648 - 1 = 2147483647);
Is i + n >= nextn the same as i >= n?(I don't think so)
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
//...
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
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)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
//...
}
答案1
得分: 1
逻辑上来说,这是一段无效的代码,我认为它可能在编码/调试期间用于边界检测。
从数学的角度来看,如果 i >= n,那么:
- 整数溢出:不可能,因为最大调整阈值是 1<<29,而 n 的最大值是 1<<29。
 - i 变大于 n:不可能,因为 i = nextIndex-1,而 nextIndex = transferIndex,且 transferIndex = nextIndex-stride。
 
如果 i >= n,那么 transferIndex 需要被另一个线程更新为更大的值(加倍)。
这意味着在当前调整尚未完成时发生了新的调整!
这绝对不可能。
while (advance) {
  int nextIndex, nextBound;
  if (--i >= bound || finishing)
      advance = false;
  else if ((nextIndex = transferIndex) <= 0) {
      i = -1;
      advance = false;
  }
  else if (U.compareAndSwapInt
           (this, TRANSFERINDEX, nextIndex,
            nextBound = (nextIndex > stride ?
                         nextIndex - stride : 0))) {
      bound = nextBound;
      i = nextIndex - 1;
      advance = false;
  }
}
有人可能会质疑 volatile 变量的更新顺序,比如 nextTable/table/sizeCtl,也是不可能的。
因为在调整结束时,它们会被更新如下:
// 见方法 transfer
if (finishing) {
   nextTable = null;
   table = nextTab;
   sizeCtl = (n << 1) - (n >>> 1);
   return;
}
而所有的转移入口严格检查 table/nextTable/sizeCtl 和 transferIndex。
同样,无法泄漏部分更新到 transfer 中。
所以,我有 i + n >= nextn 的疑虑。
英文:
logically, it's a piece of dead code, i think it might be boundary dection during coding/deubging.
From the view of math, if i >= n, then
- int overflow: impossible. because max resizing threshold is 1<<29,the maximum value of n is 1<<29
 - i become larger than n: impossible. beacuse i = nextIndex-1, while nextIndex = transferIndex, and transferIndex=nextIndex-stride
<br/>
if i>=n, then transferIndex need to be updated to larger value(doubled) by another thread.
which means a new resizing happens while current resizing has not completed!
<br/>
it's definitely impossible 
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) { //here is the only chance to update nextIndex
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
one might doubt the updated sequence of volatile variables, such as nextTable/table/sizeCtl, also impossible.
<br>
because at the end of resizing, they got updated as belows:
//see the method transfer
if (finishing) {
   nextTable = null;
   table = nextTab;
   sizeCtl = (n << 1) - (n >>> 1);
   return;
}
And all the entering of transfer strictly check table/nextTable/sizeCtl and transferIndex.
<br>
again, no way to leak partially updates to transfer.
and so i+n >= nextn
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。


评论