在日常開發(fā)中，我們經(jīng)常會像如下方式以下創(chuàng)建一個HashMap： Map<String, String> map = new HashMap<String, String>(); 但是，大家有沒有想過，上面的代碼中，我們并沒有給HashMap指定容量，那么，這時候一個新創(chuàng)建的HashMap的默認容量是多少呢？為什么呢？ 什么是容量 在Java中，保存數(shù)據(jù)有兩種比較簡單的數(shù)據(jù)結構：數(shù)組和鏈表。數(shù)組的特點是：尋址容易，插入和刪除困難；而鏈表的特點是：尋址困難，插入和刪除容易。HashMap就是將數(shù)組和鏈表組合在一起，發(fā)揮了兩者的優(yōu)勢，我們可以將其理解為鏈表的數(shù)組。 在HashMap中，有兩個比較容易混淆的關鍵字段：size和capacity ，這其中capacity就是Map的容量，而size我們稱之為Map中的元素個數(shù)。 簡單打個比方你就更容易理解了：HashMap就是一個“桶”，那么容量（capacity）就是這個桶當前最多可以裝多少元素，而元素個數(shù)（size）表示這個桶已經(jīng)裝了多少元素。 Map<String, String> map = new HashMap<String, String>(); 上面我們定義了一個新的HashMap，并向其中put了一個元素，然后通過反射的方式打印capacity和size，其容量是16，已經(jīng)存放的元素個數(shù)是1。 通過前面的例子，我們發(fā)現(xiàn)了，當我們創(chuàng)建一個HashMap的時候，如果沒有指定其容量，那么會得到一個默認容量為16的Map，那么，這個容量是怎么來的呢？又為什么是這個數(shù)字呢？ 容量與哈希 要想講清楚這個默認容量的緣由，我們要首先要知道這個容量有什么用？ 我們知道，容量就是一個HashMap中"桶"的個數(shù)，那么，當我們想要往一個HashMap中put一個元素的時候，需要通過一定的算法計算出應該把他放到哪個桶中，這個過程就叫做哈希（hash），對應的就是HashMap中的hash方法。 我們知道，hash方法的功能是根據(jù)Key來定位這個K-V在鏈表數(shù)組中的位置的。也就是hash方法的輸入應該是個Object類型的Key，輸出應該是個int類型的數(shù)組下標。如果讓你設計這個方法，你會怎么做？ 其實簡單，我們只要調(diào)用Object對象的hashCode()方法，該方法會返回一個整數(shù)，然后用這個數(shù)對HashMap的容量進行取模就行了。 如果真的是這么簡單的話，那HashMap的容量設置就會簡單很多了，但是考慮到效率等問題，HashMap的hash方法實現(xiàn)還是有一定的復雜的。 hash的實現(xiàn) 接下來就介紹下HashMap中hash方法的實現(xiàn)原理。(下面部分內(nèi)容參考自我的文章：全網(wǎng)把Map中的hash()分析的最透徹的文章，別無二家。PS：網(wǎng)上的關于HashMap的hash方法的分析的文章，很多都是在我這篇文章的基礎上"衍生"過來的。） 具體實現(xiàn)上，由兩個方法int hash(Object k)和int indexFor(int h, int length)來實現(xiàn)。 hash ：該方法主要是將Object轉(zhuǎn)換成一個整型。 indexFor ：該方法主要是將hash生成的整型轉(zhuǎn)換成鏈表數(shù)組中的下標。 為了聚焦本文的重點，我們只來看一下indexFor方法。我們先來看下Java 7（Java8中雖然沒有這樣一個單獨的方法，但是查詢下標的算法也是和Java 7一樣的）中該實現(xiàn)細節(jié)： static int indexFor(int h, int length) { indexFor方法其實主要是將hashcode換成鏈表數(shù)組中的下標。其中的兩個參數(shù)h表示元素的hashcode值，length表示HashMap的容量。那么return h & (length-1) 是什么意思呢？ 其實，他就是取模。Java之所有使用位運算(&)來代替取模運算(%)，最主要的考慮就是效率。 位運算(&)效率要比代替取模運算(%)高很多，主要原因是位運算直接對內(nèi)存數(shù)據(jù)進行操作，不需要轉(zhuǎn)成十進制，因此處理速度非?？臁?/section> 那么，為什么可以使用位運算(&)來實現(xiàn)取模運算(%)呢？這實現(xiàn)的原理如下： 假設n為3，則2^3 = 8，表示成2進制就是1000。2^3 -1 = 7 ，即0111。 此時X & (2^3 – 1) 就相當于取X的2進制的最后三位數(shù)。 從2進制角度來看，X / 8相當于 X >> 3，即把X右移3位，此時得到了X / 8的商，而被移掉的部分(后三位)，則是X % 8，也就是余數(shù)。 上面的解釋不知道你有沒有看懂，沒看懂的話其實也沒關系，你只需要記住這個技巧就可以了。或者你可以找?guī)讉€例子試一下。 6 % 8 = 6 ，6 & 7 = 6 運算過程如下如：
所以，return h & (length-1);只要保證length的長度是2^n 的話，就可以實現(xiàn)取模運算了。
所以，因為位運算直接對內(nèi)存數(shù)據(jù)進行操作，不需要轉(zhuǎn)成十進制，所以位運算要比取模運算的效率更高，所以HashMap在計算元素要存放在數(shù)組中的index的時候，使用位運算代替了取模運算。之所以可以做等價代替，前提是要求HashMap的容量一定要是2^n 。 那么，既然是2^n ，為啥一定要是16呢？為什么不能是4、8或者32呢？ 關于這個默認容量的選擇，JDK并沒有給出官方解釋，筆者也沒有在網(wǎng)上找到關于這個任何有價值的資料。（如果哪位有相關的權威資料或者想法，可以留言交流） 根據(jù)作者的推斷，這應該就是個經(jīng)驗值（Experience Value），既然一定要設置一個默認的2^n 作為初始值，那么就需要在效率和內(nèi)存使用上做一個權衡。這個值既不能太小，也不能太大。 太小了就有可能頻繁發(fā)生擴容，影響效率。太大了又浪費空間，不劃算。 在JDK 8中，關于默認容量的定義為：static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 ，其故意把16寫成1<<4，就是提醒開發(fā)者，這個地方要是2的冪。值得玩味的是：注釋中的 aka 16 也是1.8中新增的， 那么，接下來我們再來談談，HashMap是如何保證其容量一定可以是2^n 的呢？如果用戶自己設置了的話又會怎么樣呢？ 關于這部分，HashMap在兩個可能改變其容量的地方都做了兼容處理，分別是指定容量初始化時以及擴容時。 指定容量初始化 當我們通過HashMap(int initialCapacity)設置初始容量的時候，HashMap并不一定會直接采用我們傳入的數(shù)值，而是經(jīng)過計算，得到一個新值，目的是提高hash的效率。(1->1、3->4、7->8、9->16) 在JDK 1.7和JDK 1.8中，HashMap初始化這個容量的時機不同。JDK 1.8中，在調(diào)用HashMap的構造函數(shù)定義HashMap的時候，就會進行容量的設定。而在JDK 1.7中，要等到第一次put操作時才進行這一操作。 看一下JDK是如何找到比傳入的指定值大的第一個2的冪的： int n = cap - 1; 上面的算法目的挺簡單，就是：根據(jù)用戶傳入的容量值（代碼中的cap），通過計算，得到第一個比他大的2的冪并返回。 請關注上面的幾個例子中，藍色字體部分的變化情況，或許你會發(fā)現(xiàn)些規(guī)律。5->8、9->16、19->32、37->64都是主要經(jīng)過了兩個階段。 n |= n >>> 1; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; Step 2 比較簡單，就是做一下極限值的判斷，然后把Step 1得到的數(shù)值+1。 Step 1 怎么理解呢？其實是對一個二進制數(shù)依次向右移位，然后與原值取或。其目的對于一個數(shù)字的二進制，從第一個不為0的位開始，把后面的所有位都設置成1。 隨便拿一個二進制數(shù)，套一遍上面的公式就發(fā)現(xiàn)其目的了： 1100 1100 1100 >>>1 = 0110 0110 0110 通過幾次無符號右移和按位或運算，我們把1100 1100 1100轉(zhuǎn)換成了1111 1111 1111 ，再把1111 1111 1111加1，就得到了1 0000 0000 0000，這就是大于1100 1100 1100的第一個2的冪。 好了，我們現(xiàn)在解釋清楚了Step 1和Step 2的代碼。就是可以把一個數(shù)轉(zhuǎn)化成第一個比他自身大的2的冪。 但是還有一種特殊情況套用以上公式不行，這些數(shù)字就是2的冪自身。如果數(shù)字4套用公式的話。得到的會是 8，不過其實這個問題也被解決了，具體驗證辦法及JDK的解決方案見全網(wǎng)把Map中的hash()分析的最透徹的文章，別無二家。這里就不再展開了。 總之，HashMap根據(jù)用戶傳入的初始化容量，利用無符號右移和按位或運算等方式計算出第一個大于該數(shù)的2的冪。 擴容 除了初始化的時候會指定HashMap的容量，在進行擴容的時候，其容量也可能會改變。 HashMap有擴容機制，就是當達到擴容條件時會進行擴容。HashMap的擴容條件就是當HashMap中的元素個數(shù)（size）超過臨界值（threshold）時就會自動擴容。 在HashMap中，threshold = loadFactor * capacity。 loadFactor是裝載因子，表示HashMap滿的程度，默認值為0.75f，設置成0.75有一個好處，那就是0.75正好是3/4，而capacity又是2的冪。所以，兩個數(shù)的乘積都是整數(shù)。 對于一個默認的HashMap來說，默認情況下，當其size大于12(16*0.75)時就會觸發(fā)擴容。 下面是HashMap中的擴容方法(resize)中的一段： if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 從上面代碼可以看出，擴容后的table大小變?yōu)樵瓉淼膬杀?，這一步執(zhí)行之后，就會進行擴容后table的調(diào)整，這部分非本文重點，省略。 可見，當HashMap中的元素個數(shù)（size）超過臨界值（threshold）時就會自動擴容，擴容成原容量的2倍，即從16擴容到32、64、128 … 所以，通過保證初始化容量均為2的冪，并且擴容時也是擴容到之前容量的2倍，所以，保證了HashMap的容量永遠都是2的冪。 HashMap作為一種數(shù)據(jù)結構，元素在put的過程中需要進行hash運算，目的是計算出該元素存放在hashMap中的具體位置。hash運算的過程其實就是對目標元素的Key進行hashcode，再對Map的容量進行取模，而JDK 的工程師為了提升取模的效率，使用位運算代替了取模運算，這就要求Map的容量一定得是2的冪。而作為默認容量，太大和太小都不合適，所以16就作為一個比較合適的經(jīng)驗值被采用了。為了保證任何情況下Map的容量都是2的冪，HashMap在兩個地方都做了限制。首先是，如果用戶制定了初始容量，那么HashMap會計算出比該數(shù)大的第一個2的冪作為初始容量。另外，在擴容的時候，也是進行成倍的擴容，即4變成8，8變成16。 關于如何選擇HashMap的默認容量問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關注億速云行業(yè)資訊頻道了解更多相關知識。 
