摘要：但是，如果像上例中只取最后幾位的時候，這可不是什么好事，即使我的數(shù)據(jù)分布很散亂，但是哈希沖突仍然會很嚴重。由于我們所創(chuàng)建的是類型的，這也是最巧的一點，類型的返回值就是其值本身，而存儲的時候元素通過一些運算后會得出自己在數(shù)組中所處的位置。

《Core Java Volume I—Fundamentals》中對HashSet的描述是這樣的：

HashSet：一種沒有重復元素的無序集合

解釋：我們一般說HashSet是無序的，它既不能保證存儲和取出順序一致，更不能保證自然順序（a-z）

下面是《Thinking in Java》中的使用Integer對象的HashSet的示例

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<10000; i++)
       intset.add(rand.nextInt(30));
   System.out.println(intset);
}
}    /*    Output:
[15, 8, 23, 16, 7, 22, 9, 21, 6, 1 , 29 , 14, 24, 4, 19, 26, 11, 18, 3, 12, 27, 17, 2, 13, 28, 20, 25, 10, 5, 0]

在0-29之間的10000個隨機數(shù)被添加到了Set中，大量的數(shù)據(jù)是重復的，但輸出結(jié)果卻每一個數(shù)只有一個實例出現(xiàn)在結(jié)果中，并且輸出的結(jié)果沒有任何規(guī)律可循。 這正與其不重復，且無序的特點相吻合。

看來兩本書的結(jié)果，以及我們之前所學的知識，看起來都是一致的，一切就是這么美好。

隨手運行了一下這段書中的代碼，結(jié)果卻讓人大吃一驚

//JDK1.8下 Idea中運行
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<10000; i++)
            intset.add(rand.nextInt(30));
        System.out.println(intset);
    }
}

//運行結(jié)果
[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]

嗯！不重復的特點依舊吻合，但是為什么遍歷輸出結(jié)果卻是有序的？？？

寫一個最簡單的程序再驗證一下：

import java.util.*;

public class HashSetDemo {
    public static void main(String[] args) {

        Set hs = new HashSet();

        hs.add(1);
        hs.add(2);
        hs.add(3);

        //增強for遍歷
        for (Integer s : hs) {
            System.out.print(s + " ");
        }
    }
}

//運行結(jié)果
1 2 3 

我還不死心，是不是元素數(shù)據(jù)不夠多，有序這只是一種巧合的存在，增加元素數(shù)量試試

import java.util.*;

public class HashSetDemo {
    public static void main(String[] args) {
        
        Set hs = new HashSet();

        for (int i = 0; i < 10000; i++) {
            hs.add(i);
        }

        //增強for遍歷
        for (Integer s : hs) {
            System.out.print(s + " ");
        }
    }
}

//運行結(jié)果
1 2 3 ... 9997 9998 9999 

可以看到，遍歷后輸出依舊是有序的

通過一步一步分析源碼，我們來看一看，這究竟是怎么一回事，首先我們先從程序的第一步——集合元素的存儲開始看起，先看一看HashSet的add方法源碼：

// HashSet 源碼節(jié)選-JKD8
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

我們可以看到，HashSet直接調(diào)用HashMap的put方法，并且將元素e放到map的key位置（保證了唯一性 ）

順著線索繼續(xù)查看HashMap的put方法源碼：

//HashMap 源碼節(jié)選-JDK8
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

而我們的值在返回前需要經(jīng)過HashMap中的hash方法

接著定位到hash方法的源碼：

//HashMap 源碼節(jié)選-JDK8
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

hash方法的返回結(jié)果中是一句三目運算符，鍵 (key) 為null即返回 0,存在則返回后一句的內(nèi)容

(h = key.hashCode()) ^ (h >>> 16)

JDK8中 HashMap——hash 方法中的這段代碼叫做 “擾動函數(shù)”

我們來分析一下：

hashCode是Object類中的一個方法，在子類中一般都會重寫，而根據(jù)我們之前自己給出的程序，暫以Integer類型為例，我們來看一下Integer中hashCode方法的源碼：

/**
 * Returns a hash code for this {@code Integer}.
 *
 * @return  a hash code value for this object, equal to the
 *          primitive {@code int} value represented by this
 *          {@code Integer} object.
 */
@Override
public int hashCode() {
    return Integer.hashCode(value);
}

