java - 不可变集和图的JDK9随机化

Question

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

由于规范不保证集合和 map 的遍历/迭代顺序，因此绝对可以。实际上，代码绝不能依赖于实现特定的细节，而只能依赖规范。

我知道今天使用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说这种随机化的动机是:

(...)人们编写的应用程序对迭代顺序有无意的依赖性。 (...)因此，无论如何，迭代顺序很重要，我认为那里有很多代码都对尚未发现的迭代顺序具有潜在的依赖性。 (...)因此，我们对此的响应是故意将新集合中Set和Map中的迭代顺序随机化。因此，尽管集合的迭代顺序是不可预测的但稳定的，但是它们是不可预测的。因此，每次JVM启动时，我们都会获得一个随机数，并将其用作与哈希值混合在一起的种子值。因此，如果您运行一个程序来初始化一个集合，然后以任何顺序打印出元素，那么您会得到一个答案，然后，如果再次调用JVM并运行该程序，则通常会在其中出现一组元素不同的顺序。因此，这里的想法是(...)如果您的代码中存在迭代顺序依赖性(过去曾经发生过这种情况)，是新的JDK版本发布了，您可以测试代码，然后(...) d需要花费数小时的调试才能将其追溯到迭代顺序中的某种更改。这意味着该代码中存在一个依赖于迭代顺序的错误。现在，如果您像每次JVM调用一样更频繁地更改迭代顺序，那么(我们希望)奇怪的行为会更频繁地表现出来，实际上，我们希望在您进行测试时...

因此，动机很明显，而且很明显，这种随机化只会影响新的不可变集和映射。

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

Answer 1

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

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

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

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

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

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

保留未指定的迭代顺序，但应尽可能少地更改迭代顺序。

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

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

经常将迭代顺序更改为，例如，从一个迭代到下一个迭代。

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

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

因此，我们最终制定了策略3，尽管迭代次数有时会有所变化，但要保持迭代顺序尽可能稳定。例如，我们在JDK 7u6中引入了替代哈希(对于JDK-7118743为code review)，而在JDK 8中引入了树状容器(JEP 180)，并且在某些情况下都改变了HashMap迭代顺序。在较早的版本中，订购也更改了几次。有人进行了一些考古研究，发现每个主要JDK版本的迭代顺序平均更改了一次。

这是所有可能世界中最糟糕的。主要版本仅每两年发布一次。当一个出来的时候，每个人的代码都会被破坏。会有很多哭泣和咬牙切齿的事情，人们会修复他们的代码，我们保证永远不会再更改迭代顺序。几年后，新的代码将被无意中依赖于迭代顺序。然后，我们将发布另一个主要版本，该版本更改了迭代顺序，这将再次破坏每个人的代码。周期将重新开始。

我想避免对新的收藏重复这个循环。我没有使迭代顺序尽可能稳定，而是采取了尽可能频繁地更改它的策略。最初，顺序在每次迭代时都会更改，但这会带来一些开销。最终，我们确定每次JVM调用一次。成本是每个表探针需要32位XOR操作，我认为这非常便宜。

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

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

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

总而言之，需要权衡的是应用程序开发人员必须做更多的工作，以确保他们的代码能够抵抗迭代顺序更改造成的破坏。无论如何，这可能是他们必须使用HashMap完成的工作。这样可以为JDK提供更多的机会来提高性能和空间效率，每个人都可以从中受益。