23

如果添加到 java.util.HashSet 的每个对象都以确定性方式实现 Object.equals() 和 Object.hashCode(),那么无论添加的每个相同元素集如何,HashSet 上的迭代顺序都保证相同添加它们的顺序?

额外的问题:如果插入顺序也相同怎么办?

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

编辑:我原来的问题不清楚。这不是关于 HashSet 的一般合同,而是 Sun 在 JDK6 中的 HashSet 实现提供了关于确定性的保证。它本质上是非确定性的吗?是什么影响了它的迭代器使用的顺序?

4

9 回答 9

21

绝对不。

每当发生桶碰撞时,插入顺序都会直​​接影响迭代顺序:

当两个元素最终在同一个桶中时,插入的第一个元素也将是迭代过程中返回的第一个元素,至少如果碰撞处理和迭代的实现很简单(Sun 的那个java.util.HashMap是)

于 2010-04-24T13:39:17.713 回答
12

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

此外,由于重新散列,对于以不同大小初始化的相同 HashSet 实现的实例,它可能会有所不同。即,如果你有 100 个元素和两组,一组初始化的大小大于 100,另一组的大小要小得多,第二个将被重新分配,并且它的元素在填充时会重新散列几次。这可能会导致映射到相同存储桶的元素以不同的顺序添加(并因此迭代)。

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

于 2010-04-24T13:30:27.327 回答
10

想要确认/支持之前的评论。简而言之,不要依赖 HashSet 以一致的顺序迭代。这会并且会在您的系统中引入错误。

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

  • 相同的插入顺序。
  • 具有有效 equals() 和 hashCode() 方法的类的对象。

并通过使用 LinkedHashSet 修复它。

感谢之前的海报:)

于 2010-11-05T21:02:28.637 回答
9

根据javadoc:

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

和方法iterator

返回此集合中元素的迭代器。返回的元素没有特定的顺序。

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

于 2010-04-24T13:29:51.163 回答
3

永远不要对你放入 HashSet 的任何东西的迭代顺序做出假设,因为它的合同明确规定你不能以任何方式指望它。如果要保持插入顺序,请使用LinkedHashSet ;如果要保持自然排序顺序,请使用TreeSet 。

于 2010-04-24T13:42:05.537 回答
2

出现的订单对象将取决于 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]
于 2010-11-05T21:37:01.113 回答
1

不,这不能保证。

首先,不同的 JVM 可能会以不同的方式实现 HashSet 算法(只要它符合 HashSet 规范),因此在不同的 JVM 上会得到不同的结果。

其次,该算法在构建不同的桶(哈希表算法的一部分)时可能依赖于非确定性因素。

于 2010-04-24T13:29:45.433 回答
0

我确信 Java 开发人员希望您假设答案是“否”。特别是,对于哈希表,为什么它们会让其他不需要此属性的人变慢以保证哈希冲突的对象(相同的 hashCode % 大小)以相同的顺序被观察到,而不管它们的顺序如何投放?

于 2010-04-24T13:31:19.020 回答
0

不能做出这样的假设。javadoc 说:

该类实现了由哈希表(实际上是 HashMap 实例)支持的 Set 接口。它不保证集合的迭代顺序;特别是,它不保证订单会随着时间的推移保持不变。

您可以获得的最接近的是使用LinkedHashSet,它维护插入顺序。

于 2010-04-24T13:40:59.113 回答