Java資料結構之HashMap和HashSet

1、認識 HashMap 和 HashSet

在上期中，學習到 TreeMap 和 TreeSet，因為他們實現了 SortedMap 和 SortedSet 介面(本質是 實現了 NavigableMap 和 NavigableSet)，表示你建立的 TreeMap 或 TreeSet，必須是可排序的，也就是裡面的元素是可比較的。

HashSet 的底層也是 HashMap，跟上期 TreeSet 大同小異，感興趣可以去看看原始碼。

本期的 HashMap 和 HashSet 並沒有繼承上述所說的倆個介面，也即表示 HashMap 和 HashSet 中的 key 可以不重寫 compareTo 方法，由此也能得出，HashMap 與 HashSet 不關於 key 有序！

因為 Set 的底層就是 Map，那麼這裡我們就來驗證下 TreeSet 關於 key 有序，而 HashSet 不關於 key 有序。

public class Test {
    public static void main(String[] args) {
        Set<String> treeSet = new TreeSet<>();
        Set<String> hashSet = new HashSet<>();;
        treeSet.add("0012");
        treeSet.add("0083");
        treeSet.add("0032");
        treeSet.add("0057");
        System.out.print("TreeSet: ");
        for (String s : treeSet) {
            System.out.print(s + " ");
        }
        hashSet.add("0012");
        hashSet.add("0083");
        hashSet.add("0032");
        hashSet.add("0057");
        System.out.print("nHashSet: ");
        for (String s : hashSet) {
            System.out.print(s + " ");
        }
    }
}

列印結果

為什麼 HashMap 和 HashSet 不關於 key 有序呢？隨著往文章後續學習，你就會明白。

2、雜湊表

2.1 什麼是雜湊表

之前的學習中，如果我們要查詢一個元素，肯定是要經過比較的，那有沒有一種辦法，可以不用經過比較，直接就能拿到呢？

如果我們能構造一種儲存結構，通過一種函數 (hashFunc) 使元素的儲存位置與函數得出的關鍵碼之間能夠建立一一對映的關係，那麼在查詢某個元素的時候，就能通過這個函數來很快的找到該元素所在的位置。

這種函數就叫做雜湊(雜湊)函數，上述所說構造出來的結構，叫做雜湊表或者稱為雜湊表。

插入元素的時候：根據元素的關鍵碼，Person中關鍵碼可能是 age，這個具體情況具體分析，上述例子只是在插入整型的時候，通過關鍵碼通過雜湊函數得到的 index 就是要插入的位置。

搜尋元素的時候：對元素的關鍵碼，通過雜湊函數得出的 index 位置，與該位置的關鍵碼比較，若倆個關鍵碼相同，則搜尋成功。

採取上面的方法，確實能避免多次關鍵碼的比較，搜尋的效率也提高的，但是問題來了，拿上述圖的情況來舉例子的話，我接著還要插入一個元素 15，該怎麼辦呢？

2.2 雜湊衝突

2.2.1 概念

接著上面的例子來說，如果要插入 15，使用雜湊函數出來的 index = 5，但是此時的 5，下標的位置已經有元素存在了，這種情況我們就稱為雜湊衝突！

簡單來說，不同的關鍵字通過相同的雜湊函數計算出相同的雜湊地址（前面我們稱為 index），這種現象就被稱為雜湊衝突或雜湊碰撞！ 

2.2.2 設計合理雜湊函數 - 避免衝突

如果雜湊函數設計的不夠合理，是可能會引起雜湊衝突的。

雜湊函數的定義域，必須包括所需儲存的全部關鍵碼，雜湊函數計算出來的地址，應能均勻的分佈在整個空間中，雜湊函數不能設計太過於複雜。(工作中一般用不著我們親自設計)

常見的雜湊函數：

直接客製化法：取關鍵字的某個線性函數作為雜湊地址：hash = A * key + B， 這樣比較簡單，但是需要事先知道關鍵字的分佈情況，適合於查詢比較小且連續的情況。

除留餘數法：設雜湊表中允許的地址數為 m，取一個不大於 m 的數，但接近或等於 m 的質數 p 作為除數，即雜湊函數：hash = key % p，(p <= m)。

還有其他的方法感興趣可以查閱下相關資料，這兩個只是比較常見的方法了，當然，就算雜湊函數設計的再優秀，只是產生雜湊的衝突概率沒那麼高，但是仍然避免不了雜湊衝突的問題，於是又有了一個降低衝突概率的辦法，調節負載因子。

2.2.3 調節負載因子 - 避免衝突

負載因子 α = 雜湊表中元素個數 / 雜湊表的長度

