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 回答