日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

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

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷(xiāo)解決方案
你給HashMap初始化了容量，卻讓性能變加更糟

本文轉(zhuǎn)載自微信公眾號(hào)「程序新視界」，作者二師兄。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序新視界公眾號(hào)。 

成都創(chuàng)新互聯(lián)專(zhuān)業(yè)提供聯(lián)通機(jī)房服務(wù)器托管服務(wù)，為用戶(hù)提供五星數(shù)據(jù)中心、電信、雙線(xiàn)接入解決方案，用戶(hù)可自行在線(xiàn)購(gòu)買(mǎi)聯(lián)通機(jī)房服務(wù)器托管服務(wù)，并享受7*24小時(shí)金牌售后服務(wù)。

前言

項(xiàng)目中，看到大家已經(jīng)意識(shí)到初始化HashMap時(shí)給Map指定初始容量大小，甚是欣慰。但仔細(xì)一看，發(fā)現(xiàn)事情好像又有一些不對(duì)頭。雖然指定了大小，卻讓性能變得更加糟糕了。

可能你也是如此，看了《阿里巴巴Java開(kāi)發(fā)手冊(cè)》感覺(jué)學(xué)到了很多，于是在實(shí)踐中開(kāi)始嘗試給Map指定初始大小，并感覺(jué)自己寫(xiě)的代碼高大上了一些。

的確，當(dāng)你意識(shí)到指定初始化值時(shí)，已經(jīng)比普通人更進(jìn)了一步，但是如果這個(gè)值指定的不好，程序的性能反而不如默認(rèn)值。

這篇文章就來(lái)從頭到尾分析一下，讀者多注意分析的方法和底層的原理實(shí)現(xiàn)。

阿里開(kāi)發(fā)規(guī)范

我們先來(lái)看看阿里巴巴Java開(kāi)發(fā)規(guī)范中是如何描述Map初始值大小這一規(guī)范的吧。

阿里巴巴《Java開(kāi)發(fā)手冊(cè)》第1章編程規(guī)范，第6節(jié)集合處理的第17條規(guī)定如下：

【推薦】集合初始化時(shí)，指定集合初始值大小。說(shuō)明：HashMap 使用HashMap(int initialCapacity)初始化，如果暫時(shí)無(wú)法確定集合大小，那么指定默認(rèn)值(16)即可。

正例：initialCapacity = (需要存儲(chǔ)的元素個(gè)數(shù) / 負(fù)載因子) + 1。注意負(fù)載因子(即loader factor)默認(rèn)為0.75，如果暫時(shí)無(wú)法確定初始值大小，請(qǐng)?jiān)O(shè)置為16(即默認(rèn)值)。

反例：HashMap需要放置1024個(gè)元素，由于沒(méi)有設(shè)置容量初始大小，隨著元素不斷增加，容量7次被迫擴(kuò)大，resize需要重建hash表。當(dāng)放置的集合元素個(gè)數(shù)達(dá)千萬(wàn)級(jí)別時(shí)，不斷擴(kuò)容會(huì)嚴(yán)重影響性能。

通過(guò)上面的規(guī)約我們大概了解到幾個(gè)信息：

  • 第一，HashMap的默認(rèn)容量是16;
  • 第二，容量擴(kuò)容與負(fù)載因子和存儲(chǔ)元素個(gè)數(shù)有關(guān);
  • 第三，設(shè)置初始值是為了減少擴(kuò)容導(dǎo)致重建hash的性能影響。

可能你看完上述規(guī)約之后，就開(kāi)始在代碼中進(jìn)行使用指定集合初始值的方式了，這很好。但稍有不慎，這中間卻會(huì)出現(xiàn)很多的問(wèn)題，下面我們就來(lái)看看實(shí)例。

你指定的初始值對(duì)嗎?

直接上一段示例代碼，并思考這段代碼是否有問(wèn)題：

 
 
 
    
  
  
  
  1. Map map = new HashMap<>(4); 
    2.   
  
  
  2. map.put("username","Tom"); 
    3.   
  
  
  3. map.put("address","Bei Jing"); 
    4.   
  
  
  4. map.put("age","28"); 
    5.   
  
  
  5. map.put("phone","15800000000"); 
    6.   
  
  
  6. System.out.println(map); 
    7.

類(lèi)似的代碼是不是很熟悉，寫(xiě)起來(lái)也很牛的樣子。HashMap使用了4個(gè)值，就初始化4個(gè)大小。空間完全利用，而且又滿(mǎn)足了阿里開(kāi)發(fā)手冊(cè)的規(guī)約?!

上述寫(xiě)法真的對(duì)嗎?真的沒(méi)問(wèn)題嗎?直接看代碼可能看不出來(lái)問(wèn)題，我們添加一些打印信息。

如何驗(yàn)證擴(kuò)容

