在 Java 中，HashMap 是個挺常用的 Map 類別的實作。而且嚴格來說，雖然 Map 在 JDK 中就有 HashMap 和 TreeMap 兩大類（其實還有其他像是 Property 啦，但我個人覺得不太會把他們放在一起討論 XD），不過其實大多數狀況大家需要用到 Map 時，都不是太在乎 Map 是否有多餘的特性，只在乎 Map 這個介面原本提供的特性，也就是「任意一個 key 在 Map 中都是唯一的」，所以相較於 TreeMap 來說，HashMap 是比較常被使用的類別。這篇文章就是要來討論一下 Java 11 的 HashMap。
會想要寫這篇文章，其實是最近開始在準備面試，然後翻到以前寫的文章提到 HashMap 的時間複雜度的問題，才突然想起 HashMap 有個奇妙的特性！同時當時查資料時的對象是 Java 7/8，但現在的主流已經是 Java 11 了，也有些好奇 Java 11 的 HashMap 是否有其他的變化，因此就花了些時間再來閱讀一下 Java 11 的 HashMap 實作了（雖然 Java 17 LTS 也快出了....）。
HashMap 的概要
一般我們談到 HashMap 的效能時，通常會預期 HashMap 的 put 和 get 的時間複雜度應該會是 O(1) 常數時間，因為想像上 HashMap 會透過雜湊演算法快速地鎖定到一個放值的位置，所以 put 和 get 的效能跟已經存在裡面的資料量應該是沒有關聯的。但實際上在 Java 的實作中，這個假設是錯誤的。
Java 11 的 HashMap 跟 Java 8 實作差不多，裡面存在有「bucket」的概念。bucket 代表的是一個小空間，可以用來存放多個物件，用在 HashMap 裡是為了解決 collision 的問題。更確切地說，HashMap 裡並不會產生跟 HashMap 長度相等的表格，而是產生 2^n <= capacity 的 bucket。舉例來說，如果要求的是長度為 512 的 HashMap，實際上會產生的是包含有 9 個 bucket 的 HashMap。這裡面的算法還蠻神妙的，是嘗試用數值去推算二進位的狀況，挺有意思的，不過由於這跟 HashMap 關聯性稍低一點，所以這裡就不細談，有興趣的話可以參考 [2] 看看。既然 bucket 數與實際的容量並不相同，那麼意思就是放資料到 HashMap 時，必然會有 collision 的狀況，因此每個 bucket 裡可能存放超過 1 個物件，在 HashMap 的實作中會依據狀況決定在 bucket 裡會以什麼資料結構來放這些物件。
基於 bucket 的概念，當我們對 HashMap 進行 put 或 get 時，它會花費 O(1) 的複雜度透過雜湊演算法（基本上就是 hash code）決定 bucket 的位置，然後接著在 bucket 當中以 O(n) 或者 O(logn) 的複雜度來找出真正符合的 key 值與其 value。因此就結果來說，實際上 HashMap 的 put 或 get 操作，在資料量不大的時候，worst case 的時間複雜度其實是 O(n)；而在資料量大的時候，worst case 的時間複雜度會是 O(logn)。
接著就來看看 HashMap 的一些細節實作了～。
HashMap 的初始化
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);
}HashMap 初始化的時候，只會決定兩個參數 loadFactor 和 threshold 各自是多少，兩個參數都是用在決定 bucket 有幾個。threshold 是用來決定「下一次 resize 時的 bucket 數量」、而 loadFactor 則是用來決定「下一次 resize 時要讓 bucket 數量增長到什麼程度」。
在這段初始化的程序中，還有一段 tableSizeFor() 的呼叫，這個函式的目的是為了決定 resize 後的結果，內容如下：
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}可以看到，這段其實就是前面講到的，用來決定 bucket 數量的演算法。它的輸出就是距離指定長度最近的 2 的冪。舉例來說，如果指定的是長度 510，那這個函式會回覆 9，因為 2^9 = 512 >= 510。
Treeify
在 HashMap 的實作當中，可以看到有很長一段註解在說明 Treeify，意義就如同字面上所示，意思是 HashMap 裡面有一段關於樹狀結構的行為。相關的參數如下：
/** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */ static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */ static final int MIN_TREEIFY_CAPACITY = 64;
這邊連同參數的註解也貼進來，從註解很容易就可以理解它們的意義了。如前面提到的，在 HashMap 當中資料是存放在 bucket 裡，其中每個 bucket 會有一個或多個物件（在程式碼中被稱為 bin/node），因此需要一種能夠存放多個物件的資料結構作為實際存放物件的位置。如果 HashMap 需要存放的資料夠多的時候，HashMap 會開始將 bucket 內的每個物件進行 treeify，也就是把資料結構轉換成樹狀結構，以此來提昇存取的效能。而依照這裡的預設參數可以看出，條件是「若 bucket 內有超過 8 個物件、且整個 HashMap 至少有 64 個物件」時，HashMap 會開始把 bucket 的資料結構轉換為樹狀結構；同時，若資料減少到少於 6 個物件時，HashMap 也會反過來將樹狀結構還原為 List。這也就是為何前面提到，在不同狀況時 HashMap 存取資料的複雜度會不同的原因，因為 bucket 底下的資料結構可能會依據資料量的不同而有差別。
暫時先寫到這，其實主要影響的因素已經寫在上面了，剩下的看之後有動力寫的時候再補了 XDrz。
沒有留言:
張貼留言