/**
 * Returns a hash code for a {@code int} value; compatible with
 * {@code Integer.hashCode()}.
 *
 * @param value the value to hash
 * @since 1.8
 *
 * @return a hash code value for a {@code int} value.
 */
public static int hashCode(int value) {
    return value;
}

Integer中hashCode方法的返回值就是這個數(shù)本身

注：整數(shù)的值因為與整數(shù)本身一樣唯一，所以它是一個足夠好的散列

所以，下面的A、B兩個式子就是等價的

//注：key為 hash(Object key)參數(shù)

A：(h = key.hashCode()) ^ (h >>> 16)

B：key ^ (key >>> 16)

分析到這一步，我們的式子只剩下位運算了，先不急著算什么，我們先理清思路

HashSet因為底層使用哈希表（鏈表結(jié)合數(shù)組）實現(xiàn)，存儲時key通過一些運算后得出自己在數(shù)組中所處的位置。

我們在hashCoe方法中返回到了一個等同于本身值的散列值，但是考慮到int類型數(shù)據(jù)的范圍：-2147483648~2147483647 ，著很顯然，這些散列值不能直接使用，因為內(nèi)存是沒有辦法放得下，一個40億長度的數(shù)組的。所以它使用了對數(shù)組長度進行取模運算，得余后再作為其數(shù)組下標，indexFor( ) ——JDK7中，就這樣出現(xiàn)了，在JDK8中 indexFor()就消失了，而全部使用下面的語句代替，原理是一樣的。

//JDK8中
(tab.length - 1) & hash；

//JDK7中
bucketIndex = indexFor(hash, table.length);

static int indexFor(int h, int length) {
    return h & (length - 1);
}

提一句，為什么取模運算時我們用 & 而不用 % 呢，因為位運算直接對內(nèi)存數(shù)據(jù)進行操作，不需要轉(zhuǎn)成十進制，因此處理速度非?？欤@樣就導致位運算 & 效率要比取模運算 % 高很多。

看到這里我們就知道了，存儲時key需要通過hash方法和indexFor( )運算，來確定自己的對應下標

(取模運算，應以JDK8為準，但為了稱呼方便，還是按照JDK7的叫法來說，下面的例子均為此，特此提前聲明)

但是先直接看與運算(&)，好像又出現(xiàn)了一些問題，我們舉個例子：

HashMap中初始長度為16，length - 1 = 15；其二進制表示為 00000000 00000000 00000000 00001111

而與運算計算方式為：遇0則0，我們隨便舉一個key值

        1111 1111 1010 0101 1111 0000 0011 1100
&       0000 0000 0000 0000 0000 0000 0000 1111
----------------------------------------------------
        0000 0000 0000 0000 0000 0000 0000 1100

我們將這32位從中分開，左邊16位稱作高位，右邊16位稱作低位，可以看到經(jīng)過&運算后 結(jié)果就是高位全部歸0，剩下了低位的最后四位。但是問題就來了，我們按照當前初始長度為默認的16，HashCode值為下圖兩個，可以看到，在不經(jīng)過擾動計算時，只進行與(&)運算后 Index值均為 12 這也就導致了哈希沖突

哈希沖突的簡單理解：計劃把一個對象插入到散列表(哈希表)中，但是發(fā)現(xiàn)這個位置已經(jīng)被別的對象所占據(jù)了

例子中，兩個不同的HashCode值卻經(jīng)過運算后，得到了相同的值，也就代表，他們都需要被放在下標為2的位置

一般來說，如果數(shù)據(jù)分布比較廣泛，而且存儲數(shù)據(jù)的數(shù)組長度比較大，那么哈希沖突就會比較少，否則很高。

但是，如果像上例中只取最后幾位的時候，這可不是什么好事，即使我的數(shù)據(jù)分布很散亂，但是哈希沖突仍然會很嚴重。

別忘了，我們的擾動函數(shù)還在前面擱著呢，這個時候它就要發(fā)揮強大的作用了,還是使用上面兩個發(fā)生了哈希沖突的數(shù)據(jù)，這一次我們加入擾動函數(shù)再進行與(&)運算

補充 ：>>> 按位右移補零操作符，左操作數(shù)的值按右操作數(shù)指定的為主右移，移動得到的空位以零填充 
?         ^     位異或運算，相同則0，不同則1

可以看到，本發(fā)生了哈希沖突的兩組數(shù)據(jù)，經(jīng)過擾動函數(shù)處理后，數(shù)值變得不再一樣了，也就避免了沖突

