轉(zhuǎn)自知乎

看到《Thinking in Java》中有這么一段代碼，書中給出的Output是無序的，可是我實(shí)際運(yùn)行出來是有序的，就是從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()+" ");
? ? ? ?}
? ?}
}

首先 @趙劼 大大的答案就是正解了。“不保證有序”和“保證無序”不等價(jià)，HashSet的iterator是前者而不是后者，所以在一次運(yùn)行中看到有序的結(jié)果也是正常的，但不能依賴這個(gè)有序行為。
況且HashSet并不關(guān)心key的“排序”，就算其iterator“有序”通常也是說“按元素插入順序”（LinkedHashSet就支持插入順序遍歷）。題主在此看到的所謂“有序”純粹是個(gè)巧合。

然后我復(fù)制粘貼了題主的代碼運(yùn)行了一次：

$ 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的開發(fā)版）
就不是有序的嘛。同樣在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實(shí)現(xiàn)變了，導(dǎo)致元素插入的位置發(fā)生了變化；iterator自身實(shí)現(xiàn)的順序倒沒變，還是按照內(nèi)部插入的位置順序來遍歷，于是題主就看到了JDK7和JDK8的結(jié)果不一樣。具體來說，是JDK7與JDK8的java.util.HashMap的hash算法以及HashMap的數(shù)據(jù)布局發(fā)生了變化。

題主插入HashSet的是Integer，其hashCode()實(shí)現(xiàn)就返回int值本身。所以在對象hashCode這一步引入了巧合的“按大小排序”。
然后HashMap.hash(Object)獲取了對象的hashCode()之后會(huì)嘗試進(jìn)一步混淆。
JDK8版java.util.HashMap內(nèi)的hash算法比JDK7版的混淆程度低；在[0, 2^32-1]范圍內(nèi)經(jīng)過HashMap.hash()之后還是得到自己。題主的例子正好落入這個(gè)范圍內(nèi)。外加load factor正好在此例中讓這個(gè)HashMap沒有hash沖突，這就導(dǎo)致例中元素正好按大小順序插入在HashMap的開放式哈希表里。
根據(jù)它的實(shí)現(xiàn)特征，把題主的例子稍微修改一下的話：

$ 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)

就可以看到順序不一樣了。修改的內(nèi)容就是把插入的數(shù)字先加上2的16次方，然后拿出來之后再減去2的16次方，而已 ^_^

作者：RednaxelaFX
鏈接：https://www.zhihu.com/question/28414001/answer/40733996
來源：知乎
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

這里我看的不是很明白，他說的意思是JDK1.8版之后HashSet實(shí)現(xiàn)類的方法改變了，導(dǎo)致能夠產(chǎn)生無序的最小范圍擴(kuò)大了嗎？還是其他什么？

至于原HashSet實(shí)現(xiàn)類具體是怎么樣我還沒學(xué)不知道是什么樣子，看樣子好像是原來是沒有這個(gè)范圍的？不管是輸入多少輸出之后都是無序的，像視頻里一樣？懇請各位大大幫忙解答。