java - 不可变集和映射上的 JDK9 随机化

Question

阅读this question和 the answer given by Eugene ，我发现 JDK9 的不可变集合和映射会引入随机源，影响它们的遍历。这意味着迭代顺序确实是随机的，至少在 JVM 的不同运行中是这样。

由于规范不保证集合和映射的任何遍历/迭代顺序，这绝对没问题。事实上，代码绝不能依赖于特定于实现的细节，而是依赖于规范。

我知道今天使用 JDK 8，如果我有一个 HashSet并执行此操作(取自链接的答案):

Set<String> wordSet = new HashSet<>(Arrays.asList("just", "a", "test"));

System.out.println(wordSet);

for (int i = 0; i < 100; i++) {
    wordSet.add("" + i);
}

for (int i = 0; i < 100; i++) {
    wordSet.remove("" + i);
}

System.out.println(wordSet);

然后元素的迭代顺序将改变，两个输出将不同。这是因为在集合中添加和删除 100 个元素会改变 HashSet 的内部容量。并重新哈希元素。这是完全有效的行为。我不是在这里问这个。

但是，使用 JDK9，如果我这样做:

Set<String> set = Set.of("just", "a", "test");
System.out.println(set);

然后，在 JVM 的另一个实例中，我运行相同的代码，输出可能不同，因为引入了随机化。

到目前为止，我发现这个很棒 video in youtube (minute 44:55) ，其中 Stuart Marks 说这种随机化的一个动机是:

(...) that people write applications that have inadvertent dependencies on iteration order. (...) So, anyway, iteration order is a big deal and I think there's a lot of code out there that has latent dependencies on iteration order that has not been discovered yet. (...) So, our response to this is to deliberately randomize the iteration order in Set and Map in the new collections. So whereas before the iteration order of collections was unpredictable but stable, these are predictably unpredictable. So every time the JVM starts up, we get a random number and we use that at as a seed value that gets mixed in with the hash values. So, if you run a program that initializes a set and then prints out the elements in any order, you get an answer, and then, if you invoke the JVM again and run that same program, the set of elements usually would come out in a different order. So, the idea here is that (...) if there are iteration order dependencies in your code, what used to happen in the past, is a new JDK release came out and you test your code and (...) it'd take hours of debugging to trace it down to some kind of change in iteration order. What that meant was there was a bug in that code that depended on the iteration order. Now, if you vary the iteration order more often, like every JVM invocation, then (we hope) that weird behavior will manifest itself more frequently, and in fact we hope while you're doing testing...

所以，动机很明确，而且这种随机化只会影响新的不可变集和 map 。

我的问题是:这种随机化还有其他动机吗？它有什么优势？

Answer 1

事实证明，随机迭代顺序还有另一个原因。这不是什么大 secret 或什么。我以为我在那次演讲中已经解释过了，但也许没有。我可能在 OpenJDK 邮件列表或内部讨论中提到过它。

无论如何，随机迭代顺序的另一个原因是 保留 future 实现变更的灵活性。

事实证明，这比大多数人想象的要大得多。从历史上看，HashSet和 HashMap从未指定特定的迭代顺序。但是，有时需要更改实现以提高性能或修复错误。对迭代顺序的任何更改都会引起用户的强烈不满。多年来，改变迭代顺序产生了很多阻力，这使得 HashMap 的维护变得困难。更加困难。

要了解为什么这是一个问题，请考虑一系列不同的策略来管理迭代顺序的稳定性:

指定迭代顺序，并坚持下去。

不指定迭代顺序，但隐含地保持迭代顺序稳定。

不指定迭代顺序，但尽可能少地更改迭代顺序。

经常更改迭代顺序，例如在更新版本中。

更频繁地更改迭代顺序，例如，从 JVM 的一次运行到下一次。

更改迭代顺序更多经常，例如，从一次迭代到下一次。

当 JDK 1.2 中引入集合时，HashMap迭代顺序未指定。稳定的迭代顺序由 LinkedHashMap 提供以更高的成本。如果您不需要稳定的迭代顺序，则不必为此付费。这排除了#1和#2。

在接下来的几个版本中，我们试图保持迭代顺序稳定，即使规范允许它改变。当代码中断时，没有人喜欢它，并且不得不告诉客户他的代码已损坏，因为这取决于迭代顺序，这是非常不愉快的。

所以我们最终采用了策略 #3，尽可能保持迭代顺序稳定，尽管它不时发生变化。例如，我们在 JDK 7u6(code review 用于 JDK-7118743)和 JDK 8(JEP 180)中的树箱中引入了替代散列，并且都更改了 HashMap某些情况下的迭代顺序。在早期版本中，排序也发生了几次变化。有人做了一些考古，发现迭代顺序平均每个主要 JDK 版本改变一次。

这是所有可能的世界中最糟糕的。主要版本每两年才发布一次。当一个出来时，每个人的代码都会被破解。会有很多提示和咬牙切齿，人们会修复他们的代码，我们保证永远不会再改变迭代顺序。几年过去了，新代码会在无意中依赖于迭代顺序而编写。然后我们会推出另一个改变迭代顺序的主要版本，这将再次破坏每个人的代码。而这个循环又会重新开始。

我想避免为新系列重复这个循环。我没有尽可能保持迭代顺序稳定，而是尽可能频繁地更改它。最初，每次迭代的顺序都会改变，但这会带来一些开销。最终我们决定每次 JVM 调用一次。成本是每个表探针的 32 位 XOR 操作，我认为这非常便宜。

在某种程度上，这与“强化”应用程序代码有关。如果更改迭代顺序会破坏代码，那么更频繁地破坏该代码将导致它对这种破坏产生抵抗力。当然，代码本身并不会变得更强大；这需要开发人员付出更多努力才能实现。人们会很合理地提示不得不做这项额外的工作。

但是，在某种意义上，应用程序代码的“强化”是次要于保持更改实现的自由的另一个目标。保留 HashMap 的迭代顺序使得维护变得更加困难。新集合中的随机迭代顺序意味着我们在修改它们时不必担心保留迭代顺序，因此它们更易于维护和增强。

例如，当前的实现(Java 9，pre-GA，2017 年 7 月)具有三个基于字段的 Set 实现( Set0 、 Set1 和 Set2 )和一个基于数组的实现( SetN )它使用带有线性探测方案的简单封闭散列。将来，我们可能想添加一个 Set3在三个字段中包含三个元素的实现。或者，我们可能想要更改 SetN 的冲突解决策略。从线性探测到更复杂的东西。如果我们不必处理保留迭代顺序的问题，我们可以完全重构实现，即使是在次要版本中。

总之，权衡是应用程序开发人员必须做更多的工作来确保他们的代码抵抗迭代顺序更改的破坏。无论如何，这很可能是他们在某个时候必须使用 HashMap 做的工作。 .由此获得的是 JDK 提供更高性能和空间效率的更多机会，每个人都可以从中受益。