【Java】HashMap 的底層工作原理

日期：

https://unsplash.com/photos/a-row-of-books-sitting-on-top-of-a-shelf-6EH_ILd3S50

在「認識 Java HashMap 前要具備的雜湊概念」文章中，筆者對「雜湊」做了介紹。而本文將以此為基礎，進一步認識 Java 8 的 HashMap 是怎麼儲存和查詢資料的。HashMap 原理牽涉到許多知識點，讀者可能要多看幾次、多找參考資料，才會更明白。

一、HashMap 的內部結構

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

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

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

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

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

以下是樹節點的原始碼。

讓我們再複習一下雜湊相關結構，並與 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 有資料，那也只要在當中一筆一筆檢查就好，不必將整個 HashMap 中的資料都拜訪一次。

三、定位 bucket 的過程

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

（一）計算專用的 hash code

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

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

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

這邊要知道一下，hashCode 的回傳是型態 int，用二進制可表示成 32 個位元。過程中透過右移 16 個位元，便得出左邊高位的 16 位元。

例如原始 hash code 的二進制為：「0000 1110 1010 0001 1010 1001 0010 1011」， 則右移 16 位元後得到：「0000 1110 1010 0100」。

接著原始 hash code 和右移後的結果做 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（2⁴）、32（2⁵）、64（2⁶）。
  • 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 的程式碼片段。

四、定位節點的過程

（一）過程

HashMap 在 put 或 get 資料時，會根據傳入的 key 參數，定位出資料應在的 bucket，也就是 table 陣列的某個位置。

然而發生雜湊碰撞在所難免，假使 bucket 中已經有節點資料了，那就要在這些節點中逐一確認。這會透過 equals 方法，好好地比對 key 的內容是否相等。

若正在 put 資料，當找到 key 相等的節點，就進行覆蓋；否則就插入一個新節點。若正在 get 資料，當找到 key 相等的節點，就回傳；否則回傳 null。

（二）覆寫 hashCode 和 equals 的原因

對於 hashCode 和 equals 方法要一起覆寫的議題，便是跟上述的操作有關。

如果沒有覆寫 hashCode，並預期兩個內容相同的物件會被「HashSet」視為相同，那就錯了。由於 hashCode 預設是根據記憶體位址算出，第二個物件可能就直接被放入不同的 bucket 了。即便有覆寫 equals，也沒有執行的機會。

如果只覆寫了 hashCode，卻忘記覆寫 equals，那麼即使內容相同的物件被算出在同一個 bucket，但由於 equals 預設是判斷記憶體位址相等，它們在最終依然被視為不同。


五、HashMap 的容量

（一）初始容量的決定

在宣告 HashMap 時，可以透過建構子傳入叫做 initialCapacity（初始容量）的參數，用來指定 bucket 的初始數量（即 table 陣列長度）。

HashMap 有個特別的設計，即使建構子的 initialCapacity 參數不是傳入 2 的冪數，仍然會被換算為大於它的冪數。例如傳入 15，就換算成 16（2⁴）；傳入 17，就換算成 32（2⁵）。

為何刻意取 2 的冪數呢？。在第三節第二段有提到，table 陣列長度會用於定位 bucket 位置。若為 2 的冪數，能減少 AND 運算後的雜湊碰撞。筆者就不再贅述。

（二）擴容

HashMap 建構子還有另一個參數叫 loadFactor（負載因子）。我們稱 initialCapacity × loadFactor 為「閥值」（threshold）。

當存放完新資料後，若發現已超過閥值，HashMap 會進行擴充容量的動作，簡稱擴容。要做的事包含：

  1. 將 bucket 數量，也就是 table 陣列的長度，增加為原來的 2 倍。
  2. 將現有的資料節點，重新分布到新的 table 陣列中。

也就是說，initialCapacity 預設為 16，且 loadFactor 預設為 0.75，則當資料數量超過 12 時，便會啟動擴容機制。使得 bucket 數量增至 32，而新的閥值為 24。

超過閥值這件事，對 HashMap 而言意味著雜湊碰撞變嚴重了，這可以從兩個角度來思考。

  • 假設資料分布趨近於「12 個 bucket 各有 1 筆資料」，雖然最均勻，但新增第 13 筆時發生碰撞的機會還蠻高的（75%）。
  • 假設資料分布趨近於「1 個 bucket 有 12 筆資料」，或者不要那麼極端，「4 個 bucket 各有 3 筆資料」也好，感覺也不是很理想。

HashMap 擴容之後，「table 陣列長度 - 1」的二進制，會多一個 1。藉此重新計算出每一筆資料節點要存放的新 bucket，達到「打散」的效果。仔細想想，其實 HashMap 的 bucket 並非每一個都會被用到。它的設計者犧牲了空間，來換取效率。

擴容會對許多資料做重新安置的操作，將消耗較大的效能。所以當我們能預測存進 HashMap 的資料數量有多少時，建議可在宣告時給予適當的 initialCapacity，避免執行太多次的擴容。

上一篇：【Java】認識 HashMap 前要具備的雜湊概念

參考資料：

留言

張貼留言