Java遍历HashSet为什么输出是有序的？

看到《Thinking in Java》中有这么一段代码，书中给出的Output是无序的，可是我实际运行出来是有序的，就是从0递增到29，这是为什么呢？
[code]public class SetOfInteger {
public static void main(String[] args){
      Random rand=new Random(47);
      Set intset=new HashSet();
      for (int i=0;i

有关回应 · 2022-2-9 13:53:07

首先 @赵劼大大的答案就是正解了。“不保证有序”和“保证无序”不等价，HashSet的iterator是前者而不是后者，所以在一次运行中看到有序的结果也是正常的，但不能依赖这个有序行为。
况且HashSet并不关心key的“排序”，就算其iterator“有序”通常也是说“按元素插入顺序”（LinkedHashSet就支持插入顺序遍历）。题主在此看到的所谓“有序”纯粹是个巧合。

然后我复制粘贴了题主的代码运行了一次：

$ java SetOfInteger0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 16 19 18 21 20 23 22 25 24 27 26 29 28 $ java -versionjava version "1.7.0-internal-zing_99.99.99.99.dev"Zing Runtime Environment for Java Applications (build 1.7.0-internal-zing_99.99.99.99.dev-b65)Zing 64-Bit Tiered VM (build 1.7.0-zing_99.99.99.99.dev-b870-product-azlinuxM-X86_64, mixed mode)

复制代码

（Zing JDK7的开发版）
就不是有序的嘛。同样在Oracle JDK7u51上也是如此：

$ java SetOfInteger0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 16 19 18 21 20 23 22 25 24 27 26 29 28 $ java -versionjava version "1.7.0_51"Java(TM) SE Runtime Environment (build 1.7.0_51-b13)Java HotSpot(TM) 64-Bit Server VM (build 24.51-b03, mixed mode)

复制代码

换到Zing JDK8：

$ java SetOfInteger0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 $ java -versionjava version "1.8.0-internal-zing_99.99.99.99.dev"Zing Runtime Environment for Java Applications (build 1.8.0-internal-zing_99.99.99.99.dev-b65)Zing 64-Bit Tiered VM (build 1.8.0-zing_99.99.99.99.dev-b870-product-azlinuxM-X86_64, mixed mode)

复制代码

再换到Oracle JDK8u25：

$ java SetOfInteger0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 $ java -versionjava version "1.8.0_25"Java(TM) SE Runtime Environment (build 1.8.0_25-b17)Java HotSpot(TM) 64-Bit Server VM (build 25.25-b02, mixed mode)

复制代码

就看到了题主说的有序行为。

JDK8的HashSet实现变了，导致元素插入的位置发生了变化；iterator自身实现的顺序倒没变，还是按照内部插入的位置顺序来遍历，于是题主就看到了JDK7和JDK8的结果不一样。具体来说，是JDK7与JDK8的java.util.HashMap的hash算法以及HashMap的数据布局发生了变化。

题主插入HashSet的是Integer，其hashCode()实现就返回int值本身。所以在对象hashCode这一步引入了巧合的“按大小排序”。
然后HashMap.hash(Object)获取了对象的hashCode()之后会尝试进一步混淆。
JDK8版java.util.HashMap内的hash算法比JDK7版的混淆程度低；在[0, 2^32-1]范围内经过HashMap.hash()之后还是得到自己。题主的例子正好落入这个范围内。外加load factor正好在此例中让这个HashMap没有hash冲突，这就导致例中元素正好按大小顺序插入在HashMap的开放式哈希表里。
根据它的实现特征，把题主的例子稍微修改一下的话：
[code]$ cat SetOfInteger.java import java.util.*;public class SetOfInteger { public static void main(String[] args){ Random rand=new Random(47); Set intset=new HashSet(); for (int i=0;i

有关回应 · 2022-2-9 13:53:08

实现是会变的，HashSet的迭代器在输出时“不保证有序”，但也不是“保证无序”。也就是说，输出时有序也是允许的，但是你的程序不应该依赖这一点。

有关回应 · 2022-2-9 13:53:09

有关回应 · 2022-2-9 13:53:10

我觉得有必要来厘清一下我们说的有序和无序到底指的是什么。

有序和无序的概念远不是你字面上看的这样简单。

举个栗子，List是有序的？还是无序的？

通常情况下，我们说一个列表是有序的，是指：
这个列表严格按照指定的偏序关系（Comparable接口等定义）存放或检索元素。

我们说一个列表是无序的，是指：
这个列表存放或检索元素的顺序是不确定的。

根据这两个定义，我们可以得到第三种情况，也就是List这种：
他既不是有序的，因为存放或检索元素不按照指定的偏序关系。
他也不是无序的，因为这个列表存放或检索元素的顺序是确定的。

所以实质上，一般语境中的有序无序并不是反义词，无序不等价于非有序。

更重要的，有序是一个保证，不是结果。
我们按照某个顺序往List里面塞元素，我们检索List的时候，自然看起来是有序的，我们能说List是一个有序列表吗？不能，因为在我们的语境中，有序列表是指，其检索的顺序严格遵循偏序关系，与你存放的顺序无关。

有关回应 · 2022-2-9 13:53:11

It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.

Java遍历HashSet为什么输出是有序的？

5 个回复

浏览过的版块