雜湊表的長度沒有擴容是定長的，即 α 與 元素的個數是成正比的，當 α 越大，即程式碼雜湊表中的元素個數越多，元素越多，發生雜湊衝突的概率就增加了，因此 α 越小，雜湊衝突的概率也就越小。所以我們應該嚴格控制負載因子的大小，在 Java 中，限制了負載因子最大為 0.75，當超過了這個值，就要進行擴容雜湊表，重新雜湊(重新將各個元素放在新的位置上)。

所以負載因子越大，衝突率越高，我們就需要降低負載因子來變相的降低衝突率，雜湊表中元素個數不能改變，所以只能給雜湊表擴容了。

2.2.4 Java中解決雜湊衝突 - 開雜湊/雜湊桶

上面講述的都是避免衝突的方法，其實還往往不夠，不管怎麼避免，還是會有衝突的可能性，那麼通常我們解決雜湊衝突有兩種辦法，分別是 閉雜湊 和 開雜湊 那麼今天我們主要介紹 Java 中的開雜湊是如何解決的，感興趣可以下來自己瞭解下閉雜湊。

開雜湊又叫鏈地址法，或開鏈法，其實簡單來說就是一個陣列加連結串列的結構。如圖：

如上圖我們可得出，通過雜湊函數得出的地址相同的關鍵碼放在一起，這樣的每個子集合稱為桶，接著桶中的元素用連結串列的結構組織起來，，每個連結串列的頭節點存放在雜湊表中。

3、HashMap 的部分原始碼解讀

3.1 HashMap 的構造方法

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
 
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}
 
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
 
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

這幾個構造方法相信都不難理解，第一個無參構造方法，預設負載因子是 0.75，第二個構造方法是你可以傳一個 Map 進去，構造出一個新的 Map，負載因子仍然是預設的 0.75， 第三個構造方法就是指定開闢的容量了(並不是你想象那樣簡單哦，面試題講解)，這個很簡單，第四個構造方法指定容量並且自定義負載因子。

在 HashMap 中，範例化物件的時候並不會預設開闢空間(指定空間除外)。

3.2 HashMap 是如何插入元素的？

前面對 HashMap 的講解，已經大概瞭解了一點，但是 HashMap 底層的雜湊函數是如何設定的呢？而且 Map 中不能有重複值的情況，是利用什麼來判斷這兩個值是相同的值呢？

這裡我們通過檢視 put 方法的原始碼，來帶大家一層層揭開這個面紗：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

進入到 put 方法，隨之呼叫了 putVal 方法，而第一個引數就是我們雜湊函數的實現了，我們轉到hash() 方法中：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

通過雜湊函數，能看出，首先呼叫 key 的hashCode 方法，接著無符號右移 16 位，即將 key 的高16位元 與 低 16位元 互斥或得到的 hash 值，通過這個也就在說明，我們如果是自定義型別的話，比如 Person，那麼一定要重寫 hashCode 方法，不然則是呼叫 Object 裡的 hashCode 方法了。

接著我們再往下看，putVal 方法裡面的邏輯，這裡程式碼比較長，我們分段演示：

這裡就是判斷雜湊表是否為有元素，如果表為 null 或者 雜湊表的長度為 0，就會初始化陣列(Node型別的陣列)，即呼叫 resize() 方法。初始雜湊表的長度是 16，臨界閾值為 16 * 0.75 = 12，也就是陣列元素達到 12個即會擴容。往後走程式碼：

這裡作用是通過 hash 值得到索引 i，也就是陣列的下標，判斷這個位置是否有元素了，如果沒有則直接 new 一個節點放到該處。反之走 else 就表示該陣列下標已經有元素了。

如果得到的 i 索引處有元素，則需要判斷當前下標元素的 hash 值是否與我們要插入的元素 hash 值相同，如果相同，接著判斷 下標元素的 key 與我們要插入元素的 key一樣，或者通過 equals 方法比較是一樣了，則表示是同一個元素，則不用插入了，e 儲存這個已經存在的元素。到這裡也能發現，這其實就是 Map 底層不能有重複 key 的原因了。

那如果他們不相同的情況下，就會判斷該下標 i 的位置值是不是紅黑樹的節點(到了一定條件雜湊桶中的元素會採用紅黑樹來組織資料)，如果是，則採用紅黑樹的方式進行插入元素，這裡我們就不往裡面看了。

最後都不滿足的情況，也就是元素不相同，並且不是紅黑樹結構，則走後面的 else，首先這個 else 裡面是個死迴圈，要想退出，必須滿足兩個條件，① 找到了可以插入的地方，② 在雜湊桶中發現了相同的元素。

比較該陣列索引 i 下標的下一個節點，如果為 null，則直接插入該節點，如果連結串列長度大於8，則可能需要樹化，也就是轉換成紅黑樹，如果找到了相同的 key，則不用插入直接跳出迴圈。

