不可变集和图的JDK9随机化

Question

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

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

我知道今天使用JDK 8，如果我拥有ie 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的另一个实例中，我运行相同的代码，输出可能会有所不同，因为引入了随机化。

到目前为止，我已经在youtube（第44:55分钟）上找到了这段出色的视频，其中Stuart
Marks说，这种随机化的动机是：

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

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

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

Answer 1

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

在任何情况下，随机迭代顺序的另一个原因是 保留灵活性，以供将来实现更改。

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

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

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

2. 保留未指定的迭代顺序，但隐式保持迭代顺序稳定。

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

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

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

6. 甚至更 频繁地更改迭代顺序，例如，从一个迭代到下一个迭代。

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

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

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

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

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

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

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

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

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