HashMap调整方法实现细节

Question

正如标题所示,这是一个关于实现细节的问题HashMap#resize- 当内部数组的大小加倍时.这有点罗嗦,但我真的试图证明我对此有了最好的理解......

这发生在这个特定桶/箱中的条目以某种方式存储的时刻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的条目- 但是肯定会保留在这个bin中.

它实际上是非常聪明的 - 它是通过这段代码:

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

这样做是检查下一位(在我们的例子中是第5位)是否实际为零 - 如果是,则表示该条目将保持原样; 如果不是,它将以新箱中的两个偏移力移动.

最后问题是:调整大小中的那段代码是经过仔细制作的,以便保留该 bin中条目的顺序.

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

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

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

你为什么要保留一些条目的顺序HashMap？在订单Map是真的详见坏在这里或在这里.

Answer 1

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

\n\n

\n

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

\n

\n\n

由于通过迭代器删除映射可以 \xe2\x80\x99t 触发调整大小，因此专门保留 \xe2\x80\x9c 中的顺序的原因resize是 \xe2\x80\x9c 以更好地保留局部性，并稍微简化对 splits\xe2\x80\x9d 的处理，以及政策上的一致性。

\n