摘要：HashMap是近幾年java面試新秀，出場率高達80%以上，如此高頻的出場不得不讓碼農們慎重其事。但依舊拜倒在它的石榴裙下，讓面試場面一度尷尬。它也是開發中最常用到的key-value數據類型。
為什麼HashMap深受面試官青睞，我想有這3個原因：
常用、基礎線程不安全，容易出問題大廠都在問，自己不問顯得面試官沒水平Hash虐我千百遍，我視它為初戀，真的是又愛又恨。愛的是每次面試都有它，可以提前做準備，恨的是準備也白準備，依然被滅。
這次要做回真正的男人，和它做一個了斷。互虐一次，一勞永逸。
我們以天（小）使（白）視角來解剖一下HahsMap。
首先要明白幾個概念
hash值是把任意長度的輸入通過散列算法變換成固定長度的輸出，該輸出就是hash值。java中，hash值就是一個固定長度的int值。補充一點，java的int佔4位，每位8個字節，共32個字節。
hash表存儲hash值的數組就是hash表。
hash函數hash表在存儲hash值的時候需要計算存到哪個index。這個計算規則就是hash函數。我們知道數組的長度是提前定義好的，假如一個數組的長度是4，不斷地給數組添加值，一定會出現多個值放在同一個index上，這就叫hash衝突。如何解決？要麼覆蓋，要麼丟棄。顯然這2種都不太合適。
4種解決hash衝突的常見方法：再哈希法：如果hash出的index已經有值，就再hash，不行繼續hash，直至找到空的index位置，要相信瞎貓總能碰上死耗子。這個辦法最容易想到。但有2個缺點：比較浪費空間，消耗效率。根本原因還是數組的長度是固定不變的，不斷hash找出空的index，可能越界，這時就要創建新數組，而老數組的數據也需要遷移。隨著數組越來越大，消耗不可小覷。get不到，或者說get算法複雜。進是進去了，想出來就沒那麼容易了。開放地址方法：如果hash出的index已經有值，通過算法在它前面或後面的若干位置尋找空位，這個和再hash算法差別不大。建立公共溢出區： 把衝突的hash值放到另外一塊溢出區。鏈式地址法： 把產生hash衝突的hash值以鍊表形式存儲在index位置上。HashMap用的就是該方法。優點是不需要另外開闢新空間，也不會丟失數據，尋址也比較簡單。但是隨著hash鏈越來越長，尋址也是更加耗時。好的hash算法就是要讓鏈儘量短，最好一個index上只有一個值。也就是儘可能地保證散列地址分布均勻，同時要計算簡單。看源碼前的2個準備
1. 複習二進位運算
一次次被虐，主要因為沒有深讀HashMap源碼。而在讀源碼的過程中經常會看到二進位的相關運算。這裡有必要溫習一些HashMap中用到的二進位算法。為了不浪費大家的雙眸，我們以8位二進位來舉例。
& 與運算，2個二進位數對應的位置都為1結果才為1如：10&700001010---10&00000111---7=00000010---2| 或運算：只要有個一個為1，就為1如：10|700001010---10|00000111---7=00001111---15^ 異或：2個二進位數對應的位置不一樣，才為1如：1^700001010---10^00000111---7=00001101---13<<左移 左移一位都相當於乘以2的1次方，左移n位就相當於乘以2的n次方，前提是數字不能溢出。比如8位作業系統中有一個二進位數是0100 0000，左移一位是1000 0000，是原來數的2倍。但是再左移就成了0000 0000，就不是原數的2倍了。2. HashMap常見的面試題
帶著問題看源碼可能不那麼迷茫枯燥。當然還有很多面試題，但只要抓住關鍵的幾點，其他的也就迎刃而解，萬變不離其宗。
HashMap的底層原理是什麼，採用什麼數據結構HashMap容量為什麼必須是2的冪次方HashMap什麼時候需要進行擴容，擴容如何實現HashMap在什麼地方會出現線程不安全，如何解決源碼終於來了，本文默認分析JDK1.8的源碼，因為網上分析1.7的已經很多了，只在必要時用1.7作為對比。
我們宏觀了解下HashMap的數據結構。首先它是一個基於hashtable的map。前面我們說到hashtable是存儲hash值的數組。可知HahsMap最外層是一個數組。這個數組在源碼中的表示是Node<K,V>[] table。如下圖： Node是HashMap的內部類，結構如下：
classNode<K,V>implementsMap.Entry<K,V> {finalinthash;//key的哈希值，用來定位數組索引位置finalKkey;//keyVvalue;//valueNode<K,V>next;//下一個node ........... } 前面我們又提到，HashMap是通過鏈式法解決hash衝突。結合Node的結構，HashMap的結構圖大概是這樣：
HashMap的基本數據結構就是數組+鍊表。當然在1.8以後又引入了紅黑樹，我們先不講，它並不妨礙我們理解HashMap的思想。
除了table屬性（註：table[i]=bucket,包含該位置的所有node），還有幾個屬性需要提前了解：
/*** The default initial capacity - MUST be a power of two.* 數組的初始化容量，必須是2的冪次方，默認16。* 為什麼不直接寫16。鄙人猜測是：可能大師要告訴我們HashMap的容量必須是2的冪次方。* 好比我們給某一緩存設置有效時間是3*60s。而不是直接寫180秒。其實我們強調的是前面的3分鐘。當然這並不重要。*/staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;/*** The number of key-value mappings contained in this map.* 已經儲存的Node<key,value>的數量，包括數組中的和鍊表中的*/transientintsize;/*** The load factor for the hash table.* 負載因子*/finalfloatloadFactor;/*** The load factor used when none specified in constructor.* 負載因子的默認值*/staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;/*** The javadoc description is true upon serialization.* Additionally, if the table array has not been allocated,* this field holds the initial array capacity, or zero signifying DEFAULT_INITIAL_CAPACITY.)* The next size value at which to resize (capacity * load factor).* <p>* 擴容的閥值。當size>threshold（=capacity * load factor）的時候就會擴容**/intthreshold;/*** The bin count threshold for untreeifying a (split) bin during a* resize operation. Should be less than TREEIFY_THRESHOLD, and at* most 6 to mesh with shrinkage detection under removal.* 擴容時，如果bucket的node數量小於UNTREEIFY_THRESHOLD，紅黑樹轉為單向鍊表*/staticfinalintUNTREEIFY_THRESHOLD=6;/*** The bin count threshold for using a tree rather than list for a* bin. Bins are converted to trees when adding an element to a* bin with at least this many nodes. The value must be greater* than 2 and should be at least 8 to mesh with assumptions in* tree removal about conversion back to plain bins upon* shrinkage.* <p>* 鍊表轉紅黑樹的閥值。*/staticfinalintTREEIFY_THRESHOLD=8;HashMap中需要剖析的內容很多，但篇幅有限，讀者耐心有限，鄙人水平有限。下面僅從hash函數、put方法、擴容過程3個最具代表性的點深入展開講解。這3點基本涵蓋了日常使用和面試的所有場面。1.hash函數如何計算index。
32位hash的範圍是-2147483648到2147483648，40多億。只要hash做的好，很難發生碰撞。但是40億的數組內存是放不下的，只能進行壓縮。最簡單的方法就是取模，hash%table.length就能計算出index。我們能想到，大師也想到了。只是大師想的更周全。在1.7中有這麼一個方法
staticintindexFor(inth, intlength) {//jdk1.7的源碼，jdk1.8沒有這個方法，但實現過程一樣returnh& (length-1);}因為length是2的冪次，才有hash &（length-1）等價於hash % length，只是在效率上比取模要高，至於為什麼，大家可以課下推導，或者找相關文章。這也是map容量為什麼必須是2的冪次的一個原因。除了這個原因，此時如果length不是2的冪次會是什麼情況？
1.假如length是一個奇數n，參與hash運算的（n-1）一定是偶數，偶數的最低位一定是0，0和任何數&都為0。所以hash&（n-1）最低位是0，也就是偶數。這樣數組的奇數位就浪費了。舉個最容易理解的例子，假如length=3。參與hash運算的就是3-1=2。現在有一個任意hash值：10101111001001011111111111100111&00000000000000000000000000000010---2=00000000000000000000000000000010---2不管hash值是多少。和2於運算之後，要麼是0，要麼是2。永遠輪不到1。2.假如length是一個非2的冪次的偶數n。n=6現在有一個任意hash值：10101111001001011111111111100111&00000000000000000000000000000101---5=00000000000000000000000000000101---55「101」的中間的「0」和任何數&運算後的結果都是0。意味著index低位第二位永遠是0。此時index永遠不可能是2或3。有些基礎差的同學可能不太理解，如果你知道二進位如何轉成十進位就很好理解。如果不知道，我們列舉出hash值和5「101」做與的所有可能。因為101前面都是0，所以hash對應位置不管是什麼數，&後都為0。我們只關注hash低3位。h000001011111110100101n-1&101&101&101&101&101&101&101=000001001101100100101---二進位=0115445---十進位從結果中可以看出index沒有2和3，n越大空位越多。3.如果length是2的冪次，那length-1的低位全是1。就不會出現永遠為空的位置。比如默認容量16。現在有一個任意hash值：10101111001001011111111111100111&00000000000000000000000000001111---15=00000000000000000000000000000111---7hash高位全部歸零，具體落到哪個角標位，主要取決於hash值的後幾位。這是第二個length是2的冪次的原因：數組各個位置不浪費，雨露均沾。
length的作用已經發揮到了極致。剛才提到hash&（length-1），真正起作用的是hash的低位，它是否均勻決定了整個數組分配是否均勻。不能保證key.hashCode()非常合理，如果hash後幾位一樣，會碰的頭破血流。所以HashMap對它做了進一步優化，讓hash低位更均勻。
/*** Computes key.hashCode() and spreads (XORs) higher bits of hash* to lower. Because the table uses power-of-two masking, sets of* hashes that vary only in bits above the current mask will* always collide. (Among known examples are sets of Float keys* holding consecutive whole numbers in small tables.) So we* apply a transform that spreads the impact of higher bits* downward. There is a tradeoff between speed, utility, and* quality of bit-spreading. Because many common sets of hashes* are already reasonably distributed (so don't benefit from* spreading), and because we use trees to handle large sets of* collisions in bins, we just XOR some shifted bits in the* cheapest possible way to reduce systematic lossage, as well as* to incorporate impact of the highest bits that would otherwise* never be used in index calculations because of table bounds.* 擾動函數*/staticfinalinthash(Objectkey) {inth;return (key==null) ?0 : (h=key.hashCode()) ^ (h>>>16);}首先將hashCode無符號右移16位，然後再做異或。這裡參考了胖哥的知乎回答
java中int是32bit，右移16位正好是一半。這樣就做到了hash高位於低位的混合，以此來提高低位的隨機性。同時也保留了高位的部分特徵。胖哥文中提到的實驗也證明了混合後的hash要比原始hash衝突概率小。但也不能完全避免hash衝突，我們前文提到，好的hash函數不僅要散列均勻，也要保證高效。
如果效率太低，put，get等相關操作時消耗太大則本末倒置。HashMap設計目標是簡潔與高效。
這裡還有一個小問題。為什麼此時高位和低位要做^，而非&或者｜？其實不難想到，&運算計算出來的值會向0靠攏，而|運算計算出來的值會向1靠攏。造成散列不均勻。
總之，不管用什麼方式，最終目的都是散列均勻，效率高。
2. 詳解put方法
/*** Associates the specified value with the specified key in this map.* If the map previously contained a mapping for the key, the old* value is replaced.** @param key key with which the specified value is to be associated* @param value value to be associated with the specified key* @return the previous value associated with <tt>key</tt>, or* <tt>null</tt> if there was no mapping for <tt>key</tt>.* (A <tt>null</tt> return can also indicate that the map* previously associated <tt>null</tt> with <tt>key</tt>.)* <p>*/@OverridepublicVput(Kkey, Vvalue) {//對key.hashCode做hashreturnputVal(hash(key), key, value, false, true); }finalVputVal(inthash, Kkey, Vvalue, booleanonlyIfAbsent,booleanevict) {Node<K, V>[] tab;//暫存tableNode<K, V>p;//tab[i]intn; //tab數組長度inti; //數組下標index//1. table為空，調用resize()新建if ((tab=table) ==null|| (n=tab.length) ==0) {n= (tab=resize()).length; }//2. 計算index值i= (n-1) &hash;//3. 賦值if ((p=tab[i]) ==null) {//如果tab[i]為空，新建一個。tab[i] =newNode(hash, key, value, null); } else {//如果tab[i]上已經有元素，也就是發生了碰撞。Node<K, V>e;Kk;//（1）如果hash和key都相等if (p.hash==hash&& ((k=p.key) ==key|| (key!=null&&key.equals(k)))) {e=p; } elseif (pinstanceofTreeNode) {//判斷該鏈是否為紅黑樹，入樹e= ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value); } else {//單向鍊表遍歷，index相同，key不同for (intbinCount=0; ; ++binCount) {if ((e=p.next) ==null) {//如果next為空，追加到鍊表尾部breakp.next=newNode(hash, key, value, null);//鍊表長度大於8轉換為紅黑樹if (binCount>=TREEIFY_THRESHOLD-1) {treeifyBin(tab, hash); }break; }//如果key已存在，直接 breakif (e.hash==hash&& ((k=e.key) ==key|| (key!=null&&key.equals(k)))) {break; }//繼續遍歷nextp=e; } }// 返回oldValueif (e!=null) {VoldValue=e.value;//put的入參onlyIfAbsent=false，所以!onlyIfAbsent一直成立if (!onlyIfAbsent||oldValue==null) {e.value=value; }returnoldValue; } }++modCount;//4. 超過最大容量限制，擴容if (++size>threshold) {resize(); }returnnull; }整個put流程還是比較清晰簡單的，總體步驟如下：
判斷table是否為空，為空就調用resize()初始化數組。HashMap的構造函數並沒有初始化數組，而是在put方法初始化數組。計算index值判斷p=table[i]是否為空，如果是空，直接new Node放到該bucket（table[i]對應的鍊表）。If不為空如果p的hash和key與參數中的hash、key都相等，把p賦值給e。不新建Node。如果p是紅黑樹，把新Node加入樹中。如果是單向列表，則遍歷，把新Node插到bucket末端，如果bucket長度大於8，鍊表轉換成紅黑樹。如果size>threshol就擴容。3. resize擴容機制
一般情況下，當size > threshold的時候就需要擴容，我們知道java的數組是無法真正擴容的。只能新建一個更大的數組來替代之前的老數組，新數組的容量是上一個數組容量的2倍，同樣可以保證是2的冪次。
注意擴容的目的並不是讓數組容納更多的量（理論上鍊表可以無限長），而是為了提高HashMap的查找、插入效率。
下面是擴容源碼。
/*** Initializes or doubles table size. If null, allocates in* accord with initial capacity target held in field threshold.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.* 初始化或把table的size擴大2倍.* 如果是null，就是需要初始化，在put的方法我們見過。初始化做的就是初始capacity和對應的threshold* 否則，老table中的元素在向新數組的遷移中，元素要麼落在新數組相同的index下。要麼落在capacity+index下。* @return the table*/finalNode<K, V>[] resize() {Node<K, V>[] oldTab=table;//創建一個oldTab數組用於保存之前的數組intoldCap= (oldTab==null) ?0 : oldTab.length;//獲取原來數組的長度intoldThr=threshold;//原來數組擴容的臨界值intnewCap, newThr=0;if (oldCap>0) {//如果原來的數組長度大於最大值(2^30)，不再擴容if (oldCap>=MAXIMUM_CAPACITY) {threshold=Integer.MAX_VALUE;returnoldTab; }//新的數組容量為原來的2倍elseif ((newCap=oldCap<<1) <MAXIMUM_CAPACITY&&oldCap>=DEFAULT_INITIAL_CAPACITY) {newThr=oldThr<<1; // double threshold } } elseif (oldThr>0) // initial capacity was placed in threshold {newCap=oldThr; } else {//oldThr == 0,初始化cap和thresholdnewCap=DEFAULT_INITIAL_CAPACITY;//新數組初始容量設置為默認值newThr= (int) (DEFAULT_LOAD_FACTOR*DEFAULT_INITIAL_CAPACITY);//計算默認容量下的閾值 }// 計算新的resize上限if (newThr==0) {floatft= (float) newCap*loadFactor;//ft為臨時變量，用於判斷閾值的合法性newThr= (newCap<MAXIMUM_CAPACITY&&ft< (float) MAXIMUM_CAPACITY? (int) ft : Integer.MAX_VALUE);//計算新的閾值 }threshold=newThr;//改變threshold值為新的閾值Node<K, V>[] newTab= (Node<K, V>[]) newNode[newCap];table=newTab;//擴容，深度複製 bucketif (oldTab!=null) {for (intj=0; j<oldCap; ++j) {Node<K, V>e;if ((e=oldTab[j]) !=null) {oldTab[j] =null;//釋放老數組元素if (e.next==null) {//將e也就是oldTab[j]放入newTab中e.hash & (newCap - 1)的位置newTab[e.hash& (newCap-1)] =e; } elseif (einstanceofTreeNode) {//紅黑樹處理 ((TreeNode<K, V>) e).split(null, newTab, j, oldCap); } else { // preserve order//lo=low hi=highNode<K, V>loHead=null, loTail=null;Node<K, V>hiHead=null, hiTail=null;Node<K, V>next;//遍歷整個單向鍊表，元素新index，要麼是原來index，要麼是（index+oldCap）do {next=e.next;/** e.hash & oldCap == 0 ，node放在原來的index上。why？1. 由於oldCap是2的冪次。它的二進位表示是1個1後面有n個0。比如16的二機制是0001 0000（8位為例）2. 要想 hash & oldCap == 0，那hash二進位中與0001 0000中「1：從低位數第5位」的對應位置必須是0，其他位置是什麼無所謂。所以hash格式是 ***0 ****（從低位數第5位是0）。為了更加直觀，我們按照推演出來的hash規則，隨機給hash取個值1110 1010，滿足0001 0000 & 1110 1010 = 0。3. 我們知道table的index =（oldCap-1）& hash。（oldCap - 1） & hash= 15 & hash= 0000 1111 & 1110 1010= 0000 1010 = 10 node在原數組的index為10。4. 現在resize，newCap=oldCap*2。index =（2*oldCap-1）& hash=（2*16-1）&hash= 0001 1111 & 1110 1010= 0000 1010 = 10擴容後node在新數組的下標也是10。其實可以明顯看到，index就是hash後4位的值。因為這4位的（length-1）都為1，其餘位置都為0。5. 所以(e.hash & oldCap) == 0 的時候 node在老數組中的位置與在新數組中的位置一致。此時hash從低位數第5位是0。下面else源碼中的hash此位置為1。*/if ((e.hash&oldCap) ==0) {if (loTail==null) {loHead=e; } else {loTail.next=e; }loTail=e; }/*** else 原索引+oldCap* 1. 假設oldCap依然是16,hash = 1111 1010。* 上面已經計算過此hash原始index為10。* 2. 擴容後* index =（2oldCap-1）& hash。* = 31 & hash* = 0001 1111 & 1111 1010* = 0001 1010 = 26（oldIndex+oldCap）* 我們細品一下 newIndex為什麼等於（oldIndex+oldCap），其實也很簡單。* oldIndex就是hash後4位的值。這個我們上面已經推演過。* 本次2*length-1的後四位也都是1，所以newIndex值的後4位也是hash後4位。* 本次不同的是從低位數第5位，hash此位是1，2*length-1的此位也是1，&運算以後此位置為1.* 所以結果就是1後面跟上hash的後4位，就是11010，也就是10000 +0 1010。** 總結，newIndex的值取決於hash從低位數第5位的值。* 如果這個位置是0，index不變。如果是1，index=index+oldCap。* 通過簡單的&運算就能確定index，無需像jdk1.7那樣重新計算index值。這也是為什麼HashMap容量是2的 * 冪次的一個原因。* 有心的同學可能注意到了，index主要取決與hash的最後幾位，如果hash算法做的不好，就會加大hash碰 * 撞。所以this.hash()「擾動函數」做了些優化。* */else {if (hiTail==null) {hiHead=e; } else {hiTail.next=e; }hiTail=e; } } while ((e=next) !=null);// 原索引放到bucket裡，尾插法if (loTail!=null) {loTail.next=null;newTab[j] =loHead; }// 原索引+oldCap放到bucket裡，尾插法if (hiTail!=null) {hiTail.next=null;newTab[j+oldCap] =hiHead; } } } } }returnnewTab; }線程安全
HashMap是線程不安全的。多線程情況下會出現很多問題，比較常見的問題就是丟失數據。當有一個線程改動了散列表的結構，都有可能造成另一個線程的操作失敗，主要集中在put和resize方法中。更多問題需要大家去探究，只是探究，別以身試法。多線程環境下建議用線程安全的ConcurrentHashMap或者synchronizedMap。
比如1.8在put方法中
finalVputVal(inthash, Kkey, Vvalue, booleanonlyIfAbsent,booleanevict) { ...省略部分源碼..//，向同一個位置存入元素，會有值覆蓋的問題，導致數丟失。if ((p=tab[i]) ==null) {tab[i] =newNode(hash, key, value, null); } else { ...省略部分源碼.. } 1.8在擴容時：
// 給同一個數組的相同位置賦值，會有數據覆蓋的風險if (loTail!=null) {loTail.next=null;//將原始索引位的數據遷移到新數組1newTab[j] =loHead; }if (hiTail!=null) {hiTail.next=null;//將原始索引位的數據遷移到新數組2newTab[j+oldCap] =hiHead;}再見面試題&小結
文章開始提到的幾個問題應該已經有了答案。
HashMap的底層原理是什麼，採用什麼數據結構基於HashTable，最外層是一個Node[]，每個Node可能是單向鍊表，或者紅黑樹（列表長度大於8時轉紅黑樹）。HashMap容量為什麼必須是2的冪次方在計算index時，hash&（length-1）等價於hash % length，但要比直接取模效率高。範圍當然也是0至length-1。還是hash&（length-1），當length是2的冪次時，數組各個位置不浪費，能做到雨露均沾。其他數都有可能造成空間浪費。在擴容時，無需重新hash再計算index，通過和hash&cap就能確定元素在擴容後數組的位置。&要比重新hash效率高的多。HashMap什麼時候需要進行擴容，擴容如何實現當size>threshold（capacity * load factor）的時候擴容。簡單的說，1.7採用的是頭插法擴容，1.8採用的是尾插法進行擴容。具體源碼比較簡單，大家可以下來自己看，文中也給出了關鍵代碼的註解。多線程時，頭插法可能出現的問題是死循環。尾插法的問題是丟失數據。當然其他問題還有待大家發現，如果已經發現，不妨在發表在留言區，大家一起討論，集思廣益。HashMap在什麼地方會出現線程不安全，如何解決由於沒做同步，線程不安全隨處可見。但最致命的是在put和resize發生數據結構變更的地方。解決方案就是用ConcurrentHashMap或者synchronizedMap替代。本文參考
本文參考了諸多大神的文章，站在巨人的肩膀上希望能看的更高，進步更大。
由於本人才疏學淺，難免會有若干謬誤，歡迎指正。
有問題在留言區談論，如果覺得「還可以」，期望點讚轉發。
JDK1.7&JDK1.8 源碼。Java Code Geeks，HashMap performance improvements in Java 8，2014。深入理解 hashcode() 和 HashMap 中的hash 算法JDK 源碼中 HashMap 的 hash 方法原理是什麼？Java 8系列之重新認識HashMap