很多朋友可能也想驗(yàn)證HashMap到底在什么時(shí)候進(jìn)行擴(kuò)容的，但苦于沒(méi)有思路或方法。這里提供一個(gè)簡(jiǎn)單的方式，就是基于反射獲取并打印一下capacity的值。

還是上面的示例我們改造一下，向HashMap中添加數(shù)據(jù)時(shí)，打印對(duì)應(yīng)的capacity和size這兩個(gè)屬性的值。

 
 
 
    
  
  
  
  1. public class MapTest { 
    2.   
  
  
  2.  
    3.   
  
  
  3.     public static void main(String[] args) { 
    4.   
  
  
  4.         Map map = new HashMap<>(4); 
    5.   
  
  
  5.         map.put("username", "Tom"); 
    6.   
  
  
  6.         print(map); 
    7.   
  
  
  7.         map.put("address", "Bei Jing"); 
    8.   
  
  
  8.         print(map); 
    9.   
  
  
  9.         map.put("age", "28"); 
    10.   
  
  
  10.         print(map); 
    11.   
  
  
  11.         map.put("phone", "15800000000"); 
    12.   
  
  
  12.         print(map); 
    13.   
  
  
  13.     } 
    14.   
  
  
  14.  
    15.   
  
  
  15.     public static void print(Map map) { 
    16.   
  
  
  16.         try { 
    17.   
  
  
  17.             Class mapType = map.getClass(); 
    18.   
  
  
  18.             Method capacity = mapType.getDeclaredMethod("capacity"); 
    19.   
  
  
  19.             capacity.setAccessible(true); 
    20.   
  
  
  20.             System.out.println("capacity : " + capacity.invoke(map) + "    size : " + map.size()); 
    21.   
  
  
  21.         } catch (Exception e) { 
    22.   
  
  
  22.             e.printStackTrace(); 
    23.   
  
  
  23.         } 
    24.   
  
  
  24.     } 
    25.   
  
  
  25. } 
    26.

其中print方法通過(guò)反射機(jī)制，獲取到Map中的capacity和size屬性值，然后進(jìn)行打印。在main方法中，每新增一個(gè)數(shù)據(jù)，就打印一下Map的容量。

打印結(jié)果如下：

 
 
 
    
  
  
  
  1. capacity : 4    size : 1 
    2.   
  
  
  2. capacity : 4    size : 2 
    3.   
  
  
  3. capacity : 4    size : 3 
    4.   
  
  
  4. capacity : 8    size : 4 
    5.

發(fā)現(xiàn)什么?當(dāng)?shù)?個(gè)數(shù)據(jù)put進(jìn)去之后，HashMap的容量發(fā)生了一次擴(kuò)容。

想想最開(kāi)始我們指定初始容量的目的是什么?不就是為了避免擴(kuò)容帶來(lái)的性能損失嗎?現(xiàn)在反而導(dǎo)致了擴(kuò)容。

現(xiàn)在，如果去掉指定的初始值，采用new HashMap<>()的方式，執(zhí)行一下程序，打印結(jié)果如下：

 
 
 
    
  
  
  
  1. capacity : 16    size : 1 
    2.   
  
  
  2. capacity : 16    size : 2 
    3.   
  
  
  3. capacity : 16    size : 3 
    4.   
  
  
  4. capacity : 16    size : 4 
    5.

發(fā)現(xiàn)默認(rèn)值并沒(méi)有擴(kuò)容，理論上性能反而更高了。是不是很有意思?你是不是也走進(jìn)了這個(gè)使用誤區(qū)了?

原理分析

之所會(huì)出現(xiàn)上述問(wèn)題，最主要的是我們忽視了總結(jié)規(guī)約中的第二條，就是擴(kuò)容機(jī)制。

HashMap的擴(kuò)容機(jī)制，就是當(dāng)達(dá)到擴(kuò)容條件時(shí)會(huì)進(jìn)行擴(kuò)容。擴(kuò)容條件就是當(dāng)HashMap中的元素個(gè)數(shù)(size)超過(guò)臨界值(threshold)時(shí)就會(huì)自動(dòng)擴(kuò)容。在HashMap中，threshold = loadFactor * capacity。其中，默認(rèn)的負(fù)載因子為0.75。

套入公式我們來(lái)算一下，負(fù)載因子為0.75，示例中capacity的值為4，得出臨界值為4 * 0.75 = 3。也就說(shuō)，當(dāng)實(shí)際的size超過(guò)3之后，就會(huì)觸發(fā)擴(kuò)容，而擴(kuò)容是直接將HashMap的容量加倍。這跟我們打印的結(jié)果一致。

JDK7和JDK8的實(shí)現(xiàn)是一樣的，關(guān)于實(shí)現(xiàn)源碼的分析，我們不放在本篇文章中進(jìn)行分析。大家知道基本的原理及試驗(yàn)效果即可。

