是什么导致java.util.HashSet和HashMap.keySet()类的iterator()稍微不可预测的排序？

Question

六年前,我烧了几天试图追捕我完全确定的框架随机响应的地方.在精心追逐整个框架确保它全部使用相同的Random实例后,我继续追逐单步执行代码.这是高度重复的迭代自调用代码.更糟糕的是,该死的效果只会在完成大量迭代后出现.在+6小时之后,当我在javadoc中为HashSet.iterator()发现一行时,我终于处于智慧状态,表明它不能保证返回元素的顺序.然后我浏览了整个代码库,并用LinkedHashSet替换了所有HashSet实例.而且,我的框架正好向确定性生活迈进!哎呀!

我现在刚刚经历过同样的FREAKIN影响(至少这次只有3个小时).无论出于何种原因,我都错过了HashMap碰巧为其keySet()获得相同方式的细节.

这是关于这个主题的SO线程,虽然讨论从来没有完全回答我的问题:HashSet的迭代顺序

所以,我很好奇为什么会这样.鉴于我两次都有一个庞大的单线程java应用程序在完全相同的实例化/插入空间中使用完全相同的JVM参数(来自同一批处理文件的多次运行)在同一台计算机上运行,​​几乎没有其他任何运行,这可能会扰乱JVM使得HashSet和HashMap在经过大量迭代之后会表现得不可预测(并不是因为javadoc说不依赖于顺序而不一致)？

从源代码(java.util中的这些类的实现)或者你对JVM的了解(可能是某些GC影响内部java类在分配内部存储空间时获得非零内存的位置)的任何想法？

Answer 1

简答

有一个权衡.如果您希望对元素进行分摊的常量时间O(1)访问,那么迄今为止的技术依赖于像散列这样的随机方案.如果您想要对元素进行有序访问,那么最佳工程权衡只能为您提供O(ln(n))性能.对于你的情况,也许这并不重要,但是即使相对较小的结构,恒定时间和对数时间之间的差异也会产生很大的差异.

所以,是的,您可以仔细查看代码并仔细检查,但它归结为一个相当实际的理论事实.现在是刷掉那些支撑你房子基础的下垂角落的Cormen(或Googly Bookiness)副本上的灰尘的好时机,看看第11章(哈希表)和第13章(红黑树).这些将分别填充JDK的HashMap和TreeMap实现.

答案很长

您不希望Map或Set返回键/成员的有序列表.这不是他们想要的.地图和集合结构不像基础数学概念那样排序,它们提供不同的性能.这些数据结构的(如@thejh指出)的目标是有效的摊销insert,contains和get时间,不保持排序.您可以了解如何维护散列数据结构以了解权衡取舍.看看关于Hash函数和哈希表的Wikipedia条目(具有讽刺意味的是,注意"无序映射"的Wiki条目重定向到后者)或计算机科学/数据结构文本.

请记住:除非您仔细查看合同是什么,否则不要依赖于ADT(特别是集合)的属性,例如订购,不变性,线程安全或其他任何内容.请注意,对于Map,Javadoc清楚地说:

地图的顺序定义为地图集合视图上的迭代器返回其元素的顺序.一些地图实现,比如TreeMap类,对它们的顺序做出了特定的保证; 其他人,比如HashMap类,没有.

并Set.iterator()有类似的:

返回此set中元素的迭代器.元素以无特定顺序返回(除非此集合是某个提供保证的类的实例).

如果您想要这些的有序视图,请使用以下方法之一:

• 如果它只是一个Set,也许你真的想要一个SortedSet像TreeSet
• 使用a TreeMap,允许自然排序键或特定排序通过Comparator
• 抽象你的数据结构,如果这是你想要的行为,它可能是一个特定于应用程序的东西,并且同时维护一个SortedSet密钥和一个密钥Map,它将在摊销时间内表现更好.
• 得到Map.keySet()(或者只是Set你感兴趣的)并将其放入SortedSet诸如TreeSet使用自然顺序或特定的Comparator.
• 在排序之后迭代Map.Entry<K,V>使用Map.entrySet().iterator().例如for (final Map.Entry<K,V> entry : new TreeSet(map.entrySet())) { },有效地访问键和值.
• 如果您只是这样做一次,您可以从结构和使用中获取一组值Arrays.sort(),这些值具有不同的性能配置文件(空间和时间).

链接到源

如果您想查看juHashSet和juHashMap的源代码,可以在GrepCode上找到它们.请注意,HashSet只是HashMap的糖.为什么不总是使用排序版本？好吧,正如我在上面提到的那样,性能不同而且在某些应用中很重要.请在此处查看相关的SO问题.您还可以在底部看到一些具体的性能数字(我没有仔细查看以确认这些是准确的,但它们恰好证实了我的观点,所以我会轻松地传递链接.:-)

Answer 2

我以前遇到过这个问题，顺序并不重要，但确实影响了结果。

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

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

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