郎行天下

要么就别做，要做就做好。

2016.12.14

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

今天运行《疯狂Java讲义》中 8.2 中的 IteratorTest.java 时，不管运行多少次，结果输出都是一致的，如下所示：



Code   ViewPrint




  1. package com.menglanglang.java.collection;


  2. import java.util.*;

  3. /**

  4.  * Description:

  5.  * <br/>网站: <a href="https://www.crazyit.org">疯狂Java联盟</a>

  6.  * <br/>Copyright (C), 2001-2016, Yeeku.H.Lee

  7.  * <br/>This program is protected by copyright laws.

  8.  * <br/>Program Name:

  9.  * <br/>Date:

  10.  * @author Yeeku.H.Lee kongyeeku@163.com

  11.  * @version 1.0

  12.  */

  13. public class IteratorTest

  14. {

  15.     public static void main(String[] args)

  16.     {

  17.         // 创建集合、添加元素的代码与前一个程序相同

  18.         Collection books = new HashSet();

  19.         books.add("疯狂Java讲义");

  20.         books.add("轻量级Java EE企业应用实战");

  21.         books.add("疯狂Android讲义");

  22.         // 获取books集合对应的迭代器

  23.         Iterator it = books.iterator();

  24.         while(it.hasNext())

  25.         {

  26.             // it.next()方法返回的数据类型是Object类型，因此需要强制类型转换

  27.             String book = (String)it.next();

  28.             System.out.println(book);

  29.             if (book.equals("疯狂Java讲义"))

  30.             {

  31.                 // 从集合中删除上一次next方法返回的元素

  32.                 it.remove();

  33.             }

  34.             // 对book变量赋值，不会改变集合元素本身

  35.             book = "测试字符串";   //①

  36.         }

  37.         System.out.println(books);

  38.     }

  39. }

  40. // 输出：

  41. // 疯狂Android讲义

  42. // 轻量级Java EE企业应用实战

  43. // 疯狂Java讲义

  44. // [疯狂Android讲义, 轻量级Java EE企业应用实战]



很奇怪，明明书上说 Set 是无序的，那么输出应该是随机的才对，为何输出总是一定的呢？不管 add 的顺序如何，输出总是一定。

上网查了下，以前也有很多网友有这样的疑惑，详情如下：
看到《Thinking in Java》中有这么一段代码，书中给出的Output是无序的，可是我实际运行出来是有序的，就是从0递增到29，这是为什么呢？


public class SetOfInteger {
public static void main(String[] args){
Random rand=new Random(47);
Set<Integer> intset=new HashSet<Integer>();
for (int i=0;i<10000;i++){
intset.add(rand.nextInt(30));
}
Iterator<Integer> iterator=intset.iterator();
while (iterator.hasNext()){
System.out.print(iterator.next()+" ");
}
}
}


网友 RednaxelaFX 的回答特别不错，这里也顺便记录并分享：

作者：RednaxelaFX
链接：https://www.zhihu.com/question/28414001/answer/40733996
来源：知乎
著作权归作者所有，转载请联系作者获得授权。

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


$ java SetOfInteger
0 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 -version
java 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 SetOfInteger
0 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 -version
java 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 SetOfInteger
0 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 -version
java 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 SetOfInteger
0 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 -version
java 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的开放式哈希表里。
根据它的实现特征，把题主的例子稍微修改一下的话：


$ cat SetOfInteger.java
import java.util.*;

public class SetOfInteger {
public static void main(String[] args){
Random rand=new Random(47);
Set<Integer> intset=new HashSet<Integer>();
for (int i=0;i<10000;i++){
intset.add(rand.nextInt(30) + (1 << 16));
}
Iterator<Integer> iterator=intset.iterator();
while (iterator.hasNext()){
System.out.print((iterator.next() - (1 << 16)) +" ");
}
}
}
$ java SetOfInteger
1 0 3 2 5 4 7 6 9 8 11 10 13 12 15 14 17 16 19 18 21 20 23 22 25 24 27 26 29 28
$ java -version
java 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)


就可以看到顺序不一样了。修改的内容就是把插入的数字先加上2的16次方，然后拿出来之后再减去2的16次方，而已 ^_^



这里如果想要知道输出的顺序是随机的，可以简单在 add 时，加入的串稍微变一下，就可以看出顺序与原来的不一样了，测试如下：



Code   ViewPrint




  1. package com.menglanglang.java.collection;


  2. import java.util.*;

  3. /**

  4.  * Description:

  5.  * <br/>网站: <a href="https://www.crazyit.org">疯狂Java联盟</a>

  6.  * <br/>Copyright (C), 2001-2016, Yeeku.H.Lee

  7.  * <br/>This program is protected by copyright laws.

  8.  * <br/>Program Name:

  9.  * <br/>Date:

  10.  * @author Yeeku.H.Lee kongyeeku@163.com

  11.  * @version 1.0

  12.  */

  13. public class IteratorTest

  14. {

  15.     public static void main(String[] args)

  16.     {

  17.         // 创建集合、添加元素的代码与前一个程序相同

  18.         Collection books = new HashSet();

  19.         books.add("孟疯狂Java讲义");

  20.         books.add("孟轻量级Java EE企业应用实战");

  21.         books.add("孟疯狂Android讲义");

  22.         // 获取books集合对应的迭代器

  23.         Iterator it = books.iterator();

  24.         while(it.hasNext())

  25.         {

  26.             // it.next()方法返回的数据类型是Object类型，因此需要强制类型转换

  27.             String book = (String)it.next();

  28.             System.out.println(book);

  29.             if (book.equals("疯狂Java讲义"))

  30.             {

  31.                 // 从集合中删除上一次next方法返回的元素

  32.                 it.remove();

  33.             }

  34.             // 对book变量赋值，不会改变集合元素本身

  35.             book = "测试字符串";   //①

  36.         }

  37.         System.out.println(books);

  38.     }

  39. }

  40. // 输出：

  41. // 孟疯狂Java讲义

  42. // 孟疯狂Android讲义

  43. // 孟轻量级Java EE企业应用实战

  44. // [孟疯狂Java讲义, 孟疯狂Android讲义, 孟轻量级Java EE企业应用实战]



共勉~~
#Java

评论

©郎行天下 | Powered by LOFTER