為什么建議初始化 HashMap 的容量大小？ · java開發手冊

# 為什么建議初始化 HashMap 的容量大小？在《[HashMap中傻傻分不清楚的那些概念](http://www.javashuo.com/link?url=http://www.hollischuang.com/archives/2416)》文章中，咱們介紹了HashMap中和容量相關的幾個概念，簡單介紹了一下HashMap的擴容機制。html 文中咱們提到，默認狀況下HashMap的容量是16，可是，若是用戶經過構造函數指定了一個數字做為容量，那么Hash會選擇**大于該數字的第一個2的冪**做為容量。(3->四、7->八、9->16)程序員本文，延續上一篇文章，咱們再來深刻學習下，到底應不該該設置HashMap的默認容量？若是真的要設置HashMap的初始容量，咱們應該設置多少？算法 ### 為何要設置HashMap的初始化容量咱們以前提到過，《阿里巴巴Java開發手冊》中建議咱們設置HashMap的初始化容量。app 函數那么，為何要這么建議？你有想過沒有。性能咱們先來寫一段代碼在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個數的時候，設置一個合理的初始化容量能夠有效的提升性能。**spa 固然，以上結論也是有理論支撐的。咱們[上一篇](http://www.javashuo.com/link?url=http://www.hollischuang.com/archives/2416)文章介紹過，HashMap有擴容機制，就是當達到擴容條件時會進行擴容。HashMap的擴容條件就是當HashMap中的元素個數（size）超過臨界值（threshold）時就會自動擴容。在HashMap中，`threshold = loadFactor * capacity`。因此，若是咱們沒有設置初始容量大小，隨著元素的不斷增長，HashMap會發生屢次擴容，而HashMap中的擴容機制決定了每次擴容都須要重建hash表，是很是影響性能的。（關于resize，后面我會有文章單獨介紹）從上面的代碼示例中，咱們還發現，一樣是設置初始化容量，設置的數值不一樣也會影響性能，那么當咱們已知HashMap中即將存放的KV個數的時候，容量設置成多少為好呢？ ### 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)); ~~~ 初始化容量設置成1的時候，輸出結果是2。在jdk1.8中，若是咱們傳入的初始化容量為1，實際上設置的結果也為1，上面代碼輸出結果為2的緣由是代碼中map.put("hahaha", "hollischuang");致使了擴容，容量從1擴容到2。那么，話題再說回來，當咱們經過HashMap(int initialCapacity)設置初始容量的時候，HashMap并不必定會直接采用咱們傳入的數值，而是通過計算，獲得一個新值，目的是提升hash的效率。(1->一、3->四、7->八、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->八、9->1六、19->3二、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 對應到以上代碼中，Step1： ~~~ 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; ~~~ ### 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 是一個在性能上相對好的選擇，可是，同時也會犧牲些內存。 ### 總結當咱們想要在代碼中建立一個HashMap的時候，若是咱們已知這個Map中即將存放的元素個數，給HashMap設置初始容量能夠在必定程度上提高效率。可是，JDK并不會直接拿用戶傳進來的數字當作默認容量，而是會進行一番運算，最終獲得一個2的冪。緣由在（[全網把Map中的hash()分析的最透徹的文章，別無二家。](http://www.javashuo.com/link?url=http://www.hollischuang.com/archives/2091)）介紹過，獲得這個數字的算法實際上是使用了使用無符號右移和按位或運算來提高效率。