# 工作日記 #003：為何初始 Map 時要先設定容量？
之前上班看到同事都會先給定Map一個初始的容量，一開始我不太懂差別，但最近有稍微理解了用意，主要是因為要避免動態擴容所造成的性能開銷。
## 動態擴容
如果沒有在創建 Map 物件時，預先指定容量的話，那底層預設會是一個長度為 16 的陣列（Map底層是陣列＋鏈表實作的），而這個Map會有一個負載因子（Load Factor）的機制。也就是說，假設我要存入的元素超過了原始陣列長度的 75%，就會觸發擴容，在這個例子裡就是 16 * 0.75 = 12 個元素，當我存了 12 個元素，Map 底層就會擴容一倍變成長度 32 的陣列。
## CPU 性能開銷
動態擴容不只是會消耗記憶體的使用空間，擴容的過程中也會需要變更記憶體的存儲位置，因為陣列存在記憶體的方式是一塊連續的記憶體地址，如果動態擴容的話，假設旁邊有其他的應用在使用，是不能拆分儲存的，一定要整個更換地址，這個過程就會造成CPU的性能開銷。

另外，除了遷址的開銷外，每次觸發擴容也需要做 Rehash 的操作，因為當 size 改變時（比如從16變成32）即使是同一個 key，算出來的 index 也會不同，因此需要重新分配元素到不同的 Hash 槽並取得新的索引值，而 Rehash 的計算方式是 =>

HashCode % size = index

所以擴容時的開銷主要有兩部分：

1. 記憶體遷移的開銷（複製數據到新地址）
2. Rehash 的開銷（重新計算每個元素的索引位置）
## 續：當 HashMap 碰上 Hash Collusion
補充一下，每個 HashMap 的 Key 都會對應一個 HashCode，而剛有提到 HashCode % size = Hash 槽的索引，但假設兩個不同 Key 計算出的索引是相同的，就會引發所謂的 Hash Collusion（哈希衝突），這時候 HashMap 的解決方法是在每個 Hash 槽實作單向鏈表，同索引的 Key-value 會形成一個鏈，找到這個鏈之後再迭代找出符合需求的 Key-value（又稱 Entry）。

而在 Java 8 以後，當槽位的鏈表長度超過 8（且陣列長度來到 64）時，HashMap 會用紅黑數取代單向鏈表，以提升碰撞時的查詢效能：
* 鏈表查詢是O(n)，n是鏈表長度
* 紅黑樹查詢是O(log n)