如何選擇HashMap的默認(rèn)容量，針對(duì)這個(gè)問(wèn)題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問(wèn)題的小伙伴找到更簡(jiǎn)單易行的方法。

創(chuàng)新互聯(lián)是一家專業(yè)提供壽光企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計(jì)、成都網(wǎng)站設(shè)計(jì)、H5場(chǎng)景定制、小程序制作等業(yè)務(wù)。10年已為壽光眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站設(shè)計(jì)公司優(yōu)惠進(jìn)行中。集合是Java開(kāi)發(fā)日常開(kāi)發(fā)中經(jīng)常會(huì)使用到的，而作為一種典型的K-V結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)，HashMap對(duì)于Java開(kāi)發(fā)者一定不陌生。在日常開(kāi)發(fā)中，我們經(jīng)常會(huì)像如下方式以下創(chuàng)建一個(gè)HashMap：

Map<String, String> map = new HashMap<String, String>();

但是，大家有沒(méi)有想過(guò)，上面的代碼中，我們并沒(méi)有給HashMap指定容量，那么，這時(shí)候一個(gè)新創(chuàng)建的HashMap的默認(rèn)容量是多少呢？為什么呢？本文就來(lái)分析下這個(gè)問(wèn)題。

什么是容量

在Java中，保存數(shù)據(jù)有兩種比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)：數(shù)組和鏈表。數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難；而鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。HashMap就是將數(shù)組和鏈表組合在一起，發(fā)揮了兩者的優(yōu)勢(shì)，我們可以將其理解為鏈表的數(shù)組。在HashMap中，有兩個(gè)比較容易混淆的關(guān)鍵字段：size和capacity ，這其中capacity就是Map的容量，而size我們稱之為Map中的元素個(gè)數(shù)。簡(jiǎn)單打個(gè)比方你就更容易理解了：HashMap就是一個(gè)“桶”，那么容量（capacity）就是這個(gè)桶當(dāng)前最多可以裝多少元素，而元素個(gè)數(shù)（size）表示這個(gè)桶已經(jīng)裝了多少元素。

如以下代碼：

Map<String, String> map = new HashMap<String, String>();

map.put("hollis", "hollischuang");



Class<?> mapType = map.getClass();

Method capacity = mapType.getDeclaredMethod("capacity");

capacity.setAccessible(true);

System.out.println("capacity : " + capacity.invoke(map));



Field size = mapType.getDeclaredField("size");

size.setAccessible(true);

System.out.println("size : " + size.get(map));

輸出結(jié)果：

capacity : 16、size : 1

上面我們定義了一個(gè)新的HashMap，并向其中put了一個(gè)元素，然后通過(guò)反射的方式打印capacity和size，其容量是16，已經(jīng)存放的元素個(gè)數(shù)是1。通過(guò)前面的例子，我們發(fā)現(xiàn)了，當(dāng)我們創(chuàng)建一個(gè)HashMap的時(shí)候，如果沒(méi)有指定其容量，那么會(huì)得到一個(gè)默認(rèn)容量為16的Map，那么，這個(gè)容量是怎么來(lái)的呢？又為什么是這個(gè)數(shù)字呢？

容量與哈希

要想講清楚這個(gè)默認(rèn)容量的緣由，我們要首先要知道這個(gè)容量有什么用？我們知道，容量就是一個(gè)HashMap中"桶"的個(gè)數(shù)，那么，當(dāng)我們想要往一個(gè)HashMap中put一個(gè)元素的時(shí)候，需要通過(guò)一定的算法計(jì)算出應(yīng)該把他放到哪個(gè)桶中，這個(gè)過(guò)程就叫做哈希（hash），對(duì)應(yīng)的就是HashMap中的hash方法。

