阿里巴巴Java開發(fā)手冊(cè)建議創(chuàng)建HashMap時(shí)設(shè)置初始化容量，但是多少合適呢？
集合是Java開發(fā)日常開發(fā)中經(jīng)常會(huì)使用到的，而作為一種典型的K-V結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)，HashMap對(duì)于Java開發(fā)者一定不陌生。
關(guān)于HashMap，很多人都對(duì)他有一些基本的了解，比如他和hashtable之間的區(qū)別、他和concurrentHashMap之間的區(qū)別等。這些都是比較常見的，關(guān)于HashMap的一些知識(shí)點(diǎn)和面試題，想來大家一定了熟于心了，并且在開發(fā)中也能有效的應(yīng)用上。
但是，作者在很多次 CodeReview 以及面試中發(fā)現(xiàn)，有一個(gè)比較關(guān)鍵的小細(xì)節(jié)經(jīng)常被忽視，那就是HashMap創(chuàng)建的時(shí)候，要不要指定容量?如果要指定的話，多少是合適的?為什么?
要設(shè)置HashMap的初始化容量
在《HashMap中傻傻分不清楚的那些概念》中我們?cè)?jīng)有過以下結(jié)論：
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ā)者在創(chuàng)建HashMap的時(shí)候指定初始化容量。并且《阿里巴巴開發(fā)手冊(cè)》中也是這么建議的：
HashMap初始化容量設(shè)置多少合適
那么，既然建議我們集合初始化的時(shí)候，要指定初始值大小，那么我們創(chuàng)建HashMap的時(shí)候，到底指定多少合適呢?
有些人會(huì)自然想到，我準(zhǔn)備塞多少個(gè)元素我就設(shè)置成多少唄。比如我準(zhǔn)備塞7個(gè)元素，那就new HashMap(7)。
但是，這么做不僅不對(duì)，而且以上方式創(chuàng)建出來的Map的容量也不是7。
因?yàn)?，?dāng)我們使用HashMap(int initialCapacity)來初始化容量的時(shí)候，HashMap并不會(huì)使用我們傳進(jìn)來的initialCapacity直接作為初始容量。
JDK會(huì)默認(rèn)幫我們計(jì)算一個(gè)相對(duì)合理的值當(dāng)做初始容量。所謂合理值，其實(shí)是找到第一個(gè)比用戶傳入的值大的2的冪。
也就是說，當(dāng)我們new HashMap(7)創(chuàng)建HashMap的時(shí)候，JDK會(huì)通過計(jì)算，幫我們創(chuàng)建一個(gè)容量為8的Map;當(dāng)我們new HashMap(9)創(chuàng)建HashMap的時(shí)候，JDK會(huì)通過計(jì)算，幫我們創(chuàng)建一個(gè)容量為16的Map。
但是，這個(gè)值看似合理，實(shí)際上并不盡然。因?yàn)镠ashMap在根據(jù)用戶傳入的capacity計(jì)算得到的默認(rèn)容量，并沒有考慮到loadFactor這個(gè)因素，只是簡(jiǎn)單機(jī)械的計(jì)算出第一個(gè)大約這個(gè)數(shù)字的2的冪。
loadFactor是負(fù)載因子，當(dāng)HashMap中的元素個(gè)數(shù)(size)超過 threshold = loadFactor * capacity時(shí)，就會(huì)進(jìn)行擴(kuò)容。
也就是說，如果我們?cè)O(shè)置的默認(rèn)值是7，經(jīng)過JDK處理之后，HashMap的容量會(huì)被設(shè)置成8，但是，這個(gè)HashMap在元素個(gè)數(shù)達(dá)到 8*0.75 = 6的時(shí)候就會(huì)進(jìn)行一次擴(kuò)容，這明顯是我們不希望見到的。
那么，到底設(shè)置成什么值比較合理呢?
這里我們可以參考JDK8中putAll方法中的實(shí)現(xiàn)的，這個(gè)實(shí)現(xiàn)在guava(21.0版本)也被采用。
這個(gè)值的計(jì)算方法就是：
return (int) ((float) expectedSize / 0.75F + 1.0F);
比如我們計(jì)劃向HashMap中放入7個(gè)元素的時(shí)候，我們通過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)_突也可以減小誤差。(大家結(jié)合這個(gè)公式，好好理解下這句話)
所以，我們可以認(rèn)為，當(dāng)我們明確知道HashMap中元素的個(gè)數(shù)的時(shí)候，把默認(rèn)容量設(shè)置成expectedSize / 0.75F + 1.0F 是一個(gè)在性能上相對(duì)好的選擇，但是，同時(shí)也會(huì)犧牲些內(nèi)存。
這個(gè)算法在guava中有實(shí)現(xiàn)，開發(fā)的時(shí)候，可以直接通過Maps類創(chuàng)建一個(gè)HashMap：
Map
其代碼實(shí)現(xiàn)如下：
- public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {
- return new HashMap(capacity(expectedSize));
- }
- static int capacity(int expectedSize) {
- if (expectedSize < 3) {
- CollectPreconditions.checkNonnegative(expectedSize, "expectedSize");
- return expectedSize + 1;
- } else {
- return expectedSize < 1073741824 ? (int)((float)expectedSize / 0.75F + 1.0F) : 2147483647;
- }
- }
但是，以上的操作是一種用內(nèi)存換性能的做法，真正使用的時(shí)候，要考慮到內(nèi)存的影響。但是，大多數(shù)情況下，我們還是認(rèn)為內(nèi)存是一種比較富裕的資源。
但是話又說回來了，有些時(shí)候，我們到底要不要設(shè)置HashMap的初識(shí)值，這個(gè)值又設(shè)置成多少，真的有那么大影響嗎?其實(shí)也不見得!
可是，大的性能優(yōu)化，不就是一個(gè)一個(gè)的優(yōu)化細(xì)節(jié)堆疊出來的嗎?
再不濟(jì)，以后你寫代碼的時(shí)候，使用Maps.newHashMapWithExpectedSize(7);的寫法，也可以讓同事和老板眼前一亮。
或者哪一天你碰到一個(gè)面試官問你一些細(xì)節(jié)的時(shí)候，你也能有個(gè)印象，或者某一天你也可以拿這個(gè)出去面試問其他人~!啊哈哈哈。
