你給HashMap初始化了容量，卻讓性能變加更糟
本文轉(zhuǎn)載自微信公眾號「程序新視界」，作者二師兄。轉(zhuǎn)載本文請聯(lián)系程序新視界公眾號。
前言
項(xiàng)目中，看到大家已經(jīng)意識到初始化HashMap時給Map指定初始容量大小，甚是欣慰。但仔細(xì)一看，發(fā)現(xiàn)事情好像又有一些不對頭。雖然指定了大小，卻讓性能變得更加糟糕了。
可能你也是如此，看了《阿里巴巴Java開發(fā)手冊》感覺學(xué)到了很多，于是在實(shí)踐中開始嘗試給Map指定初始大小，并感覺自己寫的代碼高大上了一些。
的確，當(dāng)你意識到指定初始化值時，已經(jīng)比普通人更進(jìn)了一步，但是如果這個值指定的不好，程序的性能反而不如默認(rèn)值。
這篇文章就來從頭到尾分析一下，讀者多注意分析的方法和底層的原理實(shí)現(xiàn)。
阿里開發(fā)規(guī)范
我們先來看看阿里巴巴Java開發(fā)規(guī)范中是如何描述Map初始值大小這一規(guī)范的吧。
阿里巴巴《Java開發(fā)手冊》第1章編程規(guī)范，第6節(jié)集合處理的第17條規(guī)定如下：
【推薦】集合初始化時，指定集合初始值大小。說明：HashMap 使用HashMap(int initialCapacity)初始化，如果暫時無法確定集合大小，那么指定默認(rèn)值(16)即可。
正例：initialCapacity = (需要存儲的元素個數(shù) / 負(fù)載因子) + 1。注意負(fù)載因子(即loader factor)默認(rèn)為0.75，如果暫時無法確定初始值大小，請設(shè)置為16(即默認(rèn)值)。
反例：HashMap需要放置1024個元素，由于沒有設(shè)置容量初始大小，隨著元素不斷增加，容量7次被迫擴(kuò)大，resize需要重建hash表。當(dāng)放置的集合元素個數(shù)達(dá)千萬級別時，不斷擴(kuò)容會嚴(yán)重影響性能。
通過上面的規(guī)約我們大概了解到幾個信息：
- 第一，HashMap的默認(rèn)容量是16;
- 第二，容量擴(kuò)容與負(fù)載因子和存儲元素個數(shù)有關(guān);
- 第三，設(shè)置初始值是為了減少擴(kuò)容導(dǎo)致重建hash的性能影響。
可能你看完上述規(guī)約之后，就開始在代碼中進(jìn)行使用指定集合初始值的方式了，這很好。但稍有不慎，這中間卻會出現(xiàn)很多的問題，下面我們就來看看實(shí)例。
你指定的初始值對嗎?
直接上一段示例代碼，并思考這段代碼是否有問題：
- 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個大小。空間完全利用，而且又滿足了阿里開發(fā)手冊的規(guī)約?!
上述寫法真的對嗎?真的沒問題嗎?直接看代碼可能看不出來問題，我們添加一些打印信息。
如何驗(yàn)證擴(kuò)容
很多朋友可能也想驗(yàn)證HashMap到底在什么時候進(jìn)行擴(kuò)容的，但苦于沒有思路或方法。這里提供一個簡單的方式，就是基于反射獲取并打印一下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方法通過反射機(jī)制，獲取到Map中的capacity和size屬性值，然后進(jìn)行打印。在main方法中，每新增一個數(shù)據(jù)，就打印一下Map的容量。
打印結(jié)果如下：
- capacity : 4 size : 1
- capacity : 4 size : 2
- capacity : 4 size : 3
- capacity : 8 size : 4
發(fā)現(xiàn)什么?當(dāng)?shù)?個數(shù)據(jù)put進(jìn)去之后，HashMap的容量發(fā)生了一次擴(kuò)容。
想想最開始我們指定初始容量的目的是什么?不就是為了避免擴(kuò)容帶來的性能損失嗎?現(xiàn)在反而導(dǎo)致了擴(kuò)容。
現(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)默認(rèn)值并沒有擴(kuò)容，理論上性能反而更高了。是不是很有意思?你是不是也走進(jìn)了這個使用誤區(qū)了?
原理分析
之所會出現(xiàn)上述問題，最主要的是我們忽視了總結(jié)規(guī)約中的第二條，就是擴(kuò)容機(jī)制。
HashMap的擴(kuò)容機(jī)制，就是當(dāng)達(dá)到擴(kuò)容條件時會進(jìn)行擴(kuò)容。擴(kuò)容條件就是當(dāng)HashMap中的元素個數(shù)(size)超過臨界值(threshold)時就會自動擴(kuò)容。在HashMap中，threshold = loadFactor * capacity。其中，默認(rèn)的負(fù)載因子為0.75。
套入公式我們來算一下，負(fù)載因子為0.75，示例中capacity的值為4，得出臨界值為4 * 0.75 = 3。也就說，當(dāng)實(shí)際的size超過3之后，就會觸發(fā)擴(kuò)容，而擴(kuò)容是直接將HashMap的容量加倍。這跟我們打印的結(jié)果一致。
JDK7和JDK8的實(shí)現(xiàn)是一樣的，關(guān)于實(shí)現(xiàn)源碼的分析，我們不放在本篇文章中進(jìn)行分析。大家知道基本的原理及試驗(yàn)效果即可。
HashMap初始化容量設(shè)置多少合適
經(jīng)過上面的分析，我們已經(jīng)看到隱含的問題了。這時不禁要問，HashMap初始化容量設(shè)置多少合適呢?是不是隨意寫一個比較大的數(shù)字就可以了呢?
這就需要我們了解當(dāng)傳入初始化容量時，HashMap是如何處理的了。
當(dāng)我們使用HashMap(int initialCapacity)來初始化容量時，HashMap并不會使用傳入的initialCapacity直接作為初始容量。
JDK會默認(rèn)幫計算一個相對合理的值當(dāng)做初始容量。所謂合理值，其實(shí)是找到第一個大于等于用戶傳入的值的2的冪的數(shù)值。實(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;
- }
也就是說，當(dāng)創(chuàng)建HashMap時，傳入了7，則初始化的容量為8;當(dāng)傳入了18，則初始化容量為32。
此時，我們得出第一條結(jié)論：設(shè)置初始容量時，采用2的n次方的數(shù)值，即使不這么設(shè)置，JDK也會幫忙取下一個最近的2的n次方的數(shù)值。
上面的值看似合理了，但對于最初的實(shí)例，我們已經(jīng)發(fā)現(xiàn)并不是存多少數(shù)據(jù)就設(shè)置多少的初始容量。因?yàn)檫€要考慮到擴(kuò)容。
根據(jù)擴(kuò)容公式可得出，如果設(shè)置初始容量為8，則8乘以0.75，也就6個值。在存儲小于等于6個值的時候，不會觸發(fā)擴(kuò)容。
那么是否可以通過一個公式來反推呢?對應(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就是比較合理的值，而且能大大減少了擴(kuò)容的幾率。
所以，可以認(rèn)為，當(dāng)明確知道HashMap中元素個數(shù)時，把默認(rèn)容量設(shè)置成expectedSize / 0.75F + 1.0F是一個在性能上相對好的選擇，但是，同時也會犧牲些內(nèi)存。
其他相關(guān)知識
了解上述知識，最后再補(bǔ)充一些HashMap相關(guān)的知識點(diǎn)：
- HashMap在new后并不會立即分配bucket數(shù)組;
- HashMap的bucket數(shù)組大小是2的冪;
- HashMap在put的元素數(shù)量大于Capacity * LoadFactor(默認(rèn)16 * 0.75)時會進(jìn)行擴(kuò)容;
- JDK8在哈希碰撞的鏈表長度達(dá)到TREEIFY_THRESHOLD(默認(rèn)8)后，會把該鏈表轉(zhuǎn)變成樹結(jié)構(gòu)，提高性能;
- JDK8在resize時，通過巧妙的設(shè)計，減少了rehash的性能消耗。
小結(jié)
本篇文章介紹了使用HashMap中的一些誤區(qū)，得出最大的結(jié)論可能就是不要因?yàn)閷σ粋€知識點(diǎn)一知半解而導(dǎo)致錯誤使用。同時，也介紹了一些分析方法和實(shí)現(xiàn)原理。
可能有朋友會問，要不要設(shè)置HashMap的初識值，這個值又設(shè)置成多少，真的有那么大影響嗎?不一定有很大影響，但性能的優(yōu)化和個人技能的累積，不正是由這一點(diǎn)點(diǎn)的改進(jìn)和提升而獲得的嗎?