我們知道，hash方法的功能是根據(jù)Key來(lái)定位這個(gè)K-V在鏈表數(shù)組中的位置的。也就是hash方法的輸入應(yīng)該是個(gè)Object類型的Key，輸出應(yīng)該是個(gè)int類型的數(shù)組下標(biāo)。如果讓你設(shè)計(jì)這個(gè)方法，你會(huì)怎么做？其實(shí)簡(jiǎn)單，我們只要調(diào)用Object對(duì)象的hashCode()方法，該方法會(huì)返回一個(gè)整數(shù)，然后用這個(gè)數(shù)對(duì)HashMap的容量進(jìn)行取模就行了。如果真的是這么簡(jiǎn)單的話，那HashMap的容量設(shè)置就會(huì)簡(jiǎn)單很多了，但是考慮到效率等問(wèn)題，HashMap的hash方法實(shí)現(xiàn)還是有一定的復(fù)雜的。

hash的實(shí)現(xiàn)

接下來(lái)就介紹下HashMap中hash方法的實(shí)現(xiàn)原理。(下面部分內(nèi)容參考自我的文章：全網(wǎng)把Map中的hash()分析的最透徹的文章，別無(wú)二家。PS：網(wǎng)上的關(guān)于HashMap的hash方法的分析的文章，很多都是在我這篇文章的基礎(chǔ)上"衍生"過(guò)來(lái)的。）具體實(shí)現(xiàn)上，由兩個(gè)方法int hash(Object k)和int indexFor(int h, int length)來(lái)實(shí)現(xiàn)。

hash ：該方法主要是將Object轉(zhuǎn)換成一個(gè)整型。indexFor ：該方法主要是將hash生成的整型轉(zhuǎn)換成鏈表數(shù)組中的下標(biāo)。

為了聚焦本文的重點(diǎn)，我們只來(lái)看一下indexFor方法。我們先來(lái)看下Java 7（Java8中雖然沒(méi)有這樣一個(gè)單獨(dú)的方法，但是查詢下標(biāo)的算法也是和Java 7一樣的）中該實(shí)現(xiàn)細(xì)節(jié)：

static int indexFor(int h, int length) {

    return h & (length-1);

}

indexFor方法其實(shí)主要是將hashcode換成鏈表數(shù)組中的下標(biāo)。其中的兩個(gè)參數(shù)h表示元素的hashcode值，length表示HashMap的容量。那么return h & (length-1) 是什么意思呢？其實(shí)，他就是取模。Java之所有使用位運(yùn)算(&)來(lái)代替取模運(yùn)算(%)，最主要的考慮就是效率。

位運(yùn)算(&)效率要比代替取模運(yùn)算(%)高很多，主要原因是位運(yùn)算直接對(duì)內(nèi)存數(shù)據(jù)進(jìn)行操作，不需要轉(zhuǎn)成十進(jìn)制，因此處理速度非常快。

那么，為什么可以使用位運(yùn)算(&)來(lái)實(shí)現(xiàn)取模運(yùn)算(%)呢？這實(shí)現(xiàn)的原理如下：

X % 2^n = X & (2^n – 1)

假設(shè)n為3，則2^3 = 8，表示成2進(jìn)制就是1000。2^3 -1 = 7 ，即0111。此時(shí)X & (2^3 – 1) 就相當(dāng)于取X的2進(jìn)制的最后三位數(shù)。從2進(jìn)制角度來(lái)看，X / 8相當(dāng)于 X >> 3，即把X右移3位，此時(shí)得到了X / 8的商，而被移掉的部分(后三位)，則是X % 8，也就是余數(shù)。上面的解釋不知道你有沒(méi)有看懂，沒(méi)看懂的話其實(shí)也沒(méi)關(guān)系，你只需要記住這個(gè)技巧就可以了。或者你可以找?guī)讉€(gè)例子試一下。

6 % 8 = 6 ，6 & 7 = 6



10 & 8 = 2 ，10 & 7 = 2

運(yùn)算過(guò)程如下如：

所以，return h & (length-1);只要保證length的長(zhǎng)度是2^n 的話，就可以實(shí)現(xiàn)取模運(yùn)算了。

