為什么阿里巴巴建議集合初始化時，指定集合容量大小？
集合是Java開發日常開發中經常會使用到的。在之前的一些文章中，我們介紹過一些關于使用集合類應該注意的事項，如《為什么阿里巴巴禁止在 foreach 循環里進行元素的 remove/add 操作》。
關于集合類，《阿里巴巴Java開發手冊》中其實還有另外一個規定：
本文就來分析一下為什么會有如此建議?如果一定要設置初始容量的話，設置多少比較合適?
1.為什么要設置初始容量
我們先來寫一段代碼在JDK 1.7 (jdk1.7.0_79)下面來分別測試下，在不指定初始化容量和指定初始化容量的情況下性能情況如何。(jdk 8 結果會有所不同，我會在后面的文章中分析)
- public static void main(String[] args) {
- int aHundredMillion = 10000000;
- Map<Integer, Integer> map = new HashMap<>();
- long s1 = System.currentTimeMillis();
- for (int i = 0; i < aHundredMillion; i++) {
- map.put(i, i);
- }
- long s2 = System.currentTimeMillis();
- System.out.println("未初始化容量，耗時 ： "+ (s2 - s1));
- Map<Integer, Integer> map1 = new HashMap<>(aHundredMillion / 2);
- long s5 = System.currentTimeMillis();
- for (int i = 0; i < aHundredMillion; i++) {
- map1.put(i, i);
- }
- long s6 = System.currentTimeMillis();
- System.out.println("初始化容量5000000，耗時 ： "+ (s6 - s5));
- Map<Integer, Integer> map2 = new HashMap<>(aHundredMillion);
- long s3 = System.currentTimeMillis();
- for (int i = 0; i < aHundredMillion; i++) {
- map2.put(i, i);
- }
- long s4 = System.currentTimeMillis();
- System.out.println("初始化容量為10000000，耗時 ： "+ (s4 - s3));
- }
以上代碼不難理解，我們創建了3個HashMap，分別使用默認的容量(16)、使用元素個數的一半(5千萬)作為初始容量、使用元素個數(一億)作為初始容量進行初始化。然后分別向其中put一億個KV。
輸出結果：
- 未初始化容量，耗時 ：14419
- 初始化容量5000000，耗時 ：11916
- 初始化容量為10000000，耗時 ：7984
從結果中，我們可以知道，在已知HashMap中將要存放的KV個數的時候，設置一個合理的初始化容量可以有效的提高性能。
當然，以上結論也是有理論支撐的。我們HashMap中傻傻分不清楚的那些概念文章介紹過，HashMap有擴容機制，就是當達到擴容條件時會進行擴容。HashMap的擴容條件就是當HashMap中的元素個數(size)超過臨界值(threshold)時就會自動擴容。在HashMap中， threshold = loadFactor * capacity。
所以，如果我們沒有設置初始容量大小，隨著元素的不斷增加，HashMap會發生多次擴容，而HashMap中的擴容機制決定了每次擴容都需要重建hash表，是非常影響性能的。
從上面的代碼示例中，我們還發現，同樣是設置初始化容量，設置的數值不同也會影響性能，那么當我們已知HashMap中即將存放的KV個數的時候，容量設置成多少為好呢?
2.HashMap中容量的初始化
默認情況下，當我們設置HashMap的初始化容量時，實際上HashMap會采用***個大于該數值的2的冪作為初始化容量。
如以下示例代碼：
- Map<String, String> map = new HashMap<String, String>(1);
- map.put("hahaha", "hollischuang");
- Class<?> mapType = map.getClass();
- Method capacity = mapType.getDeclaredMethod("capacity");
- capacity.setAccessible(true);
- System.out.println("capacity : "+ capacity.invoke(map));
在jdk1.7中，初始化容量設置成1的時候，輸出結果是2。在jdk1.8中，如果我們傳入的初始化容量為1，實際上設置的結果也為1，上面代碼輸出結果為2的原因是代碼中map.put(“hahaha”, “hollischuang”);導致了擴容，容量從1擴容到2。
那么，話題再說回來，當我們通過HashMap(int initialCapacity)設置初始容量的時候，HashMap并不一定會直接采用我們傳入的數值，而是經過計算，得到一個新值，目的是提高hash的效率。(1->1、3->4、7->8、9->16)
在Jdk 1.7和Jdk 1.8中，HashMap初始化這個容量的時機不同。jdk1.8中，在調用HashMap的構造函數定義HashMap的時候，就會進行容量的設定。而在Jdk 1.7中，要等到***次put操作時才進行這一操作。
不管是Jdk 1.7還是Jdk 1.8，計算初始化容量的算法其實是如出一轍的，主要代碼如下：
- 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;
上面的代碼挺有意思的，一個簡單的容量初始化，Java的工程師也有很多考慮在里面。
上面的算法目的挺簡單，就是：根據用戶傳入的容量值(代碼中的cap)，通過計算，得到***個比他大的2的冪并返回。
聰明的讀者們，如果讓你設計這個算法你準備如何計算?如果你想到二進制的話，那就很簡單了。舉幾個例子看一下：
請關注上面的幾個例子中，藍色字體部分的變化情況，或許你會發現些規律。5->8、9->16、19->32、37->64都是主要經過了兩個階段。
- Step 1，5->7
- Step 2，7->8
- Step 1，9->15
- Step 2，15->16
- Step 1，19->31
- Step 2，31->32
- Step 1，37->63
- Step 2，63->65
對應到以上代碼中，Step 1：
- n |= n >>> 1;
- n |= n >>> 2;
- n |= n >>> 4;
- n |= n >>> 8;
- n |= n >>> 16;
對應到以上代碼中，Step2：
- return (n < 0) ?1 :(n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
Step 2 比較簡單，就是做一下極限值的判斷，然后把Step 1得到的數值+1。
Step 1 怎么理解呢?其實是對一個二進制數依次向右移位，然后與原值取或。其目的對于一個數字的二進制，從***個不為0的位開始，把后面的所有位都設置成1。
隨便拿一個二進制數，套一遍上面的公式就發現其目的了：
- 1100 1100 1100 >>>1 = 0110 0110 0110
- 1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110
- 1110 1110 1110 >>>2 = 0011 1011 1011
- 1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111
- 1111 1111 1111 >>>4 = 1111 1111 1111
- 1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111
通過幾次無符號右移和按位或運算，我們把1100 1100 1100轉換成了1111 1111 1111 ，再把1111 1111 1111加1，就得到了1 0000 0000 0000，這就是大于1100 1100 1100的***個2的冪。
好了，我們現在解釋清楚了Step 1和Step 2的代碼。就是可以把一個數轉化成***個比他自身大的2的冪。(可以開始佩服Java的工程師們了，使用無符號右移和按位或運算大大提升了效率。)
但是還有一種特殊情況套用以上公式不行，這些數字就是2的冪自身。如果數字4 套用公式的話。得到的會是 8 ：
- Step 1:
- 0100 >>>1 = 0010
- 0100 | 0010 = 0110
- 0110 >>>1 = 0011
- 0110 | 0011 = 0111
- Step 2:
- 0111 + 0001 = 1000
為了解決這個問題，JDK的工程師把所有用戶傳進來的數在進行計算之前先-1，就是源碼中的***行：
- int n = cap - 1;
至此，再來回過頭看看這個設置初始容量的代碼，目的是不是一目了然了：
- 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;
3.HashMap初始容量的合理值
當我們使用 HashMap(int initialCapacity) 來初始化容量的時候，jdk會默認幫我們計算一個相對合理的值當做初始容量。那么，是不是我們只需要把已知的HashMap中即將存放的元素個數直接傳給initialCapacity就可以了呢?
關于這個值的設置，在《阿里巴巴Java開發手冊》有以下建議：
這個值，并不是阿里巴巴的工程師原創的，在guava(21.0版本)中也使用的是這個值。
- public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {
- return new HashMap<K, V>(capacity(expectedSize));
- }
- /**
- * Returns a capacity that is sufficient to keep the map from being resized as long as it grows no
- * larger than expectedSize and the load factor is ≥ its default (0.75).
- */
- static int capacity(int expectedSize) {
- if (expectedSize < 3) {
- checkNonnegative(expectedSize, "expectedSize");
- return expectedSize + 1;
- }
- if (expectedSize < Ints.MAX_POWER_OF_TWO) {
- // This is the calculation used in JDK8 to resize when a putAll
- // happens; it seems to be the most conservative calculation we
- // can make. 0.75 is the default load factor.
- return (int) ((float) expectedSize / 0.75F + 1.0F);
- }
- return Integer.MAX_VALUE; // any large value
- }
在return (int) ((float) expectedSize / 0.75F + 1.0F);上面有一行注釋，說明了這個公式也不是guava原創，參考的是JDK8中putAll方法中的實現的。感興趣的讀者可以去看下putAll方法的實現，也是以上的這個公式。
雖然，當我們使用 HashMap(int initialCapacity) 來初始化容量的時候，jdk會默認幫我們計算一個相對合理的值當做初始容量。但是這個值并沒有參考loadFactor的值。
也就是說，如果我們設置的默認值是7，經過Jdk處理之后，會被設置成8，但是，這個HashMap在元素個數達到 8*0.75 = 6的時候就會進行一次擴容，這明顯是我們不希望見到的。
如果我們通過 expectedSize / 0.75F + 1.0F 計算，7/0.75 + 1 = 10 ,10經過Jdk處理之后，會被設置成16，這就大大的減少了擴容的幾率。
當HashMap內部維護的哈希表的容量達到75%時(默認情況下)，會觸發rehash，而rehash的過程是比較耗費時間的。所以初始化容量要設置成expectedSize/0.75 + 1的話，可以有效的減少沖突也可以減小誤差。
所以，我可以認為，當我們明確知道HashMap中元素的個數的時候，把默認容量設置成 expectedSize / 0.75F + 1.0F 是一個在性能上相對好的選擇，但是，同時也會犧牲些內存。
4.總結
當我們想要在代碼中創建一個HashMap的時候，如果我們已知這個Map中即將存放的元素個數，給HashMap設置初始容量可以在一定程度上提升效率。
但是，JDK并不會直接拿用戶傳進來的數字當做默認容量，而是會進行一番運算，最終得到一個2的冪。原因在《全網把Map中的hash()分析的最透徹的文章，別無二家》介紹過，得到這個數字的算法其實是使用了使用無符號右移和按位或運算來提升效率。
但是，為了***程度的避免擴容帶來的性能消耗，我們建議可以把默認容量的數字設置成expectedSize / 0.75F + 1.0F 。在日常開發中，可以使用
- Map<String, String> map = Maps.newHashMapWithExpectedSize(10);
來創建一個HashMap，計算的過程guava會幫我們完成。
但是，以上的操作是一種用內存換性能的做法，真正使用的時候，要考慮到內存的影響。
***，留一個思考題：為什么JDK 8中，putAll方法采用了這個expectedSize / 0.75F + 1.0F公式，而put、構造函數等并沒有默認使用這個公式呢?
【本文是51CTO專欄作者Hollis的原創文章，作者微信公眾號Hollis(ID：hollischuang)】
