集合是Java開發日常開發中經常會使用到的，而作爲一種典型的K-V結構的數據結構，HashMap對于Java開發者一定不陌生。
在日常開發中，我們經常會像如下方式以下創建一個HashMap：
Map<String, String> map = new HashMap<String, String>();
但是，大家有沒有想過，上面的代碼中，我們並沒有給HashMap指定容量，那麽，這時候一個新創建的HashMap的默認容量是多少呢？爲什麽呢？
本文就來分析下這個問題。
什麽是容量
在Java中，保存數據有兩種比較簡單的數據結構：數組和鏈表。數組的特點是：尋址容易，插入和刪除困難；而鏈表的特點是：尋址困難，插入和刪除容易。HashMap就是將數組和鏈表組合在一起，發揮了兩者的優勢，我們可以將其理解爲鏈表的數組。
在HashMap中，有兩個比較容易混淆的關鍵字段：size和capacity ，這其中capacity就是Map的容量，而size我們稱之爲Map中的元素個數。
簡單打個比方你就更容易理解了：HashMap就是一個“桶”，那麽容量（capacity）就是這個桶當前最多可以裝多少元素，而元素個數（size）表示這個桶已經裝了多少元素。
我們知道，hash方法的功能是根據Key來定位這個K-V在鏈表數組中的位置的。也就是hash方法的輸入應該是個Object類型的Key，輸出應該是個int類型的數組下標。如果讓你設計這個方法，你會怎麽做？
其實簡單，我們只要調用Object對象的hashCode()方法，該方法會返回一個整數，然後用這個數對HashMap的容量進行取模就行了。
如果真的是這麽簡單的話，那HashMap的容量設置就會簡單很多了，但是考慮到效率等問題，HashMap的hash方法實現還是有一定的複雜的。
hash的實現
接下來就介紹下HashMap中hash方法的實現原理。(下面部分內容參考自我的文章：全網把Map中的hash()分析的最透徹的文章，別無二家。PS：網上的關于HashMap的hash方法的分析的文章，很多都是在我這篇文章的基礎上”衍生”過來的。）
具體實現上，由兩個方法int hash(Object k)和int indexFor(int h, int length)來實現。
hash ：該方法主要是將Object轉換成一個整型。
indexFor ：該方法主要是將hash生成的整型轉換成鏈表數組中的下標。
爲了聚焦本文的重點，我們只來看一下indexFor方法。我們先來看下Java 7（Java8中雖然沒有這樣一個單獨的方法，但是查詢下標的算法也是和Java 7一樣的）中該實現細節：
static int indexFor(int h, int length) { return h & (length-1); }
indexFor方法其實主要是將hashcode換成鏈表數組中的下標。其中的兩個參數h表示元素的hashcode值，length表示HashMap的容量。那麽return h & (length-1) 是什麽意思呢？
其實，他就是取模。Java之所有使用位運算(&)來代替取模運算(%)，最主要的考慮就是效率。
位運算(&)效率要比代替取模運算(%)高很多，主要原因是位運算直接對內存數據進行操作，不需要轉成十進制，因此處理速度非常快。
那麽，爲什麽可以使用位運算(&)來實現取模運算(%)呢？這實現的原理如下：
X % 2^n = X & (2^n – 1)
假設n爲3，則2^3 = 8，表示成2進制就是1000。2^3 -1 = 7 ，即0111。
此時X & (2^3 – 1) 就相當于取X的2進制的最後三位數。
從2進制角度來看，X / 8相當于 X >> 3，即把X右移3位，此時得到了X / 8的商，而被移掉的部分(後三位)，則是X % 8，也就是余數。
上面的解釋不知道你有沒有看懂，沒看懂的話其實也沒關系，你只需要記住這個技巧就可以了。或者你可以找幾個例子試一下。
6 % 8 = 6 ，6 & 7 = 6
10 & 8 = 2 ，10 & 7 = 2
運算過程如下如：
請關注上面的幾個例子中，藍色字體部分的變化情況，或許你會發現些規律。5->8、9->16、19->32、37->64都是主要經過了兩個階段。
Step 1，5->7
Step 2，7->8
Step 1，9->15
Step 2，15->16
Step 1，19->31
Step 2，31->32
對應到以上代碼中，Step1：
n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16;
對應到以上代碼中，Step2：
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
Step 2 比較簡單，就是做一下極限值的判斷，然後把Step 1得到的數值+1。
Step 1 怎麽理解呢？其實是對一個二進制數依次向右移位，然後與原值取或。其目的對于一個數字的二進制，從第一個不爲0的位開始，把後面的所有位都設置成1。
隨便拿一個二進制數，套一遍上面的公式就發現其目的了：
1100 1100 1100 >>>1 = 0110 0110 0110 1100 1100 1100 | 0110 0110 0110 = 1110 1110 11101110 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
通過幾次無符號右移和按位或運算，我們把1100 1100 1100轉換成了1111 1111 1111 ，再把1111 1111 1111加1，就得到了1 0000 0000 0000，這就是大于1100 1100 1100的第一個2的冪。
好了，我們現在解釋清楚了Step 1和Step 2的代碼。就是可以把一個數轉化成第一個比他自身大的2的冪。
但是還有一種特殊情況套用以上公式不行，這些數字就是2的冪自身。如果數字4套用公式的話。得到的會是 8，不過其實這個問題也被解決了，具體驗證辦法及JDK的解決方案見全網把Map中的hash()分析的最透徹的文章，別無二家。這裏就不再展開了。
總之，HashMap根據用戶傳入的初始化容量，利用無符號右移和按位或運算等方式計算出第一個大于該數的2的冪。
擴容
除了初始化的時候會指定HashMap的容量，在進行擴容的時候，其容量也可能會改變。
HashMap有擴容機制，就是當達到擴容條件時會進行擴容。HashMap的擴容條件就是當HashMap中的元素個數（size）超過臨界值（threshold）時就會自動擴容。
在HashMap中，threshold = loadFactor * capacity。
loadFactor是裝載因子，表示HashMap滿的程度，默認值爲0.75f，設置成0.75有一個好處，那就是0.75正好是3/4，而capacity又是2的冪。所以，兩個數的乘積都是整數。
對于一個默認的HashMap來說，默認情況下，當其size大于12(16*0.75)時就會觸發擴容。
下面是HashMap中的擴容方法(resize)中的一段：
if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold }
從上面代碼可以看出，擴容後的table大小變爲原來的兩倍，這一步執行之後，就會進行擴容後table的調整，這部分非本文重點，省略。
可見，當HashMap中的元素個數（size）超過臨界值（threshold）時就會自動擴容，擴容成原容量的2倍，即從16擴容到32、64、128 …
所以，通過保證初始化容量均爲2的冪，並且擴容時也是擴容到之前容量的2倍，所以，保證了HashMap的容量永遠都是2的冪。
總結
HashMap作爲一種數據結構，元素在put的過程中需要進行hash運算，目的是計算出該元素存放在hashMap中的具體位置。
hash運算的過程其實就是對目標元素的Key進行hashcode，再對Map的容量進行取模，而JDK 的工程師爲了提升取模的效率，使用位運算代替了取模運算，這就要求Map的容量一定得是2的冪。
而作爲默認容量，太大和太小都不合適，所以16就作爲一個比較合適的經驗值被采用了。
爲了保證任何情況下Map的容量都是2的冪，HashMap在兩個地方都做了限制。
首先是，如果用戶制定了初始容量，那麽HashMap會計算出比該數大的第一個2的冪作爲初始容量。
另外，在擴容的時候，也是進行成倍的擴容，即4變成8，8變成16。
本文，通過分析爲什麽HashMap的默認容量是16，我們深入HashMap的原理，分析了下背後的原理，從代碼中我們可以發現，JDK 的工程師把各種位運算運用到了極致，想盡各種辦法優化效率。值得我們學習！
最後，留一個思考題，既然HashMap並不會直接接收用戶傳入的初始容量，那麽爲什麽《阿裏巴巴Java開發手冊》還是建議開發者在創建HashMap的時候制定一個初始容量呢？這個容量設置成多少合適呢？爲什麽？
關于作者：Hollis，一個對Coding有著獨特追求的人，現任阿裏巴巴技術專家，個人技術博主，技術文章全網閱讀量數千萬，《程序員的三門課》聯合作者。
分享自：https://maimai.cn/article/detail?fid=1386914852&efid=I9gMBxWE2I5ota4RpogAQw&use_rn=1