你給HashMap初始化了容量，卻讓性能變加更糟
本文轉載自微信公眾號「程序新視界」，作者二師兄。轉載本文請聯系程序新視界公眾號。
前言
項目中，看到大家已經意識到初始化HashMap時給Map指定初始容量大小，甚是欣慰。但仔細一看，發現事情好像又有一些不對頭。雖然指定了大小，卻讓性能變得更加糟糕了。
可能你也是如此，看了《阿里巴巴Java開發手冊》感覺學到了很多，于是在實踐中開始嘗試給Map指定初始大小，并感覺自己寫的代碼高大上了一些。
的確，當你意識到指定初始化值時，已經比普通人更進了一步，但是如果這個值指定的不好，程序的性能反而不如默認值。
這篇文章就來從頭到尾分析一下，讀者多注意分析的方法和底層的原理實現。
阿里開發規范
我們先來看看阿里巴巴Java開發規范中是如何描述Map初始值大小這一規范的吧。
阿里巴巴《Java開發手冊》第1章編程規范，第6節集合處理的第17條規定如下：
【推薦】集合初始化時，指定集合初始值大小。說明：HashMap 使用HashMap(int initialCapacity)初始化，如果暫時無法確定集合大小，那么指定默認值(16)即可。
正例：initialCapacity = (需要存儲的元素個數 / 負載因子) + 1。注意負載因子(即loader factor)默認為0.75，如果暫時無法確定初始值大小，請設置為16(即默認值)。
反例：HashMap需要放置1024個元素，由于沒有設置容量初始大小，隨著元素不斷增加，容量7次被迫擴大，resize需要重建hash表。當放置的集合元素個數達千萬級別時，不斷擴容會嚴重影響性能。
通過上面的規約我們大概了解到幾個信息：
- 第一，HashMap的默認容量是16;
- 第二，容量擴容與負載因子和存儲元素個數有關;
- 第三，設置初始值是為了減少擴容導致重建hash的性能影響。
可能你看完上述規約之后，就開始在代碼中進行使用指定集合初始值的方式了，這很好。但稍有不慎，這中間卻會出現很多的問題，下面我們就來看看實例。
你指定的初始值對嗎?
直接上一段示例代碼，并思考這段代碼是否有問題：
- Map<String, String> map = new HashMap<>(4);
- map.put("username","Tom");
- map.put("address","Bei Jing");
- map.put("age","28");
- map.put("phone","15800000000");
- System.out.println(map);
類似的代碼是不是很熟悉，寫起來也很牛的樣子。HashMap使用了4個值，就初始化4個大小。空間完全利用，而且又滿足了阿里開發手冊的規約?!
上述寫法真的對嗎?真的沒問題嗎?直接看代碼可能看不出來問題，我們添加一些打印信息。
如何驗證擴容
很多朋友可能也想驗證HashMap到底在什么時候進行擴容的，但苦于沒有思路或方法。這里提供一個簡單的方式，就是基于反射獲取并打印一下capacity的值。
還是上面的示例我們改造一下，向HashMap中添加數據時，打印對應的capacity和size這兩個屬性的值。
- public class MapTest {
- public static void main(String[] args) {
- Map<String, String> map = new HashMap<>(4);
- map.put("username", "Tom");
- print(map);
- map.put("address", "Bei Jing");
- print(map);
- map.put("age", "28");
- print(map);
- map.put("phone", "15800000000");
- print(map);
- }
- public static void print(Map<String, String> map) {
- try {
- Class<?> mapType = map.getClass();
- Method capacity = mapType.getDeclaredMethod("capacity");
- capacity.setAccessible(true);
- System.out.println("capacity : " + capacity.invoke(map) + " size : " + map.size());
- } catch (Exception e) {
- e.printStackTrace();
- }
- }
- }
其中print方法通過反射機制，獲取到Map中的capacity和size屬性值，然后進行打印。在main方法中，每新增一個數據，就打印一下Map的容量。
打印結果如下：
- capacity : 4 size : 1
- capacity : 4 size : 2
- capacity : 4 size : 3
- capacity : 8 size : 4
發現什么?當第4個數據put進去之后，HashMap的容量發生了一次擴容。
想想最開始我們指定初始容量的目的是什么?不就是為了避免擴容帶來的性能損失嗎?現在反而導致了擴容。
現在，如果去掉指定的初始值，采用new HashMap<>()的方式，執行一下程序，打印結果如下：
- capacity : 16 size : 1
- capacity : 16 size : 2
- capacity : 16 size : 3
- capacity : 16 size : 4
發現默認值并沒有擴容，理論上性能反而更高了。是不是很有意思?你是不是也走進了這個使用誤區了?
原理分析
之所會出現上述問題，最主要的是我們忽視了總結規約中的第二條，就是擴容機制。
HashMap的擴容機制，就是當達到擴容條件時會進行擴容。擴容條件就是當HashMap中的元素個數(size)超過臨界值(threshold)時就會自動擴容。在HashMap中，threshold = loadFactor * capacity。其中，默認的負載因子為0.75。
套入公式我們來算一下，負載因子為0.75，示例中capacity的值為4，得出臨界值為4 * 0.75 = 3。也就說，當實際的size超過3之后，就會觸發擴容，而擴容是直接將HashMap的容量加倍。這跟我們打印的結果一致。
JDK7和JDK8的實現是一樣的，關于實現源碼的分析，我們不放在本篇文章中進行分析。大家知道基本的原理及試驗效果即可。
HashMap初始化容量設置多少合適
經過上面的分析，我們已經看到隱含的問題了。這時不禁要問，HashMap初始化容量設置多少合適呢?是不是隨意寫一個比較大的數字就可以了呢?
這就需要我們了解當傳入初始化容量時，HashMap是如何處理的了。
當我們使用HashMap(int initialCapacity)來初始化容量時，HashMap并不會使用傳入的initialCapacity直接作為初始容量。
JDK會默認幫計算一個相對合理的值當做初始容量。所謂合理值，其實是找到第一個大于等于用戶傳入的值的2的冪的數值。實現源碼如下：
- static final int tableSizeFor(int cap) {
- int n = cap - 1;
- n |= n >>> 1;
- n |= n >>> 2;
- n |= n >>> 4;
- n |= n >>> 8;
- n |= n >>> 16;
- return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
- }
也就是說，當創建HashMap時，傳入了7，則初始化的容量為8;當傳入了18，則初始化容量為32。
此時，我們得出第一條結論：設置初始容量時，采用2的n次方的數值，即使不這么設置，JDK也會幫忙取下一個最近的2的n次方的數值。
上面的值看似合理了，但對于最初的實例，我們已經發現并不是存多少數據就設置多少的初始容量。因為還要考慮到擴容。
根據擴容公式可得出，如果設置初始容量為8，則8乘以0.75，也就6個值。在存儲小于等于6個值的時候，不會觸發擴容。
那么是否可以通過一個公式來反推呢?對應值的計算方法如下：
- return (int) ((float) expectedSize / 0.75F + 1.0F);
比如，計劃向HashMap中放入7個元素，通過expectedSize/0.75F + 1.0F計算，7/0.75 + 1 = 10，10經過JDK處理之后，會被設置成16。
那么此時，16就是比較合理的值，而且能大大減少了擴容的幾率。
所以，可以認為，當明確知道HashMap中元素個數時，把默認容量設置成expectedSize / 0.75F + 1.0F是一個在性能上相對好的選擇，但是，同時也會犧牲些內存。
其他相關知識
了解上述知識，最后再補充一些HashMap相關的知識點：
- HashMap在new后并不會立即分配bucket數組;
- HashMap的bucket數組大小是2的冪;
- HashMap在put的元素數量大于Capacity * LoadFactor(默認16 * 0.75)時會進行擴容;
- JDK8在哈希碰撞的鏈表長度達到TREEIFY_THRESHOLD(默認8)后，會把該鏈表轉變成樹結構，提高性能;
- JDK8在resize時，通過巧妙的設計，減少了rehash的性能消耗。
小結
本篇文章介紹了使用HashMap中的一些誤區，得出最大的結論可能就是不要因為對一個知識點一知半解而導致錯誤使用。同時，也介紹了一些分析方法和實現原理。
可能有朋友會問，要不要設置HashMap的初識值，這個值又設置成多少，真的有那么大影響嗎?不一定有很大影響，但性能的優化和個人技能的累積，不正是由這一點點的改進和提升而獲得的嗎?
