在ConcurrentHashMap的传输方法中，我不明白这两个条件“i >= n”和“i + n >= nextn”的含义

Question

在转移方法中，判断扩展终止（或帮助转移线程完成）的条件是if (i < 0 || i >= n || i + n >= nextn) {。我知道i < 0这个条件意味着所有的 bin 都被分配了，但我不明白其他两个条件的含义： 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; // 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
                }
            }
            //...
}

Answer 1

从逻辑上讲，这是一段死代码，我认为这可能是编码/调试期间的边界检测。

\n

从数学的角度来看，如果 i >= n，那么

\n

\n
1. int 溢出：不可能。因为最大调整大小阈值是 1<<29\xef\xbc\x8cn 的最大值是 1<<29
\n
2. i 变得大于 n：不可能。因为 i = nextIndex-1，而 nextIndex = TransferIndex，且 TransferIndex=nextIndex-stride\n
   \n如果 i>=n，则需要由另一个线程将 TransferIndex 更新为更大的值（双倍）。\n这意味着发生新的大小调整而当前调整大小尚未完成！\n
   \nit\ 绝对不可能
\n

\n

while (advance) {\n  int nextIndex, nextBound;\n  if (--i >= bound || finishing)\n      advance = false;\n  else if ((nextIndex = transferIndex) <= 0) { //here is the only chance to update nextIndex\n      i = -1;\n      advance = false;\n  }\n  else if (U.compareAndSwapInt\n           (this, TRANSFERINDEX, nextIndex,\n            nextBound = (nextIndex > stride ?\n                         nextIndex - stride : 0))) {\n      bound = nextBound;\n      i = nextIndex - 1;\n      advance = false;\n  }\n}\n

\n

人们可能会怀疑 volatile 变量的更新顺序，例如 nextTable/table/sizeCtl，也是不可能的。 \n
\n因为在调整大小结束时，它们更新如下：

\n

while (advance) {\n  int nextIndex, nextBound;\n  if (--i >= bound || finishing)\n      advance = false;\n  else if ((nextIndex = transferIndex) <= 0) { //here is the only chance to update nextIndex\n      i = -1;\n      advance = false;\n  }\n  else if (U.compareAndSwapInt\n           (this, TRANSFERINDEX, nextIndex,\n            nextBound = (nextIndex > stride ?\n                         nextIndex - stride : 0))) {\n      bound = nextBound;\n      i = nextIndex - 1;\n      advance = false;\n  }\n}\n

\n

并且所有transfer的输入都严格检查table/nextTable/sizeCtl和transferIndex。\n
\n同样，无法泄漏部分更新到transfer。

\n

所以 i+n >= nextn

\n