日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
為什么阿里巴巴建議集合初始化時(shí)，指定集合容量大小？

 集合是Java開發(fā)日常開發(fā)中經(jīng)常會(huì)使用到的。在之前的一些文章中，我們介紹過一些關(guān)于使用集合類應(yīng)該注意的事項(xiàng)，如《為什么阿里巴巴禁止在 foreach 循環(huán)里進(jìn)行元素的 remove/add 操作》。

關(guān)于集合類，《阿里巴巴Java開發(fā)手冊(cè)》中其實(shí)還有另外一個(gè)規(guī)定：

 

本文就來分析一下為什么會(huì)有如此建議?如果一定要設(shè)置初始容量的話，設(shè)置多少比較合適?

1.為什么要設(shè)置初始容量

我們先來寫一段代碼在JDK 1.7 (jdk1.7.0_79)下面來分別測試下，在不指定初始化容量和指定初始化容量的情況下性能情況如何。(jdk 8 結(jié)果會(huì)有所不同，我會(huì)在后面的文章中分析)

 
 
 
 
    
  
  
  
  
  1. public static void main(String[] args) { 
    2. 
  
  
  
  
  2.     int aHundredMillion = 10000000; 
    3. 
  
  
  
  
  3.  
    4. 
  
  
  
  
  4.     Map map = new HashMap<>(); 
    5. 
  
  
  
  
  5.  
    6. 
  
  
  
  
  6.     long s1 = System.currentTimeMillis(); 
    7. 
  
  
  
  
  7.     for (int i = 0; i < aHundredMillion; i++) { 
    8. 
  
  
  
  
  8.         map.put(i, i); 
    9. 
  
  
  
  
  9.     } 
    10. 
  
  
  
  
  10.     long s2 = System.currentTimeMillis(); 
    11. 
  
  
  
  
  11.  
    12. 
  
  
  
  
  12.     System.out.println("未初始化容量，耗時(shí) ： "+ (s2 - s1)); 
    13. 
  
  
  
  
  13.  
    14. 
  
  
  
  
  14.  
    15. 
  
  
  
  
  15.     Map map1 = new HashMap<>(aHundredMillion / 2); 
    16. 
  
  
  
  
  16.  
    17. 
  
  
  
  
  17.     long s5 = System.currentTimeMillis(); 
    18. 
  
  
  
  
  18.     for (int i = 0; i < aHundredMillion; i++) { 
    19. 
  
  
  
  
  19.         map1.put(i, i); 
    20. 
  
  
  
  
  20.     } 
    21. 
  
  
  
  
  21.     long s6 = System.currentTimeMillis(); 
    22. 
  
  
  
  
  22.  
    23. 
  
  
  
  
  23.     System.out.println("初始化容量5000000，耗時(shí) ： "+ (s6 - s5)); 
    24. 
  
  
  
  
  24.  
    25. 
  
  
  
  
  25.  
    26. 
  
  
  
  
  26.     Map map2 = new HashMap<>(aHundredMillion); 
    27. 
  
  
  
  
  27.  
    28. 
  
  
  
  
  28.     long s3 = System.currentTimeMillis(); 
    29. 
  
  
  
  
  29.     for (int i = 0; i < aHundredMillion; i++) { 
    30. 
  
  
  
  
  30.         map2.put(i, i); 
    31. 
  
  
  
  
  31.     } 
    32. 
  
  
  
  
  32.     long s4 = System.currentTimeMillis(); 
    33. 
  
  
  
  
  33.  
    34. 
  
  
  
  
  34.     System.out.println("初始化容量為10000000，耗時(shí) ： "+ (s4 - s3)); 
    35. 
  
  
  
  
  35. } 
    36.

以上代碼不難理解，我們創(chuàng)建了3個(gè)HashMap，分別使用默認(rèn)的容量(16)、使用元素個(gè)數(shù)的一半(5千萬)作為初始容量、使用元素個(gè)數(shù)(一億)作為初始容量進(jìn)行初始化。然后分別向其中put一億個(gè)KV。

