是什么导致 java.util.HashSet 和 HashMap.keySet() 类的 iterator() 排序稍微不可预测? [英] What causes the slightly unpredictable ordering of the iterator() for the java.util.HashSet and HashMap.keySet() classes?

问题描述

六年前，我花了几天时间试图找出我完全确定的框架在哪里随机响应.在仔细追踪整个框架以确保它都使用相同的 Random 实例之后，我继续通过单步代码进行追踪.这是高度重复的迭代自调用代码.更糟糕的是，该死的效果只有在完成大量迭代后才会出现.+6 小时后，当我在 javadoc 中发现 HashSet.iterator() 的一行表明它不能保证返回元素的顺序时，我终于束手无策了.然后，我检查了整个代码库，并用 LinkedHashSet 替换了所有 HashSet 实例.低调地看，我的框架正好适合确定性生活！啊！

Six years ago, I burned several days trying to hunt down where my perfectly deterministic framework was responding randomly. After meticulously chasing the entire framework ensuring that it was all using the same instance of Random, I then kept chasing by single stepping code. It was highly repetitive iterative self-calling code. Worse, the damn effect would only show up after a huge number of iterations were completed. And after +6 hours, I was finally at wits end when I discovered a line in the javadoc for HashSet.iterator() indicating it doesn't guarantee the order in which it will return elements. I then went through my entire code base and replaced all instances of HashSet with LinkedHashSet. And low-and-behold, my framework sprang right to deterministic life! ARGH!

我现在又一次经历了同样的 FREAKIN 影响(至少这次只有 3 小时).无论出于何种原因，我都错过了 HashMap 的 keySet() 的行为方式相同的小细节.

I have now just experienced this same FREAKIN affect, again (at least it was only 3 hours this time). For whatever reason, I missed the small detail that HashMap happens to BEHAVE THE SAME WAY for its keySet().

这是一个关于这个主题的 SO 线程，尽管讨论从未完全回答我的问题:HashSet 的迭代顺序

Here's an SO thread on this subject, although the discussion never quite answers my question: Iteration order of HashSet

所以，我很好奇为什么会发生这种情况.鉴于这两次我都有一个巨大的单线程 Java 应用程序在同一台计算机上以完全相同的 JVM 参数(从同一个批处理文件多次运行)爬过完全相同的实例化/插入空间，几乎没有其他任何东西在运行，这可能会扰乱JVM 这样 HashSet 和 HashMap 在经过大量迭代后会出现不可预测的行为(并非像 javadoc 所说的不依赖于顺序那样不一致)?

So, I am curious as to why this might occur. Given both times I had a huge single threaded java application crawling through exactly the same instantiation/insertion space with exactly the same JVM parameters (multiple runs from the same batch file) on the same computer with almost nothing else running, what could possibly perturb the JVM such that HashSet and HashMap would, after an enormous number of iterations, behave unpredictably (not inconsistenly as the javadoc says not to depend upon the order)?

从源代码(这些类在 java.util 中的实现)或您对 JVM 的了解(也许某些 GC 会影响内部 java 类在分配内部内存空间时获得非零内存的位置)有什么想法?

Any ideas around this from either the source code (implementation of these classes in java.util) or from your knowledge of the JVM (perhaps some GC affect where internal java classes get non-zeroed memory when allocating internal memory spaces)?

推荐答案

我之前遇到过这个问题，顺序不是重要，但确实影响了结果.

I've struck this before, where the order wasn't important, but did affect the results.

Java 的多线程特性意味着使用完全相同的输入重复运行可能会受到(例如)分配新内存块所需时间的微小时间差异的影响，这有时可能需要分页以磁盘以前的内容，在其他时候不需要.不使用该页面的其他线程可能会继续执行，当考虑到 System 对象时，您可能会以不同的对象创建顺序结束.

The multi-threaded nature of Java means that repeated runs with exactly the same inputs can be affected by slight timing differences in (for example) how long it takes to allocate a new block of memory, which might sometimes require paging out to disk the previous contents, and at other times that isn't needed. Some other thread not using that page may proceed, and you could end up with a different order of object creation, when System objects are taken into account.

这会影响 JVM 不同运行中等效对象的 Object.hashCode() 结果.

That can affect the Object.hashCode() result for the equivalent object in different runs of the JVM.

对我来说，我决定增加使用 LinkedHashMap 的小开销，以便能够重现我正在运行的测试的结果.

For me, I decided to add the small overhead of using a LinkedHashMap, in order to be able to reproduce the results of the tests I was running.

这篇关于是什么导致 java.util.HashSet 和 HashMap.keySet() 类的 iterator() 排序稍微不可预测?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！