所以，因?yàn)槲贿\(yùn)算直接對(duì)內(nèi)存數(shù)據(jù)進(jìn)行操作，不需要轉(zhuǎn)成十進(jìn)制，所以位運(yùn)算要比取模運(yùn)算的效率更高，所以HashMap在計(jì)算元素要存放在數(shù)組中的index的時(shí)候，使用位運(yùn)算代替了取模運(yùn)算。之所以可以做等價(jià)代替，前提是要求HashMap的容量一定要是2^n 。那么，既然是2^n ，為啥一定要是16呢？為什么不能是4、8或者32呢？關(guān)于這個(gè)默認(rèn)容量的選擇，JDK并沒(méi)有給出官方解釋，筆者也沒(méi)有在網(wǎng)上找到關(guān)于這個(gè)任何有價(jià)值的資料。（如果哪位有相關(guān)的權(quán)威資料或者想法，可以留言交流）根據(jù)作者的推斷，這應(yīng)該就是個(gè)經(jīng)驗(yàn)值（Experience Value），既然一定要設(shè)置一個(gè)默認(rèn)的2^n 作為初始值，那么就需要在效率和內(nèi)存使用上做一個(gè)權(quán)衡。這個(gè)值既不能太小，也不能太大。太小了就有可能頻繁發(fā)生擴(kuò)容，影響效率。太大了又浪費(fèi)空間，不劃算。所以，16就作為一個(gè)經(jīng)驗(yàn)值被采用了。

在JDK 8中，關(guān)于默認(rèn)容量的定義為：static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 ，其故意把16寫成1<<4，就是提醒開(kāi)發(fā)者，這個(gè)地方要是2的冪。值得玩味的是：注釋中的 aka 16 也是1.8中新增的，

那么，接下來(lái)我們?cè)賮?lái)談?wù)劊琀ashMap是如何保證其容量一定可以是2^n 的呢？如果用戶自己設(shè)置了的話又會(huì)怎么樣呢？關(guān)于這部分，HashMap在兩個(gè)可能改變其容量的地方都做了兼容處理，分別是指定容量初始化時(shí)以及擴(kuò)容時(shí)。

指定容量初始化

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

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

看一下JDK是如何找到比傳入的指定值大的第一個(gè)2的冪的：

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;

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

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

Step 1，5->7Step 2，7->8Step 1，9->15Step 2，15->16Step 1，19->31Step 2，31->32

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

n |= n >>> 1;

n |= n >>> 2;

n |= n >>> 4;

n |= n >>> 8;

n |= n >>> 16;

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

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

Step 2 比較簡(jiǎn)單，就是做一下極限值的判斷，然后把Step 1得到的數(shù)值+1。Step 1 怎么理解呢？其實(shí)是對(duì)一個(gè)二進(jìn)制數(shù)依次向右移位，然后與原值取或。其目的對(duì)于一個(gè)數(shù)字的二進(jìn)制，從第一個(gè)不為0的位開(kāi)始，把后面的所有位都設(shè)置成1。隨便拿一個(gè)二進(jìn)制數(shù)，套一遍上面的公式就發(fā)現(xiàn)其目的了：

1100 1100 1100 >>>1 = 0110 0110 0110

1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110

1110 1110 1110 >>>2 = 0011 1011 1011

1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111

1111 1111 1111 >>>4 = 1111 1111 1111

1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111

