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

15
阅读这个问题Eugene给出的答案, 我发现JDK9中不可变集合和映射将引入一个影响它们遍历的随机源。这意味着迭代顺序将确实是随机的,至少在JVM的不同运行中。
由于规范不保证集合和映射的任何遍历/迭代顺序,所以这是完全可以接受的。事实上,代码不能依赖于实现特定的细节,而是要依赖于规范。
我知道在今天的JDK 8中,如果我有一个i.e. 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调用,那么我们希望这种奇怪的行为会更频繁地表现出来,并且实际上我们希望在测试时...
因此,动机是清晰的,并且很明显这种随机化只会影响新的不可变集合和映射。
我的问题是:是否存在其他的动机以进行这种随机化,它有什么优势?

3
我欢迎这个。仅在2017年,我就亲自修复了由于依赖HashSets和HashMaps的迭代顺序而导致的两个错误。 - VGR
1
@VGR 我也欢迎它。我认为这将会非常有帮助。 - fps
2
@VGR 当我们从Java7迁移到Java8时,我们不得不重新编写已有代码的平均7%,因为某些代码片段依赖于HashMap的顺序。 - Eugene
2个回答

22

事实证明,随机迭代顺序还有另一个原因。这并不是什么秘密。我认为在那次演讲中解释过了,但可能不够清楚。我可能在OpenJDK邮件列表或内部讨论中提到过。

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

这个问题比大多数人想象的要严重得多。历史上,HashSetHashMap从未指定特定的迭代顺序。然而,时不时地,实现需要进行更改,以提高性能或修复错误。对迭代顺序的任何更改都会引发用户的强烈反感。多年来,围绕更改迭代顺序积累了很多阻力,这使得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版本发布时更改一次。
这是最糟糕的情况。主要版本只会每隔几年发布一次。当一个版本发布后,所有人的代码都会出问题。会有很多哭泣和牙 gnashing,人们会修复他们的代码,并承诺永远不会再更改迭代顺序。几年后,将编写新代码,无意中依赖于迭代顺序。然后我们会发布另一个更改迭代顺序的主要版本,这将再次打破所有人的代码。并且这个循环将重新开始。
我想避免为新收藏重复此循环。我追求的政策是尽可能频繁地更改它。最初,顺序在每个迭代中都会更改,但这会带来一些开销。最终,我们定居于每个JVM调用一次。成本是每个表探测的32位XOR操作,我认为这相当便宜。
在某种程度上,这是关于“加强”应用程序代码。如果更改迭代顺序会破坏代码,则更频繁地破坏该代码会导致其发展出抵抗这种破坏的能力。当然,代码不会自己变得更强大;需要更多开发人员的努力才能实现。人们将合理地抱怨必须做出这些额外的工作。

然而,让应用程序代码“更加坚韧”在某种程度上是次要的,与保留更改实现的自由这一目标相比。保留HashMap的迭代顺序使其更难以维护。新集合的随机迭代顺序意味着在修改它们时我们不必担心保留迭代顺序,因此它们更易于维护和增强。

例如,当前实现(Java 9,预GA,2017年7月)有三个基于字段的Set实现(Set0Set1Set2)和一个基于数组的实现(SetN),它使用简单的闭散列和线性探测方案。将来,我们可能希望添加一个可容纳三个元素的Set3实现。或者,我们可能希望将SetN的冲突解决策略从线性探测更改为更复杂的方法。如果我们不必处理保留迭代顺序,甚至可以在小版本中完全重构实现。

总之,这种权衡的结果是应用程序开发人员必须做更多的工作,以确保他们的代码能够抵御迭代顺序更改所带来的破坏。这很可能是他们在某个时候必须使用HashMap进行的工作。通过这种方式获得的好处是,JDK可以提供更好的性能和空间效率,使每个人都能从中受益。


嗨,Stuart,非常感谢您。我想您在那次演讲中提到了这一点,特别是关于如果需要保持迭代顺序稳定,则维护HashMap有多么困难的部分。然而,不知道为什么,我记住了我引用的内容,并且有点忽略了您在此处陈述的另一个原因。我知道这里没有秘密 :) 我只是想进一步了解您尝试解决的动机和问题。 - fps
2
我可以想象一种类似于字符串去重特性的“Set去重”,对于那些存活足够长时间以接受这种处理的Set,可以花更多的时间来找到更好的表大小/冲突解决参数。然后,在每次迭代中迭代顺序不会改变,但可能会在Set生命周期内发生变化。当然,这仅适用于不可变的集合。 - Holger
1
@Holger,这绝对是一个有趣的想法! - Eugene
4
@Holger,是的,有趣的想法。我认为这类似于HashMap如何根据需要从链表动态更改其内部表示形式为树形结构。不可变集合和映射的规范没有说明迭代顺序可以更改的频率,但我希望当前的随机化方案(每个JVM实例一次)足够频繁,使得稍微更改迭代顺序不应该引起任何问题。 - Stuart Marks

6
那句话和你的想法已经有力地证明了这样做的优势。那么你还需要什么?
换句话说:Java的“创始人”之一宣称他们实现“随机映射/集合顺序”的动机是为了“教育”Java程序员不要期望或依赖任何特定顺序。因此,答案(可能带有主观色彩)是质疑你的期望。
主管告诉你他们这样做的想法。没有理由认为他们在这个设计决策中“隐藏”其他动机。
相反,我们可能会找到反对花费额外的努力来实现这种程度的随机性的论据 - JVM可能正在花费相当多的额外CPU周期 - 仅仅是为了实现不确定行为(通常我们尽力避免这种情况)。

嗨!谢谢您的回答。是的,我同意您的观点,即教育程序员已经足够成为动力了。我并不是说还有另一个秘密动机,我只是想知道是否还有其他动机,例如帮助保护特定哈希码攻击针对的应用程序等。另外,您能说一下这方面的优势吗? - fps
3
@GhostCat 提到了额外的工作量。当然,当你查看实现时,你会发现它非常巧妙,并且几乎不会增加任何开销,而且只在创建过程中增加一点点。 - Nicolai Parlog

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接