HashSet的迭代顺序

Question

如果每个对象添加到java.util.HashSet中以确定性的方式实现的Object.Equals()和是Object.hashCode(),是迭代顺序在HashSet的保证用于每加入相同组元素是相同的,而不管的他们被添加的顺序？

奖金问题:如果插入顺序相同怎么办？

(假设Sun JDK6具有相同的HashSet初始化.)

编辑:我原来的问题不明确.它不是关于HashSet的一般契约,而是Sun在JDK6中对HashSet的实现提供了关于确定性的保证.它本质上是非确定性的吗？什么影响其迭代器使用的顺序？

Answer 1

绝对不.

每当您遇到存储桶冲突时,插入顺序会直接影响迭代顺序:

当两个元素在同一个桶中结束,已插入第一个也将是迭代过程中第一个返回值,至少如果冲突处理和迭代的实现是直接的(和一个Sun的java.util.HashMap是)

Answer 2

对于这样的事情没有"官方"保证.我会说同样的HashSet实现的实例很可能是真的,以相同的方式初始化.但是我已经看到了例如Java 5和6之间迭代顺序不同的情况.

此外,由于重新散列,对于使用不同大小初始化的相同HashSet实现的实例可能会有所不同.也就是说,如果你有100种元素和两组,一用一尺寸大于100,另配备更小的尺寸进行初始化,第二个将得到重新分配和元素改头换面几次,而填满.这可能导致映射到同一桶的元素以不同的顺序被添加(并因此被迭代).

在Java4及更高版本中,您可以LinkedHashSet保证迭代顺序是其元素的插入顺序.

Answer 3

根据javadoc:

此类实现Set接口,由哈希表(实际上是HashMap实例)支持.它不能保证集合的迭代顺序; 特别是,它不保证订单会随着时间的推移保持不变.[...]此类的迭代器方法返回的迭代器是快速失败的:如果在创建迭代器后的任何时间修改了该集合

方法iterator:

返回此set中元素的迭代器.元素以无特定顺序返回.

所以我认为你不能做出这样的假设.

Answer 4

想要确认/提前评论.简而言之,不要以一致的顺序依赖于HashSet迭代.这可能并将在您的系统中引入错误.

我们刚刚发现并修复了HashSet中迭代顺序不一致的错误,即使:

并使用LinkedHashSet修复它.

感谢早期的海报:)