通過(guò)幾次無(wú)符號(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的冪。但是還有一種特殊情況套用以上公式不行，這些數(shù)字就是2的冪自身。如果數(shù)字4套用公式的話。得到的會(huì)是 8，不過(guò)其實(shí)這個(gè)問(wèn)題也被解決了，具體驗(yàn)證辦法及JDK的解決方案見(jiàn)全網(wǎng)把Map中的hash()分析的最透徹的文章，別無(wú)二家。這里就不再展開(kāi)了。總之，HashMap根據(jù)用戶傳入的初始化容量，利用無(wú)符號(hào)右移和按位或運(yùn)算等方式計(jì)算出第一個(gè)大于該數(shù)的2的冪。

擴(kuò)容

除了初始化的時(shí)候會(huì)指定HashMap的容量，在進(jìn)行擴(kuò)容的時(shí)候，其容量也可能會(huì)改變。HashMap有擴(kuò)容機(jī)制，就是當(dāng)達(dá)到擴(kuò)容條件時(shí)會(huì)進(jìn)行擴(kuò)容。HashMap的擴(kuò)容條件就是當(dāng)HashMap中的元素個(gè)數(shù)（size）超過(guò)臨界值（threshold）時(shí)就會(huì)自動(dòng)擴(kuò)容。在HashMap中，threshold = loadFactor * capacity。loadFactor是裝載因子，表示HashMap滿的程度，默認(rèn)值為0.75f，設(shè)置成0.75有一個(gè)好處，那就是0.75正好是3/4，而capacity又是2的冪。所以，兩個(gè)數(shù)的乘積都是整數(shù)。對(duì)于一個(gè)默認(rèn)的HashMap來(lái)說(shuō)，默認(rèn)情況下，當(dāng)其size大于12(16*0.75)時(shí)就會(huì)觸發(fā)擴(kuò)容。下面是HashMap中的擴(kuò)容方法(resize)中的一段：

if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&

                 oldCap >= DEFAULT_INITIAL_CAPACITY)

    newThr = oldThr << 1; // double threshold

}

從上面代碼可以看出，擴(kuò)容后的table大小變?yōu)樵瓉?lái)的兩倍，這一步執(zhí)行之后，就會(huì)進(jìn)行擴(kuò)容后table的調(diào)整，這部分非本文重點(diǎn)，省略。可見(jiàn)，當(dāng)HashMap中的元素個(gè)數(shù)（size）超過(guò)臨界值（threshold）時(shí)就會(huì)自動(dòng)擴(kuò)容，擴(kuò)容成原容量的2倍，即從16擴(kuò)容到32、64、128 …所以，通過(guò)保證初始化容量均為2的冪，并且擴(kuò)容時(shí)也是擴(kuò)容到之前容量的2倍，所以，保證了HashMap的容量永遠(yuǎn)都是2的冪。

HashMap作為一種數(shù)據(jù)結(jié)構(gòu)，元素在put的過(guò)程中需要進(jìn)行hash運(yùn)算，目的是計(jì)算出該元素存放在hashMap中的具體位置。hash運(yùn)算的過(guò)程其實(shí)就是對(duì)目標(biāo)元素的Key進(jìn)行hashcode，再對(duì)Map的容量進(jìn)行取模，而JDK 的工程師為了提升取模的效率，使用位運(yùn)算代替了取模運(yùn)算，這就要求Map的容量一定得是2的冪。而作為默認(rèn)容量，太大和太小都不合適，所以16就作為一個(gè)比較合適的經(jīng)驗(yàn)值被采用了。為了保證任何情況下Map的容量都是2的冪，HashMap在兩個(gè)地方都做了限制。首先是，如果用戶制定了初始容量，那么HashMap會(huì)計(jì)算出比該數(shù)大的第一個(gè)2的冪作為初始容量。另外，在擴(kuò)容的時(shí)候，也是進(jìn)行成倍的擴(kuò)容，即4變成8，8變成16。

關(guān)于如何選擇HashMap的默認(rèn)容量問(wèn)題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒(méi)有解開(kāi)，可以關(guān)注創(chuàng)新互聯(lián)-成都網(wǎng)站建設(shè)公司行業(yè)資訊頻道了解更多相關(guān)知識(shí)。

分享題目：如何選擇HashMap的默認(rèn)容量-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://chinadenli.net/article48/ccgdep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營(yíng)銷、標(biāo)簽優(yōu)化、虛擬主機(jī)、網(wǎng)站導(dǎo)航、網(wǎng)站內(nèi)鏈、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)