輸出結(jié)果：

 
 
 
 
    
  
  
  
  
  1. 未初始化容量，耗時(shí) ：14419 
    2. 
  
  
  
  
  2. 初始化容量5000000，耗時(shí) ：11916 
    3. 
  
  
  
  
  3. 初始化容量為10000000，耗時(shí) ：7984 
    4.

從結(jié)果中，我們可以知道，在已知HashMap中將要存放的KV個(gè)數(shù)的時(shí)候，設(shè)置一個(gè)合理的初始化容量可以有效的提高性能。

當(dāng)然，以上結(jié)論也是有理論支撐的。我們HashMap中傻傻分不清楚的那些概念文章介紹過，HashMap有擴(kuò)容機(jī)制，就是當(dāng)達(dá)到擴(kuò)容條件時(shí)會(huì)進(jìn)行擴(kuò)容。HashMap的擴(kuò)容條件就是當(dāng)HashMap中的元素個(gè)數(shù)(size)超過臨界值(threshold)時(shí)就會(huì)自動(dòng)擴(kuò)容。在HashMap中， threshold = loadFactor * capacity。

所以，如果我們沒有設(shè)置初始容量大小，隨著元素的不斷增加，HashMap會(huì)發(fā)生多次擴(kuò)容，而HashMap中的擴(kuò)容機(jī)制決定了每次擴(kuò)容都需要重建hash表，是非常影響性能的。

從上面的代碼示例中，我們還發(fā)現(xiàn)，同樣是設(shè)置初始化容量，設(shè)置的數(shù)值不同也會(huì)影響性能，那么當(dāng)我們已知HashMap中即將存放的KV個(gè)數(shù)的時(shí)候，容量設(shè)置成多少為好呢?

2.HashMap中容量的初始化

默認(rèn)情況下，當(dāng)我們?cè)O(shè)置HashMap的初始化容量時(shí)，實(shí)際上HashMap會(huì)采用***個(gè)大于該數(shù)值的2的冪作為初始化容量。

如以下示例代碼：

 
 
 
 
    
  
  
  
  
  1. Map map = new HashMap(1); 
    2. 
  
  
  
  
  2. map.put("hahaha", "hollischuang"); 
    3. 
  
  
  
  
  3.  
    4. 
  
  
  
  
  4. Class mapType = map.getClass(); 
    5. 
  
  
  
  
  5. Method capacity = mapType.getDeclaredMethod("capacity"); 
    6. 
  
  
  
  
  6. capacity.setAccessible(true); 
    7. 
  
  
  
  
  7. System.out.println("capacity : "+ capacity.invoke(map)); 
    8.

在jdk1.7中，初始化容量設(shè)置成1的時(shí)候，輸出結(jié)果是2。在jdk1.8中，如果我們傳入的初始化容量為1，實(shí)際上設(shè)置的結(jié)果也為1，上面代碼輸出結(jié)果為2的原因是代碼中map.put(“hahaha”, “hollischuang”);導(dǎo)致了擴(kuò)容，容量從1擴(kuò)容到2。

那么，話題再說回來，當(dāng)我們通過HashMap(int initialCapacity)設(shè)置初始容量的時(shí)候，HashMap并不一定會(huì)直接采用我們傳入的數(shù)值，而是經(jīng)過計(jì)算，得到一個(gè)新值，目的是提高h(yuǎn)ash的效率。(1->1、3->4、7->8、9->16)

在Jdk 1.7和Jdk 1.8中，HashMap初始化這個(gè)容量的時(shí)機(jī)不同。jdk1.8中，在調(diào)用HashMap的構(gòu)造函數(shù)定義HashMap的時(shí)候，就會(huì)進(jìn)行容量的設(shè)定。而在Jdk 1.7中，要等到***次put操作時(shí)才進(jìn)行這一操作。