上面的 else 走完後，如果存在新增相同的元素的時候，e 則不為 null，只需要將待新增元素的 value 值賦值給原本存在元素的 value 值即可，也就是更新一下元素的 value 值。afterNodeAccess 方法不用管，是使用 LinkedHashMap 實現的一個操作，這裡並沒有使用。

最後部分：

這裡有效元素個數自增，如果超過了陣列長度，則重新判斷是否擴容（兩倍擴容）。 afterNodeInsertion 也不用管，LinkedHashMap中的，這裡也沒有實際用途。

總結：HashMap 的 put 方法，是根據 key 的 hashCode 來計算 hash 值的，即我們要在自定義型別中重寫 HashCode 方法，再者，是根據 equals 來判斷 key 是否相同，也表示著我們同時需要去重寫 equals 方法。

3.3 雜湊表下的連結串列，何時會樹化？

在上述講解 put 方法的時候，發現插入元素的時候，陣列索引位置的連結串列不止一個元素的時候會判斷是否要轉換成紅黑樹，那麼具體要達到什麼條件才能轉換成紅黑樹呢？我們直接看上述的 treeifyBin 方法即可。

樹化的前提是，連結串列的長度大於等於 8，就會樹化，因為是從 binCount 是從 0 開始的，所以 TREEIFY_THRESHOLD - 1。那麼連結串列的長度大於等於 8，一定會從連結串列變成紅黑樹嗎？我們往後看：

第一個 if 當雜湊表為空，或者表(陣列)的長度小於64，只進行擴容即可，不會轉換成樹，當雜湊表的長度大於 64，才有可能轉換成紅黑樹。

所以我們最終得出，HashMap 中雜湊表下的連結串列，當連結串列長度大於等於 8，並且雜湊表的長度大於等於 64 則會將此連結串列轉換成紅黑樹。 

4、相關面試題

4.1 連結串列轉換成紅黑樹如何比較？

前面我們學過 TreeMap TreeSet 底層就是紅黑樹，裡面的元素必須是可比較的，那雜湊表下的連結串列轉換成紅黑樹之後，沒有重寫 compareTo 怎麼辦呢？這裡會按照 key 的雜湊值來進行比較，所以就算轉換成紅黑樹後，也不會關於 key 有序，再者可能只是雜湊表其中一個索引位置下的結構是紅黑樹，其他的仍然可能是連結串列。

4.2 hashCode 和 equals 的區別

hashCode 是虛擬出物件的地址，底層是 native 封裝的，即 C/C++實現的，而 equals 則是比較兩個物件是否相同。

當我們重寫 hashCode 的時候，是呼叫 Objects 裡面的 hash 方法：

@Override
public int hashCode() {
    return Objects.hash(name, age);
}

舉個例子，person1 和 person2 兩個物件的 hashCode 完全不一樣，但通過 hash 函數得到的 hash 值是相同的！而 hashCode 也是通過 hash 出來的，即物件的 hashCode 可以稱為 hash 值，所以得出，兩個物件的 hashCode 相同，但是這兩個物件不一定相同。

對於 persong1.equals(person2) 的值為 true 的情況，則代表這兩個物件裡面的值都是一樣的，所以 equals 為 ture，兩個一模一樣的物件，最終的 hash 值肯定也是一樣的，並且 HashMap 也是呼叫 key 中的 equals() 方式來進行判斷是否有重複的 key 值。

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    Person person = (Person) o;
    return age == person.age &&
            Objects.equals(name, person.name);
}

總結：

兩個物件的 HashCode 相同，不代表這兩個物件完全相同。

兩個物件的 equals 的結果為 true，則代表這兩個物件完全相同。

4.3 以下程式碼分配的記憶體是多少？

public static void main(String[] args) {
    Map<Integer, Integer> map = new HashMap<>(25);
}

如果你天真的回答是 25 個陣列元素大小，那就錯了，我們點進去構造方法，發現是呼叫另一個構造方法，在接著點進去，看到最後一行程式碼即 tableSizeFor 方法：

這裡就沒必要慢慢算了，實際就是給你找到一個離 cap 最近的 2 的 n 次方數，取值範圍得大於等於 cap，例如上述 25 則實際開闢的就是 1  2  4  8  16  32  64....，那麼上述程式碼實際開闢的大小就是 32 個陣列空間大小。

5、效能分析

雖然雜湊表一直在和衝突做鬥爭，但在實際使用過程中，我們認為雜湊表的衝突率是不高的，衝突個數是可控的， 也就是每個桶中的連結串列的長度是一個常數，所以，通常意義下，我們認為雜湊表的插入/刪除/查詢時間複雜度是 O(1) 。 

以上就是Java資料結構之HashMap和HashSet的詳細內容，更多關於HashMap和HashSet的資料請關注it145.com其它相關文章！