百科问答小站 logo
百科问答小站 font logo



Java遍历HashSet为什么输出是有序的? 第1页

  

user avatar   Ivony 网友的相关建议: 
      

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


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

举个栗子,List是有序的?还是无序的?


通常情况下,我们说一个列表是有序的,是指:

这个列表严格按照指定的偏序关系(Comparable接口等定义)存放或检索元素

我们说一个列表是无序的,是指:

这个列表存放或检索元素的顺序是不确定的


根据这两个定义,我们可以得到第三种情况,也就是List这种:

既不是有序的,因为存放或检索元素不按照指定的偏序关系。

也不是无序的,因为这个列表存放或检索元素的顺序是确定的


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


更重要的,有序是一个保证,不是结果。

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


user avatar   rednaxelafx 网友的相关建议: 
      

首先

@赵劼

大大的答案就是正解了。“不保证有序”和“保证无序”不等价,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次方,而已 ^_^


user avatar   jeffz 网友的相关建议: 
      

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




  

相关话题

  GitHub 上可供新手阅读和玩耍的 Java 项目有哪些? 
  作为计算机专业学生,最应该学习的课程前五位是什么? 
  C++ 有哪些缺点? 
  听说过面向工资编程吗?面向工资编程是怎样一种体验? 
  以现在的编程手段做得不到真随机吗? 
  C# 语言和 .NET 框架相比 Java、PHP、Python 等 web 开发技术有哪些优劣? 
  土豪程序员的生活是怎样的? 
  为什么要开源? 
  为什么依赖注入只在 Java 技术栈中流行,在 go 和 cpp 没有大量使用? 
  随着互联网的崛起,还有必要学习 C++ 吗?貌似 C++ 越来越难找工作了... 

前一个讨论
大专出身,学java的工资会比其他行业工资高么?从事两年后月薪八千左右是正常水平?
下一个讨论
为什么大部分中央处理器(CPU)不能直接对内存中的数据进行运算?





© 2024-11-09 - tinynew.org. All Rights Reserved.
© 2024-11-09 - tinynew.org. 保留所有权利