HashMap的resize方法实现细节

Question

正如标题所示，这是关于HashMap#resize实现细节的问题——当内部数组大小加倍时发生。虽然有点啰嗦，但我确实尽力理解了这个问题。

此时，在这个特定的bucket/bin中存储的条目呈“Linked”方式存储——因此具有确切的顺序，在这个问题的上下文中非常重要。

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

假设您将这些字符串作为键放入HashMap中（右侧是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位决定了条目的位置。

我们放置第九个键。此时击中了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;
 }

其实并不那么复杂……它所做的是将当前的垃圾桶分成两部分，一部分将要移动到其他垃圾桶中，另一部分将不会移动到其他垃圾桶中——但它们肯定会留在这个垃圾桶里。

而它实现这个功能的方法非常聪明——就是通过这段代码：

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

这段代码的作用是检查接下来的位（在我们的例子中是第5位）是否为零 - 如果是，那么这个条目将保持原地; 如果不是，则会以2的幂次方偏移量向新的bin移动。

现在最后的问题是：resize中的这段代码被仔细制作，以便 保留了该bin原有的条目顺序。

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

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

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

为什么要保留HashMap中的某些条目的顺序？在Map中，有关顺序的信息非常不好，详见这里或这里。

- Eugene

---

嘿，评论已经说了：“在新表中是2的幂偏移量”。 - holi-java

@Nicolai 老实说，Java-8和Java-9标签只是为了吸引一些特定的用户注意，以便获得答案... - Eugene

@Nicolai 这个是特定于 Java 8 及以后版本的 HashMap。 - Eugene

@Eugene：毫无疑问，访问局部变量比访问数组元素更便宜，特别是在优化器无法确定newTab[e.hash & (n-1)]始终在数组边界内的情况下。 - Holger

@Eugene：这适用于代码。但我们仍然不知道为什么评论提到了保留顺序的行为... - Holger

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中保留顺序的原因是“更好地保留局部性，并稍微简化分割处理”，并且在策略方面保持一致。

- Holger

Answer 2

在Map中排序确实很糟糕[...]

并不是很糟糕，从学术术语来说是随意的。正如Stuart Marks在您发布的第一个链接中所写：

[...]保留未来实现更改的灵活性[...]

这意味着（据我理解）现在实现恰好保持顺序，但如果将来找到更好的实现，无论它是否保持顺序，都将使用它。

- MaanooAk

---

请阅读注释，因为这并不回答问题。 - Eugene

你的意思是说有更好的实现方式，因此我的答案是错误的吗？（还是你指的是其他评论，因为有很多评论...） - MaanooAk

这并不是错误的 - 任何人都可以自由地为其点赞；但我认为它并没有回答我的问题。 - Eugene

好的，没问题。但是你认为这并没有回答问题，因为有更好的实现方式，对吗？（所以我理解你的意思）（编辑：我可能听起来很激动，但其实不是，只是想澄清一下）。 - MaanooAk

根据@Eugene的观察进行了编辑 - MaanooAk

Answer 3

维护链表中元素顺序的两个常见原因：

一种方法是按照哈希值的增加（或减少）来维护顺序。这意味着在搜索一个链表时，只要当前项大于（或小于，适用于某些情况）被搜索的哈希值，就可以停止搜索。

另一种方法是在访问时将条目移到桶的前面（或更靠近前面），或者只是将它们添加到前面。这适用于刚被访问过的元素被再次访问的概率较高的情况。

我查看了JDK-8的源代码，似乎它至少在大部分情况下采用了后一种被动版本的方法（添加到前面）：

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

尽管在不保证迭代顺序的容器中，您永远不应该依赖迭代顺序，但如果结构化，仍然可以利用它来提高性能。此外，请注意，类的实现处于一种特权位置，可以以正式方式利用其实现细节，而该类的用户不应该这样做。

如果您查看源代码并了解如何实现和利用它，那么您会冒险。如果是实现者这样做，那就是另一回事！

注意： 我有一个算法的实现，它严重依赖于称为Hashlife的哈希表。它使用了这个模型，有一个大小为2的幂次方的哈希表，因为（a）您可以通过位掩码（& mask）而不是除法来获取条目，以及（b）重新哈希变得简化，因为您只需“展开”哈希桶。

基准测试显示，当访问时将模式主动移动到它们的桶的前面，该算法获得约20％的收益。

该算法几乎利用了元胞自动机中的重复结构，这些结构很常见，因此如果您看到了一个图案，再次看到它的可能性很高。

- Persixty

---

我不明白这个“这意味着当搜索一个桶时，只要当前项更大，就可以停止”。实际上内部所做的是(n - 1)＆hash或负安全取模用于2的幂次方箱。如果我有所遗漏，请提供一个例子说明它的实际含义。 - Eugene

答案2：您将新项目添加到列表的前面（头部）。因此，如果您来到该垃圾箱，您将首先找到它。许多应用程序具有统计功能（和/或可以调整为具有该功能），即条目比其他条目更有可能很快被重新访问。 - Persixty

@1) 我明白“哈希排序”的意思了，谢谢；但是现在的HashMap并不是这样做的——它只有插入顺序。2) 新项目添加到列表末尾（始终是HashMap中的next），所以有点无关紧要。3) 是的——目前就是这样发生的——但我看不出你的答案实际上如何解释问题，考虑到你的论点与实际情况有些不符。别误会，但这根本行不通... - Eugene

@Eugene。不，它不会。在1172上，first = (first = tab[i = (n - 1) & hash])，如果它得到1201（看看newNode()），将在链的开头添加新节点。实现HashMap是一团糟（公平地说）。我认为这是因为阈值转移使用二进制树似乎被硬塞进去了。但是，在其他地方，它确实会在末尾添加它们。我可以理解反序列化，但其他的看起来很混乱。对于“树缩放”来说并不那么重要，但我认为这就是它的意思... - Persixty

换个说法吧…（除了你实际上从其他方法中链接代码）。假设我有这些键YSXFJ和AXVUH。它们将会被放置在同一个桶中（你可以测试一下）。我首先插入YSXFJ，然后再插入AXVUH。打印此Map时的顺序是什么？ - Eugene