java - HashMap resize方法实现细节

Question

正如标题所示，这是一个关于 HashMap#resize 的实现细节的问题 - 即内部数组的大小翻倍。 这有点罗嗦，但我真的试图证明我已经尽我所能理解这一点......

这发生在此特定存储桶/bin 中的条目以 Linked 方式存储时 - 因此具有准确的顺序并且在问题的上下文中 这很重要。

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

假设您将这些字符串作为键放在 HashMap 中(右侧是 hashcode after 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。

因此，如果当前 HashMap 中有 8 个条目(具有上述键之一) - 这意味着此映射中有 16 个桶，它们的最后 4 位键决定了条目的位置结果。

我们放了第九把 key 。此时 TREEIFY_THRESHOLD 被命中并且 resize 被调用。 bin 加倍为 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) 

它的作用是检查下一位(在我们的例子中是第 5 位)是否实际上为零 - 如果是，则意味着该条目将保持在原位；如果不是，它将在新 bin 中以 2 次方偏移量移动。

现在最后的问题是:调整大小中的那段代码是经过精心制作的，以便它保持条目的顺序在那个 bin 中。

所以在你将这 9 个键放入 HashMap 之后，顺序将是:

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

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

为什么要保留 HashMap 中某些条目的顺序。 Map 中的顺序真的 很糟糕，详情如下 here或 here .

Answer 1

设计考虑已记录在同一源文件中，在 line 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 中特别保留顺序的原因是“更好地保留局部性，并稍微简化拆分处理”，以及与政策保持一致。