奖励问题:如果插入顺序也相同呢?
(假设使用相同的HashSet初始化的Sun JDK6。)
(以下是修订版)我的原始问题不够清晰。这并不是关于HashSet的一般约定,而是关于Sun在JDK6中实现的HashSet提供了什么样的确定性保证。它本质上是不确定的吗?它的迭代器使用的顺序受什么影响?
绝对不行。
插入顺序会直接影响到在桶碰撞时的迭代顺序:
当两个元素被放进了同一个桶中,如果冲突处理和迭代的实现是直接的(比如Sun的java.util.HashMap
),那么第一个被插入的元素也将会是在迭代时返回的第一个元素。
对于这种情况,没有官方的保证。我认为,对于相同的HashSet实现以及相同的初始化方式,这种说法很可能是正确的。但是,例如Java 5和6之间的迭代顺序就有所不同。
此外,即使是相同的HashSet实现,如果初始化大小不同,也可能会有所差异,这是由于重新哈希导致的。例如,如果你有100个元素和两个集合,一个使用比100更大的大小进行初始化,另一个使用较小的大小进行初始化,那么第二个集合将在填充时被重新分配和重哈希多次。这可能导致映射到相同桶中的元素按不同的顺序添加(并因此在迭代时以不同的顺序出现)。
在Java 4及其后续版本中,您可以使用LinkedHashSet
,它保证了迭代顺序是按照元素插入的顺序排列的。
想要确认/点赞之前的评论。简而言之,不要依赖HashSet迭代以保持一致的顺序。这可能会在您的系统中引入错误。
我们刚刚发现并修复了一个bug,即使使用:
在HashSet中,迭代顺序也是不一致的。
我们通过使用LinkedHashSet来解决这个问题。
感谢早期的帖子作者们 :)
永远不要对放入HashSet中的任何内容的迭代顺序做出假设,因为它的契约明确表示您不能以任何方式依赖它。如果您想保持插入顺序,请使用LinkedHashSet;如果您想保持自然排序顺序,请使用TreeSet。
HashSet 中的元素出现顺序取决于 HashSet 的最终桶数。通过更改负载因子和/或初始容量,可以更改元素的顺序。
在下面的示例中,您可以看到每种配置都会产生不同的顺序。
public static void main(String...args) throws IOException {
printOrdersFor(8, 2);
printOrdersFor(8, 1);
printOrdersFor(8, 0.5f);
printOrdersFor(32, 1f);
printOrdersFor(64, 1f);
printOrdersFor(128, 1f);
}
public static void printOrdersFor(int size, float loadFactor) {
Set<Integer> set = new HashSet<Integer>(size, loadFactor);
for(int i=0;i<=100;i+=10) set.add(i);
System.out.println("new HashSet<Integer>("+size+", "+loadFactor+") adding 0,10, ... 100 => "+set);
}
打印
new HashSet<Integer>(8, 2.0) adding 0,10, ... 100 => [0, 50, 100, 70, 40, 10, 80, 20, 90, 60, 30]
new HashSet<Integer>(8, 1.0) adding 0,10, ... 100 => [0, 50, 100, 70, 20, 80, 10, 40, 90, 30, 60]
new HashSet<Integer>(8, 0.5) adding 0,10, ... 100 => [0, 100, 70, 40, 10, 50, 20, 80, 90, 30, 60]
new HashSet<Integer>(32, 1.0) adding 0,10, ... 100 => [0, 100, 70, 40, 10, 50, 80, 20, 90, 60, 30]
new HashSet<Integer>(64, 1.0) adding 0,10, ... 100 => [0, 70, 10, 80, 20, 90, 30, 100, 40, 50, 60]
new HashSet<Integer>(128, 1.0) adding 0,10, ... 100 => [0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
不,这并不是保证的。
首先,不同的JVM可能会以不同的方式实现HashSet算法(只要符合HashSet规范),因此在不同的JVM上会得到不同的结果。
其次,该算法在构建不同的桶(哈希表算法的一部分)时可能依赖于非确定性因素。
我相信Java开发者希望你假设答案是“不行”。特别是对于哈希表,为什么他们要让那些不需要保证哈希冲突对象(相同的hashCode % size)以相同顺序被观察到的人变慢呢?而无论它们被放置的顺序如何。
不能做出这样的假设。Javadoc说:
该类实现了Set接口,由哈希表(实际上是HashMap实例)支持。它不保证集合的迭代顺序;特别是,它不保证顺序会随时间保持不变。
最接近的方法是使用LinkedHashSet,它维护插入顺序。
HashSet
的迭代顺序有什么行为?”或者更具体地说,“对于给定的一组特定元素,Java是否保证HashSet
具有确定性的迭代顺序?”对于OP而言,这很重要,因为您无法保证您的代码始终会由特定的Java JDK运行。 - Arthur