哈希映射调整方法大小实现详细信息
正如标题所示，这是一个关于实现细节的问题 - 当内部数组的大小加倍时。这有点冗长，但我真的试图证明我尽了最大的努力来理解这一点......HashMap#resize
当此特定存储桶/箱中的条目以某种方式存储时，就会发生这种情况 - 因此具有确切的顺序，并且在问题的上下文中这很重要。Linked
通常，也可以从其他地方调用，但让我们只看这种情况。resize
假设您将这些字符串作为键放在 a 中（右侧是 after - 这是内部重新哈希）。是的，这些都是精心生成的，而不是随机的。HashMaphashcodeHashMap#hash
DFHXR - 11111
YSXFJ - 01111
TUDDY - 11111
AXVUH - 01111
RUTWZ - 11111
DEDUC - 01111
WFCVW - 11111
ZETCU - 01111
GCVUR - 11111
这里有一个简单的模式需要注意 - 最后4位对于所有键都是相同的 - 这意味着当我们插入其中的8个键（总共有9个）时，它们将最终在同一桶中;在9日，将被称为。HashMap#putresize
因此，如果当前有 8 个条目（具有上述键之一）- 这意味着此映射中有 16 个存储桶，并且它们的最后 4 位键决定了条目的结束位置。HashMap
我们把第九个键。此时被击中并被调用。箱子加倍到，键多一位决定该条目将去哪里（所以，现在是5位）。TREEIFY_THRESHOLDresize32
最终到达这段代码（当发生时）：resize
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
它实际上并不那么复杂...它的作用是将当前箱子拆分为将移动到其他箱子的条目和不会移动到其他箱子的条目 - 但肯定会保留在此箱中。
它实际上非常聪明地做到这一点 - 它是通过这段代码：
if ((e.hash & oldCap) == 0)
这样做是检查下一个位（在我们的例子中为第5位）是否实际上为零 - 如果是，则意味着此条目将保留在原处;如果不是，它将在新箱中以2的幂偏移移动。
现在终于有一个问题了：调整大小时的那段代码是精心制作的，以便它保留该箱中条目的顺序。
因此，在您将这9个键放入顺序之后，顺序将是：HashMap
DFHXR -> TUDDY -> RUTWZ -> WFCVW -> GCVUR (one bin)
YSXFJ -> AXVUH -> DEDUC -> ZETCU (another bin)