不管是Jdk 1.7還是Jdk 1.8，計(jì)算初始化容量的算法其實(shí)是如出一轍的，主要代碼如下：

 
 
 
 
    
  
  
  
  
  1. int n = cap - 1; 
    2. 
  
  
  
  
  2. n |= n >>> 1; 
    3. 
  
  
  
  
  3. n |= n >>> 2; 
    4. 
  
  
  
  
  4. n |= n >>> 4; 
    5. 
  
  
  
  
  5. n |= n >>> 8; 
    6. 
  
  
  
  
  6. n |= n >>> 16; 
    7. 
  
  
  
  
  7. return (n < 0) ?1 :(n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
    8.

上面的代碼挺有意思的，一個(gè)簡單的容量初始化，Java的工程師也有很多考慮在里面。

上面的算法目的挺簡單，就是：根據(jù)用戶傳入的容量值(代碼中的cap)，通過計(jì)算，得到***個(gè)比他大的2的冪并返回。

聰明的讀者們，如果讓你設(shè)計(jì)這個(gè)算法你準(zhǔn)備如何計(jì)算?如果你想到二進(jìn)制的話，那就很簡單了。舉幾個(gè)例子看一下：

 

請(qǐng)關(guān)注上面的幾個(gè)例子中，藍(lán)色字體部分的變化情況，或許你會(huì)發(fā)現(xiàn)些規(guī)律。5->8、9->16、19->32、37->64都是主要經(jīng)過了兩個(gè)階段。

 
 
 
 
    
  
  
  
  
  1. Step 1，5->7 
    2. 
  
  
  
  
  2. Step 2，7->8 
    3. 
  
  
  
  
  3.  
    4. 
  
  
  
  
  4. Step 1，9->15 
    5. 
  
  
  
  
  5. Step 2，15->16 
    6. 
  
  
  
  
  6.  
    7. 
  
  
  
  
  7. Step 1，19->31 
    8. 
  
  
  
  
  8. Step 2，31->32 
    9. 
  
  
  
  
  9.  
    10. 
  
  
  
  
  10. Step 1，37->63 
    11. 
  
  
  
  
  11. Step 2，63->65 
    12.

對(duì)應(yīng)到以上代碼中，Step 1：

 
 
 
 
    
  
  
  
  
  1. n |= n >>> 1; 
    2. 
  
  
  
  
  2. n |= n >>> 2; 
    3. 
  
  
  
  
  3. n |= n >>> 4; 
    4. 
  
  
  
  
  4. n |= n >>> 8; 
    5. 
  
  
  
  
  5. n |= n >>> 16; 
    6.

對(duì)應(yīng)到以上代碼中，Step2：

 
 
 
 
    
  
  
  
  
  1. return (n < 0) ?1 :(n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
    2.

Step 2 比較簡單，就是做一下極限值的判斷，然后把Step 1得到的數(shù)值+1。

Step 1 怎么理解呢?其實(shí)是對(duì)一個(gè)二進(jìn)制數(shù)依次向右移位，然后與原值取或。其目的對(duì)于一個(gè)數(shù)字的二進(jìn)制，從***個(gè)不為0的位開始，把后面的所有位都設(shè)置成1。

隨便拿一個(gè)二進(jìn)制數(shù)，套一遍上面的公式就發(fā)現(xiàn)其目的了：

 
 
 
 
    
  
  
  
  
  1. 1100 1100 1100 >>>1 = 0110 0110 0110 
    2. 
  
  
  
  
  2. 1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110 
    3. 
  
  
  
  
  3. 1110 1110 1110 >>>2 = 0011 1011 1011 
    4. 
  
  
  
  
  4. 1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111 
    5. 
  
  
  
  
  5. 1111 1111 1111 >>>4 = 1111 1111 1111 
    6. 
  
  
  
  
  6. 1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111 
    7.

通過幾次無符號(hào)右移和按位或運(yùn)算，我們把1100 1100 1100轉(zhuǎn)換成了1111 1111 1111 ，再把1111 1111 1111加1，就得到了1 0000 0000 0000，這就是大于1100 1100 1100的***個(gè)2的冪。

好了，我們現(xiàn)在解釋清楚了Step 1和Step 2的代碼。就是可以把一個(gè)數(shù)轉(zhuǎn)化成***個(gè)比他自身大的2的冪。(可以開始佩服Java的工程師們了，使用無符號(hào)右移和按位或運(yùn)算大大提升了效率。)

但是還有一種特殊情況套用以上公式不行，這些數(shù)字就是2的冪自身。如果數(shù)字4 套用公式的話。得到的會(huì)是 8 ：

 
 
 
 
    
  
  
  
  
  1. Step 1:  
    2. 
  
  
  
  
  2. 0100 >>>1 = 0010 
    3. 
  
  
  
  
  3. 0100 | 0010 = 0110 
    4. 
  
  
  
  
  4. 0110 >>>1 = 0011 
    5. 
  
  
  
  
  5. 0110 | 0011 = 0111 
    6. 
  
  
  
  
  6. Step 2: 
    7. 
  
  
  
  
  7. 0111 + 0001 = 1000 
    8.

為了解決這個(gè)問題，JDK的工程師把所有用戶傳進(jìn)來的數(shù)在進(jìn)行計(jì)算之前先-1，就是源碼中的***行：

 
 
 
 
    
  
  
  
  
  1. int n = cap - 1; 
    2.

至此，再來回過頭看看這個(gè)設(shè)置初始容量的代碼，目的是不是一目了然了：

 
 
 
 
    
  
  
  
  
  1. int n = cap - 1; 
    2. 
  
  
  
  
  2. n |= n >>> 1; 
    3. 
  
  
  
  
  3. n |= n >>> 2; 
    4. 
  
  
  
  
  4. n |= n >>> 4; 
    5. 
  
  
  
  
  5. n |= n >>> 8; 
    6. 
  
  
  
  
  6. n |= n >>> 16; 
    7. 
  
  
  
  
  7. return (n < 0) ?1 :(n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
    8.

3.HashMap初始容量的合理值

當(dāng)我們使用 HashMap(int initialCapacity) 來初始化容量的時(shí)候，jdk會(huì)默認(rèn)幫我們計(jì)算一個(gè)相對(duì)合理的值當(dāng)做初始容量。那么，是不是我們只需要把已知的HashMap中即將存放的元素個(gè)數(shù)直接傳給initialCapacity就可以了呢?

關(guān)于這個(gè)值的設(shè)置，在《阿里巴巴Java開發(fā)手冊(cè)》有以下建議：

 

這個(gè)值，并不是阿里巴巴的工程師原創(chuàng)的，在guava(21.0版本)中也使用的是這個(gè)值。

 
 
 
 
    
  
  
  
  
  1. public static  HashMap newHashMapWithExpectedSize(int expectedSize) { 
    2. 
  
  
  
  
  2.     return new HashMap(capacity(expectedSize)); 
    3. 
  
  
  
  
  3. } 
    4. 
  
  
  
  
  4. /** 
    5. 
  
  
  
  
  5. * Returns a capacity that is sufficient to keep the map from being resized as long as it grows no 
    6. 
  
  
  
  
  6. * larger than expectedSize and the load factor is ≥ its default (0.75). 
    7. 
  
  
  
  
  7. */ 
    8. 
  
  
  
  
  8. static int capacity(int expectedSize) { 
    9. 
  
  
  
  
  9.     if (expectedSize < 3) { 
    10. 
  
  
  
  
  10.       checkNonnegative(expectedSize, "expectedSize"); 
    11. 
  
  
  
  
  11.       return expectedSize + 1; 
    12. 
  
  
  
  
  12.     } 
    13. 
  
  
  
  
  13.     if (expectedSize < Ints.MAX_POWER_OF_TWO) { 
    14. 
  
  
  
  
  14.       // This is the calculation used in JDK8 to resize when a putAll 
    15. 
  
  
  
  
  15.       // happens; it seems to be the most conservative calculation we 
    16. 
  
  
  
  
  16.       // can make.  0.75 is the default load factor. 
    17. 
  
  
  
  
  17.       return (int) ((float) expectedSize / 0.75F + 1.0F); 
    18. 
  
  
  
  
  18.     } 
    19. 
  
  
  
  
  19.     return Integer.MAX_VALUE; // any large value 
    20. 
  
  
  
  
  20. } 
    21.

在return (int) ((float) expectedSize / 0.75F + 1.0F);上面有一行注釋，說明了這個(gè)公式也不是guava原創(chuàng)，參考的是JDK8中putAll方法中的實(shí)現(xiàn)的。感興趣的讀者可以去看下putAll方法的實(shí)現(xiàn)，也是以上的這個(gè)公式。

雖然，當(dāng)我們使用 HashMap(int initialCapacity) 來初始化容量的時(shí)候，jdk會(huì)默認(rèn)幫我們計(jì)算一個(gè)相對(duì)合理的值當(dāng)做初始容量。但是這個(gè)值并沒有參考loadFactor的值。

也就是說，如果我們?cè)O(shè)置的默認(rèn)值是7，經(jīng)過Jdk處理之后，會(huì)被設(shè)置成8，但是，這個(gè)HashMap在元素個(gè)數(shù)達(dá)到 8*0.75 = 6的時(shí)候就會(huì)進(jìn)行一次擴(kuò)容，這明顯是我們不希望見到的。

如果我們通過 expectedSize / 0.75F + 1.0F 計(jì)算，7/0.75 + 1 = 10 ,10經(jīng)過Jdk處理之后，會(huì)被設(shè)置成16，這就大大的減少了擴(kuò)容的幾率。

當(dāng)HashMap內(nèi)部維護(hù)的哈希表的容量達(dá)到75%時(shí)(默認(rèn)情況下)，會(huì)觸發(fā)rehash，而rehash的過程是比較耗費(fèi)時(shí)間的。所以初始化容量要設(shè)置成expectedSize/0.75 + 1的話，可以有效的減少?zèng)_突也可以減小誤差。

所以，我可以認(rèn)為，當(dāng)我們明確知道HashMap中元素的個(gè)數(shù)的時(shí)候，把默認(rèn)容量設(shè)置成 expectedSize / 0.75F + 1.0F 是一個(gè)在性能上相對(duì)好的選擇，但是，同時(shí)也會(huì)犧牲些內(nèi)存。

4.總結(jié)

當(dāng)我們想要在代碼中創(chuàng)建一個(gè)HashMap的時(shí)候，如果我們已知這個(gè)Map中即將存放的元素個(gè)數(shù)，給HashMap設(shè)置初始容量可以在一定程度上提升效率。

但是，JDK并不會(huì)直接拿用戶傳進(jìn)來的數(shù)字當(dāng)做默認(rèn)容量，而是會(huì)進(jìn)行一番運(yùn)算，最終得到一個(gè)2的冪。原因在《全網(wǎng)把Map中的hash()分析的最透徹的文章，別無二家》介紹過，得到這個(gè)數(shù)字的算法其實(shí)是使用了使用無符號(hào)右移和按位或運(yùn)算來提升效率。

但是，為了***程度的避免擴(kuò)容帶來的性能消耗，我們建議可以把默認(rèn)容量的數(shù)字設(shè)置成expectedSize / 0.75F + 1.0F 。在日常開發(fā)中，可以使用

 
 
 
 
    
  
  
  
  
  1. Map map = Maps.newHashMapWithExpectedSize(10); 
    2.

來創(chuàng)建一個(gè)HashMap，計(jì)算的過程guava會(huì)幫我們完成。

但是，以上的操作是一種用內(nèi)存換性能的做法，真正使用的時(shí)候，要考慮到內(nèi)存的影響。

***，留一個(gè)思考題：為什么JDK 8中，putAll方法采用了這個(gè)expectedSize / 0.75F + 1.0F公式，而put、構(gòu)造函數(shù)等并沒有默認(rèn)使用這個(gè)公式呢?

【本文是專欄作者Hollis的原創(chuàng)文章，作者微信公眾號(hào)Hollis(ID：hollischuang)】


網(wǎng)站欄目：為什么阿里巴巴建議集合初始化時(shí)，指定集合容量大小？
文章鏈接：http://www.dlmjj.cn/article/djecejg.html