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

2022-09-03 12:31:07

阅读这个问题Eugene给出的答案,我发现JDK9不可变集合和映射将引入一个随机性的来源,这将影响它们的遍历。这意味着迭代顺序确实是随机的,至少在JVM的不同运行之间是这样。

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

我知道今天,使用JDK 8,如果我有,即a并执行此操作(取自链接的答案):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说这种随机化的一个动机是:

(...)人们编写的应用程序无意中依赖于迭代顺序。(...)所以,无论如何,迭代顺序是一个大问题,我认为有很多代码对迭代顺序有潜在的依赖性,但尚未被发现。(...)因此,我们对此的回应是故意随机化新集合中 SetMap 中的迭代顺序。因此,虽然在集合的迭代顺序不可预测的但稳定之前,这些是可预测的不可预测的。因此,每次JVM启动时,我们都会得到一个随机数,并将其用作与哈希值混合的种子值。因此,如果您运行一个初始化集合的程序,然后以任何顺序打印出元素,您将获得一个答案,然后,如果您再次调用JVM并运行相同的程序,则元素集通常会以不同的顺序出现。所以,这里的想法是(...)如果你的代码中存在迭代顺序依赖关系,过去发生的事情是一个新的JDK版本出来了,你测试你的代码,(...)它需要几个小时的调试才能追踪到迭代顺序的某种变化。这意味着该代码中存在一个依赖于迭代顺序的错误。现在,如果你更频繁地改变迭代顺序,就像每次JVM调用一样,那么(我们希望)奇怪的行为会更频繁地表现出来,事实上,我们希望在你进行测试的时候......

因此,动机是明确的,也很明显,这种随机化只会影响新的不可变集合和映射。

我的问题是:这种随机化还有其他动机吗?它有什么好处?


答案 1

好吧,事实证明,随机迭代顺序还有另一个原因。这不是一个大秘密或任何东西。我以为我在那次演讲中已经解释了这一点,但也许不是。我可能在OpenJDK邮件列表上或内部讨论中提到过它。

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

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

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

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

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

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

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

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

  6. 频繁地更改迭代顺序,例如,从一次迭代到下一次迭代。

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

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

因此,我们最终选择了策略#3,保持迭代顺序尽可能稳定,尽管它确实不时发生变化。例如,我们在 JDK 7u6(JDK-7118743 的代码审查)和 JDK 8 (JEP 180) 中引入了树箱,并且在某些情况下都改变了迭代顺序。在早期版本中,排序也发生了几次更改。有人做了一些考古学,发现迭代顺序平均每个主要的JDK版本都改变了一次。HashMap

这是所有可能的世界中最糟糕的。主要版本每隔几年才发布一次。当一个出来时,每个人的代码都会中断。会有很多哭泣和咬牙切齿,人们会修复他们的代码,我们承诺永远不会再改变迭代顺序。几年过去了,新代码将不经意地依赖于迭代顺序。然后我们发布了另一个主要版本,它改变了迭代顺序,这将再次破坏每个人的代码。这个循环将重新开始。

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

在某种程度上,这是关于“加强”应用程序代码。如果更改迭代顺序会破坏代码,那么更频繁地中断该代码将导致它产生这种破坏的阻力。当然,代码本身不会变得更强。这需要更多的开发人员努力才能实现。人们会相当合理地抱怨不得不做这些额外的工作。

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

例如,当前的实现(Java 9,GA之前,2017年7月)有三个基于字段的Set(,和)实现,以及一个基于数组的实现(),它使用简单的闭合哈希和线性探测方案。将来,我们可能希望添加一个在三个字段中包含三个元素的实现。或者,我们可能希望将碰撞解决策略从线性探测更改为更复杂的策略。我们可以完全重构实现,即使在次要版本中,如果我们不必处理保留迭代顺序的问题。Set0Set1Set2SetNSet3SetN

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


答案 2

这句话和你的想法已经提出了一个强有力的论据来支持这样做。那么,您还需要什么呢?

换句话说:Java的“父亲”之一宣称,他们“随机映射/集合顺序”的动机是“教育”Java程序员不要期望甚至依赖任何特殊顺序。因此,答案(可能是固执己见的)-质疑您的期望。

负责人告诉您他们这样做的想法。没有理由认为他们正在“隐藏”这个设计决策的其他动机。

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


推荐