[[396657]]

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

前言

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

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

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

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

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

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

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

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

正例：initialCapacity = (需要存儲的元素個數(shù) / 負載因子) + 1。注意負載因子(即loader factor)默認為0.75，如果暫時無法確定初始值大小，請設(shè)置為16(即默認值)。

反例：HashMap需要放置1024個元素，由于沒有設(shè)置容量初始大小，隨著元素不斷增加，容量7次被迫擴大，resize需要重建hash表。當放置的集合元素個數(shù)達千萬級別時，不斷擴容會嚴重影響性能。

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

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

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

你指定的初始值對嗎?

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

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個大小?？臻g完全利用，而且又滿足了阿里開發(fā)手冊的規(guī)約?!

上述寫法真的對嗎?真的沒問題嗎?直接看代碼可能看不出來問題，我們添加一些打印信息。

如何驗證擴容

很多朋友可能也想驗證HashMap到底在什么時候進行擴容的，但苦于沒有思路或方法。這里提供一個簡單的方式，就是基于反射獲取并打印一下capacity的值。

還是上面的示例我們改造一下，向HashMap中添加數(shù)據(jù)時，打印對應(yīng)的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方法中，每新增一個數(shù)據(jù)，就打印一下Map的容量。

打印結(jié)果如下：

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

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

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

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

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

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

原理分析

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

HashMap的擴容機制，就是當達到擴容條件時會進行擴容。擴容條件就是當HashMap中的元素個數(shù)(size)超過臨界值(threshold)時就會自動擴容。在HashMap中，threshold = loadFactor * capacity。其中，默認的負載因子為0.75。

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

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

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

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

這就需要我們了解當傳入初始化容量時，HashMap是如何處理的了。

當我們使用HashMap(int initialCapacity)來初始化容量時，HashMap并不會使用傳入的initialCapacity直接作為初始容量。

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

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; 
} 

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

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

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

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

那么是否可以通過一個公式來反推呢?對應(yīng)值的計算方法如下：

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

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

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

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

其他相關(guān)知識

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

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

小結(jié)

本篇文章介紹了使用HashMap中的一些誤區(qū)，得出最大的結(jié)論可能就是不要因為對一個知識點一知半解而導致錯誤使用。同時，也介紹了一些分析方法和實現(xiàn)原理。

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