HashMap resize方法实现细节

Question

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

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

一般resize也可以从其他地方调用，但我们只看这个例子。

假设您将这些字符串作为键放在 HashMap 中（右边是 hashcode after HashMap#hash - 这是内部re-hashing.) 是的，这些都是精心生成的，不是随机生成的。

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

这里有一个简单的模式需要注意 - 最后 4 位对所有这些都是相同的 - 这意味着当我们插入其中的 8 个键（总共 9 个）时，它们将 end-up同一个桶；并且在 9 日 HashMap#put，resize 将被调用。

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

我们放置 nine-th 键。此时TREEIFY_THRESHOLD被命中，resize被调用。 bins 加倍到 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;
 }

实际上并没有那么复杂...它的作用是将当前垃圾箱拆分为将移动到其他垃圾箱和不会移动的条目将 移动到其他垃圾箱 - 但肯定会留在这个垃圾箱中。

实际上它是如何做到这一点的——它是通过这段代码实现的：

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

这样做是检查下一位（在我们的例子中是第 5 位）是否真的为零 - 如果是，则意味着该条目将保持原样；如果不是，它将在新容器中以两个偏移量的幂移动。

现在最后的问题是：调整大小中的那段代码是经过精心制作的，因此它保留了该容器中条目的顺序。

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

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

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

为什么要保留 HashMap 中某些条目的顺序。 Map 中的订单确实很糟糕 or 。

Answer 1

Order in a Map is really bad [...]

这还不错，（用学术术语）就是这样。 Stuart Marks 在您发布的第一个 link 中写的内容：

[...] preserve flexibility for future implementation changes [...]

也就是说（我理解的）现在的实现恰好保持顺序，但是将来如果找到更好的实现，要么保持顺序要么不使用它。

Answer 2

维护作为链表实现的 bin 中的顺序有两个常见原因：

一个是您通过增加（或减少）哈希值来维持秩序。这意味着在搜索垃圾箱时，只要当前项目大于（或小于，视情况而定）正在搜索的哈希值，您就可以停止。

另一种方法涉及在访问时将条目移动到存储桶的前面（或更靠近前面），或者只是将它们添加到前面。这适用于元素被访问的可能性很高的情况，如果它刚刚被访问过的话。

我查看了 JDK-8 的源代码，它似乎（至少在大多数情况下）在做后面的被动版本（添加到前面）：

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java

虽然您永远不应该依赖不能保证它的容器的迭代顺序，但这并不意味着如果它是结构性的，则不能利用它来提高性能。另请注意，class 的实现处于特权位置，可以以正式方式利用其实现的细节，而 class 的用户不应该这样做。

如果您查看源代码并了解它是如何实现和利用它的，那么您就是在冒险。如果实现者做了，那就另当别论了！

注意：我有一个算法的实现，该算法在很大程度上依赖于称为 Hashlife 的哈希-table。使用此模型的哈希-table 是 2 的幂，因为 (a) 您可以通过位掩码（& 掩码）而不是除法获得条目，并且 (b) 重新散列得到简化，因为您只每个 'unzip' 个哈希箱。

基准测试表明，该算法通过在访问时主动将模式移动到其 bin 的前面来获得大约 20% 的收益。

该算法在很大程度上利用了元胞自动机中的重复结构，这些结构很常见，因此如果您已经看到一个模式，再次看到它的机会就很高。

Answer 3

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

HashMap resize方法实现细节

HashMap resize method implementation detail

java

hashmap

hashcode

java-8