其實在擾動函數(shù)中，將數(shù)據(jù)右位移16位，哈希碼的高位和低位混合了起來，這也正解決了前面所講 高位歸0，計算只依賴低位最后幾位的情況, 這使得高位的一些特征也對低位產(chǎn)生了影響，使得低位的隨機性加強，能更好的避免沖突

到這里，我們一步步研究到了這一些知識

HashSet add() → HashMap put() → HashMap hash() → HashMap (tab.length - 1) & hash；

有了這些知識的鋪墊，我對于剛開始自己舉的例子又產(chǎn)生了一些疑惑,我使用for循環(huán)添加一些整型元素進入集合，難道就沒有任何一個發(fā)生哈希沖突嗎，為什么遍歷結(jié)果是有序輸出的，經(jīng)過簡單計算 2 和18這兩個值就都是2

(這個疑惑是有問題的，后面解釋了錯在了哪里)

//key = 2,(length -1) = 15

h = key.hashCode()      0000 0000 0000 0000 0000 0000 0000 0010    
h >>> 16                0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16)     0000 0000 0000 0000 0000 0000 0000 0010
(tab.length-1)&hash     0000 0000 0000 0000 0000 0000 0000 1111
                        0000 0000 0000 0000 0000 0000 0000 0010    
-------------------------------------------------------------
                        0000 0000 0000 0000 0000 0000 0000 0010

//2的十進制結(jié)果：2

//key = 18,(length -1) = 15

h = key.hashCode()      0000 0000 0000 0000 0000 0000 0001 0010    
h >>> 16                0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16)     0000 0000 0000 0000 0000 0000 0001 0010
(tab.length-1)&hash     0000 0000 0000 0000 0000 0000 0000 1111
                        0000 0000 0000 0000 0000 0000 0000 0010    
-------------------------------------------------------------
                        0000 0000 0000 0000 0000 0000 0000 0010

//18的十進制結(jié)果：2

按照我們上面的知識，按理應該輸出 1 2 18 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 但卻仍有序輸出了

import java.util.*;

public class HashSetDemo {
    public static void main(String[] args) {

        Set hs = new HashSet();

        for (int i = 0; i < 19; i++) {
            hs.add(i);
        }

        //增強for遍歷
        for (Integer s : hs) {
            System.out.print(s + " ");
        }
    }
}

//運行結(jié)果：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

再試一試

import java.util.*;

public class HashSetDemo {
    public static void main(String[] args) {

        Set hs = new HashSet();
        
        hs.add(0)
        hs.add(1);
        hs.add(18);
        hs.add(2);
        hs.add(3);
        hs.add(4);
        ......
        hs.add(17)

        //增強for遍歷
        for (Integer s : hs) {
            System.out.print(s + " ");
        }
    }
}

//運行結(jié)果：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

真讓人頭大，不死心再試一試，由與偷懶，就只添加了幾個，就是這個偷懶，讓我發(fā)現(xiàn)了新大陸！

import java.util.*;

public class HashSetDemo {
    public static void main(String[] args) {

        Set hs = new HashSet();

        hs.add(1);
        hs.add(18);
        hs.add(2);
        hs.add(3);
        hs.add(4);

        //增強for遍歷
        for (Integer s : hs) {
            System.out.print(s + " ");
        }
    }
}

//運行結(jié)果：
1 18 2 3 4

這一段程序按照我們認為應該出現(xiàn)的順序出現(xiàn)了?。?！

突然恍然大悟，我忽略了最重要的一個問題，也就是數(shù)組長度問題

//HashMap 源碼節(jié)選-JDK8

/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

<< ：按位左移運算符，做操作數(shù)按位左移右錯作數(shù)指定的位數(shù)，即左邊最高位丟棄，右邊補齊0，計算的簡便方法就是：把 << 左面的數(shù)據(jù)乘以2的移動次冪 
為什么初始長度為16：1 << 4 即 1 * 2 ^4 =16;

我們還觀察到一個叫做加載因子的東西，他默認值為0.75f，這是什么意思呢，我們來補充一點它的知識：

加載因子就是表示哈希表中元素填滿的程度，當表中元素過多，超過加載因子的值時，哈希表會自動擴容，一般是一倍，這種行為可以稱作rehashing(再哈希)。
加載因子的值設置的越大，添加的元素就會越多，確實空間利用率的到了很大的提升，但是毫無疑問，就面臨著哈希沖突的可能性增大，反之，空間利用率造成了浪費，但哈希沖突也減少了，所以我們希望在空間利用率與哈希沖突之間找到一種我們所能接受的平衡，經(jīng)過一些試驗，定在了0.75f

