HashMap调整大小方法的实现细节

Question

如标题所示，这是一个有关实现细节的问题HashMap#resize-那是内部数组的大小加倍时。有点罗word，但我确实试图证明我已尽力了解这一点…

这是在此特定存储桶/存储箱中的条目以某种方式存储的时候发生的Linked-因此具有确切的顺序，在问题的上下文中， 这一点很重要 。

通常，resize也可以从其他地方调用，但是让我们只看这种情况。

假设您将这些字符串作为键放入HashMap（在右侧，hashcode 后面是 HashMap#hash-内部重新哈希。）是的，它们是精心生成的，而不是随机生成的。

 DFHXR - 11111
 YSXFJ - 01111 
 TUDDY - 11111 
 AXVUH - 01111 
 RUTWZ - 11111
 DEDUC - 01111
 WFCVW - 11111
 ZETCU - 01111
 GCVUR - 11111

这里有一个简单的模式-所有的后4位都是相同的-
这意味着当我们插入8个键（总共9个）时，它们将最终出现在同一存储桶中；并在9个HashMap#put时，resize将被调用。

因此，如果当前-中有8个条目（具有上面的键之一），HashMap则表示此映射中有16个存储桶，它们的后4位键决定了这些条目的结尾位置。

我们输入了第九把钥匙。这时TREEIFY_THRESHOLD被点击并被resize调用。垃圾箱被加倍，32并且按键的另外一位决定该条目的去向（因此，现在为5位）。

最终，到达了这段代码（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;
 }

实际上，它并不那么复杂…它将当前的bin分为 将移至 其他bin的条目和 不会移至 其他bin的条目-但可以肯定地保留在该条目中。

实际上，如何做到这一点非常聪明-通过以下代码：

 if ((e.hash & oldCap) == 0)

这是检查下一个位（在我们的例子中为第五位）是否实际上为零-如果为零，则意味着该条目将保持在原位置；如果不是，它将在新料箱中以两个偏移量移动。

现在最后是一个问题：调整大小的那段代码是精心制作的，以便 保留该 bin中 条目的顺序 。

因此，在将这9个键放入HashMap顺序后，顺序将是：

DFHXR -> TUDDY -> RUTWZ -> WFCVW -> GCVUR (one bin)

YSXFJ -> AXVUH -> DEDUC -> ZETCU (another bin)

为什么要保留。中某些条目的顺序HashMap？在订单Map是 _真的_详见坏在这里。

Answer 1

设计注意事项已记录在同一源文件中的第211行的代码注释中

* When bin lists are treeified, split, or untreeified, we keep
* them in the same relative access/traversal order (i.e., field
* Node.next) to better preserve locality, and to slightly
* simplify handling of splits and traversals that invoke
* iterator.remove. When using comparators on insertion, to keep a
* total ordering (or as close as is required here) across
* rebalancings, we compare classes and identityHashCodes as
* tie-breakers.

由于通过迭代器删除映射无法触发调整大小，因此专门保留顺序的原因resize是“更好地保留局部性，并稍微简化拆分的处理”，以及在策略上保持一致。