在昨天的文章中，筆者對「雜湊」（hash）做了介紹。而接下來兩天的文章要以此為基礎，進一步認識 Java 8 的 HashMap 是怎麼儲存和查詢資料的。HashMap 原理牽涉到許多知識點，讀者可能要多看幾次、多讀參考資料，才會更明白。

此篇亦轉載到個人部落格。

一、HashMap 的內部結構

HashMap 結構的「門面」，是一個名為 table 的陣列。該陣列的預設長度為 16，元素型態為 Node。

public class HashMap<K,V> implements ... {
    Node<K,V>[] table;
    // ...
}

而節點 Node 中的內容，包含資料的 key、value、key 的雜湊值，以及指向下一個節點的指標。

class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // ...
}

為什麼要指向下一個節點呢？這是因為在 put 資料時，可能會遇到 hash 碰撞。例如某筆資料被算出要放在 table 陣列的索引 0 中，但該位置已經有資料了（碰撞）。

此時 HashMap 的處理方式是將新資料往現有節點的後面存放，形成「鏈結串列」（Linked List）。這便是 next 指標的用途。同理，get 資料時也是透過 next 去拜訪下一個節點。

然而，在鏈結串列中尋找資料的時間複雜度，最差是 O(n)。因此當 table 陣列的某個索引超過 8 筆資料時，HashMap 會將其轉換為「紅黑樹」（一種平衡二元樹），藉此降低至 O(log n)。

以下是樹節點的原始碼。

// PS. 父父類別有實作 Map.Entry<K,V>
class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;
    boolean red;
    // ...
}

讓我們再複習上一篇介紹的雜湊相關結構，並與 HashMap 做對照。table 陣列是 Hash Table；每個陣列元素，或者說鏈結串列和紅黑樹，都是一個 Bucket；Node 和 TreeNode 節點是 Slot。

補充一點，「HashSet」實際上是在內部管理一個 HashMap，以它的 key 當作 HashSet 存放的資料。

二、hashCode 與 equals 方法

在 Java，所有類別都是 Object 的子類別，而它的 int hashCode() 與 boolean equals(Object o) 方法可被覆寫。這裡繼續以昨天的發票情境來介紹。

• hashCode：用來計算雜湊值，直接或間接決定資料應放在哪個 bucket。例如發票經由雜湊函數運算後得到 1（假設取自發票號碼尾數），那就和其他 1 結尾的發票收在同一個區塊。
• equals：用來判斷兩個物件的內容值是否相同。例如已知載具 App 告知號碼為 87654321 的發票中獎了，那我就會在 1 號堆中一張一張地看號碼，才能找出這張發票。

如果不覆寫的話，hashCode 預設是根據記憶體位址算出；而 equals 預設是判斷記憶體位址相等。

覆寫後的 equals 方法因為要詳細地比對物件的內容值，所以工作量比較大。在雜湊結構中，hashCode 起到了「預先判斷」的效果。

若雜湊值所對應的 bucket 沒有任何一筆資料，那就能提前知道資料不存在該結構中。若 bucket 有資料，那也只要在當中一筆一筆檢查就好，不必將整個結構的資料都拜訪一次。

三、定位 bucket 的過程

不論是取得還是存放資料，HashMap 都要先知道資料的位置。這會由 put 和 get 方法接收的 key 參數來決定。

（一）計算專用的 hash code

若未覆寫 hashCode 方法，則預設會根據記憶體位置計算，如 245672235。但我們不會直接將這個數字直接當作 table 陣列的 index 指向某一個 bucket。

理由之一是陣列不會宣告那麼長（預設也才 16 個）。之二是如果 hashCode 方法沒有寫得很好（假設只可能回傳 0 ~ 9），會導致資料在 bucket 之間分布不均。

因此，HashMap 會呼叫以下的 hash 方法，進一步算出自己專用的 hash code（之後再換算成陣列 index）。

// 以下改寫自原始碼，較好閱讀
int hash(Object key) {
    if (key == null) return 0;
    
    // 步驟一：計算 key 的原始 hash code
    int h = key.hashCode();
    
    // 步驟二：取得高位的 16 位元 
    int higherBits = h >>> 16;
    
    // 步驟三：兩者做 XOR 位元運算
    return h ^ higherBits;
}

這邊要知道一下，hashCode 的回傳是型態 int，用二進制可表示成 32 個位元。過程中透過右移 16 個位元，便得出左邊高位的 16 位元。
例如原始 hash code 的二進制為：0000 1110 1010 0001 1010 1001 0010 1011，
則右移 16 位元後得到：0000 1110 1010 0100。

接著原始和右移後的結果做 XOR，就得到這個 key 的新 hash。（也就是左邊高位 16 位元和右邊低位 16 位元做 XOR）

0000 1110 1010 0100 1010 1001 0010 1011
                    0000 1110 1010 0001
---------------------------------------
0000 1110 1010 0100 1010 0111 1000 1010

為何要將左邊高 16 位元和右邊低 16 位元做運算呢？我想是因為這個演算法的設計者，希望 hash code 的每一個位元盡可能都能參與陣列 index（即 bucket）的決定過程。

至於使用 XOR 的原因，是為了減少雜湊碰撞，畢竟算出 0 或 1 的機會是相等的。若使用 AND，只有兩個 1 才會算出 1；使用 OR，只有兩個 0 才會算出 0。

（二）決定 bucket 的方式

經由上面 hash 方法算出新的 hash code 後，這個值便會用來換算成適用於 table 陣列的索引。假設陣列長度為 16，則索引範圍必須落在 0 ~ 15。我們直覺可能會想說用 hash % table.length 取餘數的做法就解決了。

然而 HashMap 選擇使用 AND 位元運算，對電腦底層來說反而效率更好。在繼續解釋之前，請讀者先知道三件事：

• HashMap 會確保 table 陣列長度均為 2 的冪數。如 16、32、64。
• 2 的冪數減 1 的二進制都是 1。如 16 - 1 = 15（十進制）= 1111（二進制）。
• 不管位元的值為何，跟 1 做 AND 運算的結果均等於自己。

有了這些概念，我們便能理解：任何數跟 1111（二進制）做 AND 運算，所得結果只剩下最右邊 4 個位元（左邊高位都變成 0 了），且當然都落在二進制的 0000 ~ 1111，也就是十進制的 0 ~ 15 之間。若 table 陣列長度為 64，則「任何數 AND 111111（二進制）」的結果，會落在 0 ~ 63（十進制）之間。

HashMap 就是用這個思路，既能將運算結果限制在「0 ~ 2 的冪數 - 1」的範圍，同時效率又比 % 取餘數來得高。以下是 HashMap 計算 key 所對應的 bucket 的程式碼片段。

// 以下改寫自原始碼，較好閱讀
Node<K,V> getNode(Object key) {
    Node<K,V>[] tab = this.table;
    if (tab != null || tab.length <= 0) return null;
    
    // 計算 key 的新 hash
    int hash = hash(key);
    
    // 計算餘數，得出 bucket 的位置
    int bucketIndex = (tab.length - 1) & hash;
    
    // 取得 bucket 中第一個節點
    Node<K,V> first = tab[bucketIndex];
    
    if (first == null) return null;
    
    // ...
}

Ref：
HashCode Calculation
Java HashMap工作原理及實現

本文講解了 HashMap 是如何將 put 與 get 方法所接收的 key 參數，對應到 bucket。明天會介紹在一個 bucket 中，要如何找到 key 所對應的資料節點位置，進而寫入或讀取資料。

今日文章到此結束！
最後推廣一下自己的部落格，我是「新手工程師的程式教室」的作者，請多指教