昨天介紹了 HashMap 將 key 定位到 bucket 的過程。而本文主要解說的是，在一個 bucket 中，要如何找到 key 所對應的節點，進而討論為什麼 hashCode 和 equals 方法要一起覆寫。最後介紹 HashMap 的容量與擴充。

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

四、定位節點的過程

（一）過程

幫讀者做個小複習，HashMap 在 put 或 get 資料時，會根據傳入的 key 參數，定位出資料應在的 bucket，也就是 table 陣列的某個位置。過程中會幫 key 算出一個 HashMap 的專用雜湊值，再換算成陣列 index。

然而發生雜湊碰撞在所難免，假使 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 陣列長度）。另外還有一個參數叫 loadFactor（負載因子）。我們稱 initialCapacity × loadFactor 為「閥值」（threshold）。

（一）初始容量的決定

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

為何刻意取 2 的冪數呢？。要知道在定位 bucket 時，key 的專用雜湊值會與 bucket 數量 - 1 進行 AND 位元運算，以求得 bucket 的位置。又因 2 的冪數 - 1 的二進制都是 1（如 16 - 1 = 15 = 1111），故 0000 ~ 1111 的每個數字都有機會算出來，有利於減少雜湊碰撞。筆者就不再贅述昨天提過的細節。

（二）擴容

當存放完新資料後，若發現已超過閥值，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。藉此重新計算出每一筆資料節點要存放的新位置，達到「打散」的效果。仔細想想，其實 HashMap 的 bucket 並非每一個都會被用到。它的設計者犧牲了空間，來換取效率。

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

Ref：
HashMap 什麼時候進行擴容呢
面渣逆襲：HashMap追魂二十三問

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