現(xiàn)在可以解決我們上面的疑惑了

數(shù)組初始的實際長度 = 16 * 0.75 = 12

這代表當我們元素數(shù)量增加到12以上時就會發(fā)生擴容，當我們上例中for循環(huán)添加0-18， 這19個元素時，先保存到前12個到第十三個元素時，超過加載因子，導致數(shù)組發(fā)生了一次擴容，而擴容以后對應與(&)運算的(tab.length-1)就發(fā)生了變化,從16-1 變成了 32-1 即31

我們來算一下

//key = 2,(length -1) = 31

h = key.hashCode()      0000 0000 0000 0000 0000 0000 0001 0010    
h >>> 16                0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16)     0000 0000 0000 0000 0000 0000 0001 0010
(tab.length-1)&hash     0000 0000 0000 0000 0000 0000 0011 1111 
                        0000 0000 0000 0000 0000 0000 0000 0010        
-------------------------------------------------------------
                        0000 0000 0000 0000 0000 0000 0000 0010

//十進制結(jié)果：2

//key = 18,(length -1) = 31

h = key.hashCode()      0000 0000 0000 0000 0000 0000 0001 0010    
h >>> 16                0000 0000 0000 0000 0000 0000 0000 0000
hash = h^(h >>> 16)     0000 0000 0000 0000 0000 0000 0001 0010
(tab.length-1)&hash     0000 0000 0000 0000 0000 0000 0011 1111 
                        0000 0000 0000 0000 0000 0000 0000 0010        
-------------------------------------------------------------
                        0000 0000 0000 0000 0000 0000 0001 0010

//十進制結(jié)果：18

當length - 1 的值發(fā)生改變的時候，18的值也變成了本身。

到這里，才意識到自己之前用2和18計算時 均使用了 length -1 的值為 15是錯誤的，當時并不清楚加載因子及它的擴容機制，這才是導致提出有問題疑惑的根本原因。

JDK7到JDK8，其內(nèi)部發(fā)生了一些變化，導致在不同版本JDK下運行結(jié)果不同，根據(jù)上面的分析，我們從HashSet追溯到HashMap的hash算法、加載因子和默認長度。

由于我們所創(chuàng)建的HashSet是Integer類型的，這也是最巧的一點，Integer類型hashCode()的返回值就是其int值本身，而存儲的時候元素通過一些運算后會得出自己在數(shù)組中所處的位置。由于在這一步，其本身即下標(只考慮這一步)，其實已經(jīng)實現(xiàn)了排序功能，由于int類型范圍太廣，內(nèi)存放不下，所以對其進行取模運算，為了減少哈希沖突，又在取模前進行了，擾動函數(shù)的計算，得到的數(shù)作為元素下標，按照JDK8下的hash算法，以及l(fā)oad factor及擴容機制，這就導致數(shù)據(jù)在經(jīng)過 HashMap.hash()運算后仍然是自己本身的值，且沒有發(fā)生哈希沖突。

補充：對于有序無序的理解

集合所說的序，是指元素存入集合的順序，當元素存儲順序和取出順序一致時就是有序，否則就是無序。

并不是說存儲數(shù)據(jù)的時候無序，沒有規(guī)則，當我們不論使用for循環(huán)隨機數(shù)添加元素的時候，還是for循環(huán)有序添加元素的時候，最后遍歷輸出的結(jié)果均為按照值的大小排序輸出，隨機添加元素，但結(jié)果仍有序輸出，這就對照著上面那句，存儲順序和取出順序是不一致的，所以我們說HashSet是無序的，雖然我們按照123的順序添加元素，結(jié)果雖然仍為123，但這只是一種巧合而已。

所以HashSet只是不保證有序，并不是保證無序

如果內(nèi)容中有什么不足，或者錯誤的地方，歡迎大家給我留言提出意見, 蟹蟹大家 ！^_^

如果能幫到你的話，那就來關(guān)注我吧！（系列文章均會在公眾號第一時間更新）

在這里的我們素不相識，卻都在為了自己的夢而努力 ?
一個堅持推送原創(chuàng)Java技術(shù)的公眾號：理想二旬不止