JDK9 对不可变集和映射的随机化
JDK9 randomization on immutable sets and maps
阅读 and ，我发现JDK9 不可变集和映射会引入影响其遍历的随机源。这意味着 迭代顺序 确实是随机的，至少在 JVM 的不同 运行 之间是这样。
由于规范不保证集合和地图的任何 traversal/iteration 顺序，这绝对没问题。事实上，代码绝不能依赖于特定于实现的细节，而是依赖于规范。
我知道今天 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...
所以，动机很明确，而且这种随机化只会影响新的不可变集和映射。
我的问题是：这种随机化还有其他动机吗？它有什么优势？
这句话和你的想法已经成为支持这样做的有力论据。那你还需要什么？
换句话说：Java 的 "fathers" 之一声明 他们 "random map/set order" 的动机是 "educate" Java 程序员不要期望甚至依赖任何特殊命令。因此答案（可能是固执己见的）——质疑你的期望。
负责人跟你说了他们做这件事的想法。没有理由假设它们是 "hiding" 此设计决策的其他动机。
恰恰相反：人们可能会发现反对花费额外努力来实现这种随机性——JVM可能正在花费相当多的额外 CPU 周期 - 只是为了 实现 不确定行为（我们通常不惜一切代价试图避免的行为）。
事实证明随机迭代顺序还有另一个原因。这不是什么大秘密。我以为我在那次谈话中已经解释过了，但也许没有。我可能在 OpenJDK 邮件列表或内部讨论中提到过它。
无论如何，随机迭代顺序的另一个原因是为未来的实施变化保留灵活性。
事实证明这比大多数人想象的要大。从历史上看，HashSet 和 HashMap 从未指定过特定的迭代顺序。然而，有时需要更改实现以提高性能或修复错误。对迭代顺序的任何更改都会引起用户的强烈不满。多年来，改变迭代顺序的阻力越来越大，这使得 HashMap 的维护变得更加困难。
要了解为什么这是一个问题，请考虑一系列不同的策略来管理迭代顺序的稳定性：
指定迭代顺序，并坚持下去。
不指定迭代顺序，但隐式保留迭代顺序 stable.
不指定迭代顺序，但尽可能少地更改迭代顺序。
经常更改迭代顺序，例如，在更新版本中。
更频繁地更改迭代顺序，例如，从 JVM 的一个 运行 到下一个。
更频繁地更改迭代顺序，例如，从一个迭代到下一个迭代。
在 JDK 1.2 中引入集合时，未指定 HashMap 迭代顺序。 Stable 迭代顺序由 LinkedHashMap 以更高的成本提供。如果您不需要 stable 迭代顺序，则不必为此付费。这排除了#1 和#2。
对于接下来的几个版本，我们尝试保持迭代顺序 stable，即使规范允许它更改。没有人喜欢代码损坏，不得不告诉客户他的代码损坏是非常不愉快的，因为它取决于迭代顺序。
所以我们最终采用了策略 #3，尽可能保持迭代顺序为 stable，尽管它确实会不时发生变化。例如，我们在 JDK 7u6 (code review for JDK-7118743) and tree bins in JDK 8 (JEP 180) 中引入了替代哈希，并且在某些情况下都更改了 HashMap 迭代顺序。在早期版本中，排序也发生了几次变化。有人做了一些考古学，发现每个主要 JDK 版本的迭代顺序平均改变一次。
这是所有可能世界中最糟糕的一个。主要版本每两年才发布一次。当一个出来时，每个人的代码都会被破坏。会有很多哀号和咬牙切齿，人们会修复他们的代码，我们承诺永远不会再改变迭代顺序。几年过去了，编写的新代码无意中依赖于迭代顺序。然后我们会推出另一个改变迭代顺序的主要版本，这会再次破坏每个人的代码。循环将重新开始。
我想避免为新系列重复这个循环。我没有尽可能保持迭代顺序为 stable，而是奉行尽可能频繁地更改它的策略。最初，顺序在 every 迭代时更改，但这会带来一些开销。最终我们确定每次 JVM 调用一次。成本是每个 table 探测器进行一次 32 位异或运算，我认为这很便宜。
在某种程度上，这是关于 "toughening up" 应用程序代码的。如果更改迭代顺序会破坏代码，那么更频繁地破坏该代码将导致它对这种破坏产生抵抗力。当然，代码本身并不会变得更强大；这需要更多的开发人员努力才能实现。人们会很合理地抱怨必须做这些额外的工作。
但是应用程序代码的 "toughening" 在某种意义上与保留更改实现自由的其他目标相比是次要的。保留 HashMap 的迭代顺序使其更难维护。新集合中的随机迭代顺序意味着我们在修改它们时不必担心保留迭代顺序，因此它们更容易维护和增强。
例如，当前实现（Java 9，pre-GA，2017 年 7 月）有 Set 的三个基于字段的实现（Set0、Set1 和 Set2) 和基于数组的实现 (SetN)，它使用带有线性探测方案的简单封闭散列。将来，我们可能想要添加一个 Set3 实现，它在三个字段中包含三个元素。或者，我们可能想要将 SetN 的冲突解决策略从线性探测更改为更复杂的东西。如果我们不必处理保留迭代顺序的问题，即使在次要版本中，我们也可以完全重构实现。
总而言之，权衡是应用程序开发人员必须做更多的工作来确保他们的代码不会因迭代顺序更改而中断。这很可能是他们在某个时候必须用 HashMap 做的工作。这样一来，JDK 就有更多机会提高性能和 space 效率，人人都能从中受益。
阅读
由于规范不保证集合和地图的任何 traversal/iteration 顺序，这绝对没问题。事实上，代码绝不能依赖于特定于实现的细节，而是依赖于规范。
我知道今天 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
SetandMapin 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...
所以，动机很明确，而且这种随机化只会影响新的不可变集和映射。
我的问题是：这种随机化还有其他动机吗？它有什么优势？
这句话和你的想法已经成为支持这样做的有力论据。那你还需要什么？
换句话说：Java 的 "fathers" 之一声明 他们 "random map/set order" 的动机是 "educate" Java 程序员不要期望甚至依赖任何特殊命令。因此答案（可能是固执己见的）——质疑你的期望。
负责人跟你说了他们做这件事的想法。没有理由假设它们是 "hiding" 此设计决策的其他动机。
恰恰相反：人们可能会发现反对花费额外努力来实现这种随机性——JVM可能正在花费相当多的额外 CPU 周期 - 只是为了 实现 不确定行为（我们通常不惜一切代价试图避免的行为）。
事实证明随机迭代顺序还有另一个原因。这不是什么大秘密。我以为我在那次谈话中已经解释过了，但也许没有。我可能在 OpenJDK 邮件列表或内部讨论中提到过它。
无论如何，随机迭代顺序的另一个原因是为未来的实施变化保留灵活性。
事实证明这比大多数人想象的要大。从历史上看，HashSet 和 HashMap 从未指定过特定的迭代顺序。然而，有时需要更改实现以提高性能或修复错误。对迭代顺序的任何更改都会引起用户的强烈不满。多年来，改变迭代顺序的阻力越来越大，这使得 HashMap 的维护变得更加困难。
要了解为什么这是一个问题，请考虑一系列不同的策略来管理迭代顺序的稳定性：
指定迭代顺序，并坚持下去。
不指定迭代顺序，但隐式保留迭代顺序 stable.
不指定迭代顺序，但尽可能少地更改迭代顺序。
经常更改迭代顺序，例如，在更新版本中。
更频繁地更改迭代顺序，例如，从 JVM 的一个 运行 到下一个。
更频繁地更改迭代顺序，例如，从一个迭代到下一个迭代。
在 JDK 1.2 中引入集合时，未指定 HashMap 迭代顺序。 Stable 迭代顺序由 LinkedHashMap 以更高的成本提供。如果您不需要 stable 迭代顺序，则不必为此付费。这排除了#1 和#2。
对于接下来的几个版本，我们尝试保持迭代顺序 stable，即使规范允许它更改。没有人喜欢代码损坏，不得不告诉客户他的代码损坏是非常不愉快的，因为它取决于迭代顺序。
所以我们最终采用了策略 #3，尽可能保持迭代顺序为 stable，尽管它确实会不时发生变化。例如，我们在 JDK 7u6 (code review for JDK-7118743) and tree bins in JDK 8 (JEP 180) 中引入了替代哈希，并且在某些情况下都更改了 HashMap 迭代顺序。在早期版本中，排序也发生了几次变化。有人做了一些考古学，发现每个主要 JDK 版本的迭代顺序平均改变一次。
这是所有可能世界中最糟糕的一个。主要版本每两年才发布一次。当一个出来时，每个人的代码都会被破坏。会有很多哀号和咬牙切齿，人们会修复他们的代码，我们承诺永远不会再改变迭代顺序。几年过去了，编写的新代码无意中依赖于迭代顺序。然后我们会推出另一个改变迭代顺序的主要版本，这会再次破坏每个人的代码。循环将重新开始。
我想避免为新系列重复这个循环。我没有尽可能保持迭代顺序为 stable，而是奉行尽可能频繁地更改它的策略。最初，顺序在 every 迭代时更改，但这会带来一些开销。最终我们确定每次 JVM 调用一次。成本是每个 table 探测器进行一次 32 位异或运算，我认为这很便宜。
在某种程度上，这是关于 "toughening up" 应用程序代码的。如果更改迭代顺序会破坏代码，那么更频繁地破坏该代码将导致它对这种破坏产生抵抗力。当然，代码本身并不会变得更强大；这需要更多的开发人员努力才能实现。人们会很合理地抱怨必须做这些额外的工作。
但是应用程序代码的 "toughening" 在某种意义上与保留更改实现自由的其他目标相比是次要的。保留 HashMap 的迭代顺序使其更难维护。新集合中的随机迭代顺序意味着我们在修改它们时不必担心保留迭代顺序，因此它们更容易维护和增强。
例如，当前实现（Java 9，pre-GA，2017 年 7 月）有 Set 的三个基于字段的实现（Set0、Set1 和 Set2) 和基于数组的实现 (SetN)，它使用带有线性探测方案的简单封闭散列。将来，我们可能想要添加一个 Set3 实现，它在三个字段中包含三个元素。或者，我们可能想要将 SetN 的冲突解决策略从线性探测更改为更复杂的东西。如果我们不必处理保留迭代顺序的问题，即使在次要版本中，我们也可以完全重构实现。
总而言之，权衡是应用程序开发人员必须做更多的工作来确保他们的代码不会因迭代顺序更改而中断。这很可能是他们在某个时候必须用 HashMap 做的工作。这样一来，JDK 就有更多机会提高性能和 space 效率，人人都能从中受益。