HashMap初始化容量設(shè)置多少合適

經(jīng)過(guò)上面的分析，我們已經(jīng)看到隱含的問(wèn)題了。這時(shí)不禁要問(wèn)，HashMap初始化容量設(shè)置多少合適呢?是不是隨意寫(xiě)一個(gè)比較大的數(shù)字就可以了呢?

這就需要我們了解當(dāng)傳入初始化容量時(shí)，HashMap是如何處理的了。

當(dāng)我們使用HashMap(int initialCapacity)來(lái)初始化容量時(shí)，HashMap并不會(huì)使用傳入的initialCapacity直接作為初始容量。

JDK會(huì)默認(rèn)幫計(jì)算一個(gè)相對(duì)合理的值當(dāng)做初始容量。所謂合理值，其實(shí)是找到第一個(gè)大于等于用戶(hù)傳入的值的2的冪的數(shù)值。實(shí)現(xiàn)源碼如下：

 
 
 
    
  
  
  
  1. static final int tableSizeFor(int cap) { 
    2.   
  
  
  2.     int n = cap - 1; 
    3.   
  
  
  3.     n |= n >>> 1; 
    4.   
  
  
  4.     n |= n >>> 2; 
    5.   
  
  
  5.     n |= n >>> 4; 
    6.   
  
  
  6.     n |= n >>> 8; 
    7.   
  
  
  7.     n |= n >>> 16; 
    8.   
  
  
  8.     return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; 
    9.   
  
  
  9. } 
    10.

也就是說(shuō)，當(dāng)創(chuàng)建HashMap時(shí)，傳入了7，則初始化的容量為8;當(dāng)傳入了18，則初始化容量為32。

此時(shí)，我們得出第一條結(jié)論：設(shè)置初始容量時(shí)，采用2的n次方的數(shù)值，即使不這么設(shè)置，JDK也會(huì)幫忙取下一個(gè)最近的2的n次方的數(shù)值。

上面的值看似合理了，但對(duì)于最初的實(shí)例，我們已經(jīng)發(fā)現(xiàn)并不是存多少數(shù)據(jù)就設(shè)置多少的初始容量。因?yàn)檫€要考慮到擴(kuò)容。

根據(jù)擴(kuò)容公式可得出，如果設(shè)置初始容量為8，則8乘以0.75，也就6個(gè)值。在存儲(chǔ)小于等于6個(gè)值的時(shí)候，不會(huì)觸發(fā)擴(kuò)容。

那么是否可以通過(guò)一個(gè)公式來(lái)反推呢?對(duì)應(yīng)值的計(jì)算方法如下：

 
 
 
    
  
  
  
  1. return (int) ((float) expectedSize / 0.75F + 1.0F); 
    2.

比如，計(jì)劃向HashMap中放入7個(gè)元素，通過(guò)expectedSize/0.75F + 1.0F計(jì)算，7/0.75 + 1 = 10，10經(jīng)過(guò)JDK處理之后，會(huì)被設(shè)置成16。

那么此時(shí)，16就是比較合理的值，而且能大大減少了擴(kuò)容的幾率。

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

其他相關(guān)知識(shí)

了解上述知識(shí)，最后再補(bǔ)充一些HashMap相關(guān)的知識(shí)點(diǎn)：

  • HashMap在new后并不會(huì)立即分配bucket數(shù)組;
  • HashMap的bucket數(shù)組大小是2的冪;
  • HashMap在put的元素?cái)?shù)量大于Capacity * LoadFactor(默認(rèn)16 * 0.75)時(shí)會(huì)進(jìn)行擴(kuò)容;
  • JDK8在哈希碰撞的鏈表長(zhǎng)度達(dá)到TREEIFY_THRESHOLD(默認(rèn)8)后，會(huì)把該鏈表轉(zhuǎn)變成樹(shù)結(jié)構(gòu)，提高性能;
  • JDK8在resize時(shí)，通過(guò)巧妙的設(shè)計(jì)，減少了rehash的性能消耗。

小結(jié)

本篇文章介紹了使用HashMap中的一些誤區(qū)，得出最大的結(jié)論可能就是不要因?yàn)閷?duì)一個(gè)知識(shí)點(diǎn)一知半解而導(dǎo)致錯(cuò)誤使用。同時(shí)，也介紹了一些分析方法和實(shí)現(xiàn)原理。

可能有朋友會(huì)問(wèn)，要不要設(shè)置HashMap的初識(shí)值，這個(gè)值又設(shè)置成多少，真的有那么大影響嗎?不一定有很大影響，但性能的優(yōu)化和個(gè)人技能的累積，不正是由這一點(diǎn)點(diǎn)的改進(jìn)和提升而獲得的嗎?


網(wǎng)站標(biāo)題：你給HashMap初始化了容量，卻讓性能變加更糟
本文URL：http://m.5511xx.com/article/dhocsej.html