关于不可变集和映射的JDK9随机化

Question

阅读这个问题和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的另一个实例中,我运行相同的代码,输出可能不同,因为已经引入了随机化.

到目前为止,我在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提供更多机会和空间效率的机会,每个人都可以从中受益.

Answer 2

这句话和你的想法已经成为支持这种做法的有力论据.那你还需要什么呢？

换句话说:Java的"父亲"之一宣称他们 "随机地图/集合顺序" 的动机是"教育"Java程序员不要期望甚至依赖任何特殊订单.因此答案(可能是自以为是) - 质疑你的期望.

负责人告诉你他们这样做的想法.没有理由认为他们"隐藏"了这个设计决策的其他动机.

恰恰相反:人们可能会发现反对花费额外努力来实现这种随机性的论据--JVM可能会花费相当多的额外CPU周期 - 只是为了实现不确定行为(我们通常会不惜一切代价避免这种行为).