HashMap在面試的時候最容易被問到的問題，估計面試有80%的幾率會被問到，如果每次當你的面試官讓你說下HashMap時，你只能說出它是以鍵值對的形式存儲數據時，那麼你的這場面試基本上已經Over了，除非你在別的方面有特別突出的地方。

為什麼這個知識會被問得這麼頻繁，為什麼每位面試官都對它情有獨鍾，主要還是在於HashMap是一個比較具有代表性的數據存儲結構，它的內部原理和設計思維在很多技術場景都有異曲同工的效果。從另外一個方面來講，這個問題基本是在探測你的技術基礎扎不紮實，如果一個最常用的基礎知識點你都沒有深入的去學習和了解過，那很大可能在別的技術方面也不會有什麼深度。

好了現在開始進入我們的正題，當然一些最最基礎的知識我們就跳過了，我們只抓重點，瞭解HashMap時你只要抓住這幾個知識點就基本上可以征服你的面試官了，過於細節的東西也沒必要深究，我們主要是學習它的思維和設計，當然不排除你有這種深入研究的愛好和多餘的時間。

知識點一：Hash組成結構

這個問題我想大部分人還是都有了解的，HashMap結構是由「數組」和「鏈表」組成，其結構類似於下圖的形式（圖是百度找的）。

通過上面的圖我們可以直觀的看出來，我們要查找一個數據時，首先要找到數組對應下標的頭部元素，而這個頭部元素就是我們的鏈表的頭，然後我們再根據鏈表的頭部元素往下一個個匹配直到找到我們的想要的數據，或者匹配完也沒找到對應的數據時就返回一個null。

當然你知道HashMap的結構之後，你還需要問自己一個問題，那就是HashMap為什麼要用數組和鏈表來組成的數據結構？ 這纔是面試官想要聽你說的。

• 為什麼要使用數組和鏈表？

兩個字「性能」，HashMap是一個集添加、刪除、查詢都具備高性能的優點於一身。首先我們看它的結構組成之一「數組」。

數組的優勢

因為每個數組都是有下標的，我們可以通過演算法做查找優化，所以數組查找數據的速度非常快，如果沒有數組下標，那我們只能一個個的遍歷匹配，有多少數據匹配多少數據，那肯定賊慢。

數組的劣勢

但是數組也有它的劣勢，那就是數組插入數據非常的慢，因為每次插入數據的時候需要把後面的數據都重新挪下位置，就像下圖描述的這樣。

現在我們知道了，數組主要是查找數據快，但插入數據卻需要挪動數據，當數組的長度越長，那麼插入數據的時候，需要挪動的元素就越多，所以效率非常低。也正因為數組插入數據的效率低，所以這裡就使用到了另外一個數據結構「鏈表」。

鏈表的優勢

鏈表一個顯著的優勢就是插入數據快，鏈表不會像數組一樣記錄下標的值，但是鏈表的每個元素自己都會記錄下一個元素的位置。就像我們排隊一樣，我們只需要記得站在我前面是誰就行， 我並不需要去記住我是隊伍的第幾個。

這樣的好處就是，如果往鏈表中間插入一條數據時，比如在A->B->D>-E 鏈表中，如果在B節點和D節點之間插入C ，那麼我只需要修改B節點保存的自己後面一個的引用，然後把C節點後面一個節點的引用指向D即可，其他的節點都不需要做任何的修改，不論這個鏈表長度如何。

鏈表的劣勢

鏈表的劣勢也很明顯，就是鏈表非常不便於查找數據，因為它沒有像數組一樣記錄元素的下標，所以每次查找一個元素就只能遍歷整個鏈表去匹配。很顯然這種查找方式很粗魯。

• 總結

因為HashMap添加數據、修改數據的操作都比較頻繁，所以必須要保證查找元素的效率的同時也要保證插入元素的效率，在查找數據的時候充分利用數組的優勢，定位到數據在哪個下標的鏈表裡。在插入數據的時候充分利用鏈表的優勢，每次插入數據時，把插入的數據放在鏈表的第一個節點，其他的節點不需要做任何修改。最終綜合兩種數據結構的優勢提升整體性能。

HashMap如何PUT一個數據的?

通過上面的HashMap的結構圖，我想你已經有了一個大概的模型了，現在我們繼續深入瞭解HashMap是怎樣把一個數據添加進去的，put數據的時候會涉及到多個知識點，我們再一一說明。

知識點二：HashMap初始化容量機制和擴容機制

• 初始化容量

如果我們進行put數據的時候，首先得初始化一個數組纔行，而數組創建是需要指定一個長度的，這裡當我們沒指定數組長度的時候，HashMap會默認給我們初始化一個默認長度為16的數組。

關於這個初始化的操作可以查看源碼中的resize()方法，此方法不僅會在初始化容量的時候用到，同時在擴容的時候也會用到，在這個方法中，有一個常量DEFAULT_INITIAL_CAPACITY控制著HashMap的初始化容量。

• 擴容機制

當我們使用數組的時候必須指定一個數組的長度，當我們數據越來越多的時候，就需要對數組進行擴容了， 進行擴容的時候會有幾個問題是需要我們思考的：

（1）當數據到達多少時進行擴容？

這裡通過源碼我們可以知道我們是否擴容的決定性因素是DEFAULT_LOAD_FACTOR負載因子這個常量上，它的值為0.75。

那麼為什麼負載因子要設置成0.75呢，這個是經過了科學測試的，不能設置得太小我想大家都能理解，這個值設置太小會導致HashMap空間利用率不高，擴容的頻率也會更高，擴容的時候需要把數據重新計算哈希排列，這樣會影響性能。

設置成0.75為了減少哈希衝突，當我們通過科學的測試後，發現當數據量超過數組容量的0.75時，產生hash衝突的幾率會很高，因為hash衝突的數據會放到同一個鏈表，這樣會加長鏈表的長度，同樣也會影響HashMap的性能。

（2）每次擴容的大小如何決定？

從上面我們知道初始化的容量是16，當我們需要進行擴容的時候都是對原來的容量增加一倍的長度，這裡主要是保證擴容後的長度是2的N次冪。至於這裡為什麼要保證這種機制，後面我們在key是如何被分配到數組的某一個位置時候結合說明。

（3）最大容量是多少？

我們同樣在源碼裡面看到一個MAXIMUM_CAPACITY的常量，這個值換算出來為1073741824，當我們的容量達到這個值時，HashMap就不再進行擴容了。

• 總結

這裡主要涉及到的知識點就是HashMap初始化容量的大小16，以及這個大小和後面的擴容機制有什麼關係，這裡主要是為了讓HashMap的容量大小為2的N次冪（詳細理解為什麼要這麼做請看下一個知識點），然後負載因子為什麼這麼設置，設置成0.75是為了減少擴容的頻率，更科學合理的利用空間之餘又盡量避免產生哈希衝突。

知識點三：如何定位一個key會存儲到數組的哪個位置？

現在我們已經得到了一個長度為16的數組，那麼我們如何定位一個Key存儲到數組的哪個位置？因為現在我們的數組長度是16，那麼我們有一個硬性要求就是通過一種方式把Key的存放位置定位到0-15下標之間。

• 第一步

首先我們要把我們的Key通過hashCode()方法得到一個數字，比如說我們Key 為「name」得到的hashCode為3373707。

String key="name";
int hashCode=key.hashCode();

• 第二步

然後我們需要對這個哈希數和數組的長度進行一個運算，得到一個1-15的數字。這我們可以使用hashCode 對我們的數組總長度16 進行取餘來得到一個1-15的數字（不過這裡HashMap中是使用的另外一種方式達到同樣的效果，但是為了方便理解，另外一種演算法稍後進行說明）

我們使用取餘方式將3373707 % 16 =11 ，最後得到Key為」name」數據會存儲到數組下標為11的位置，最後我們可以把數據存儲到下標為11的鏈表裡面去，如果鏈表裡面有相同的Key則替換，沒有重複的則追加到鏈表的尾部。

• 比取餘效率更高的元素下標定位方式

好了我想根據上面演示大家都已經理解了，如何根據hashCode來決定分配到哪個數組下標了，那麼我們下面就來看HashMap 使用的另外一種更高效的數組下標定位的演算法，我們看源碼中是使用的什麼演算法。

首先解讀下上面的代碼：

1、獲得HashMap的容量，也就是我們的數組長度。

2、把數組長度-1 然後與哈希code進行位與運算。

這裡我們首先預習一下位與運算規則

兩個數都轉為二進位，然後從高位開始比較，如果兩個數都為1則為1，否則為0。

現在按照我們的hashCode 和HashMap進行一次運算3373707 & (16-1) ，運算過程如下圖

最後我們發現通過位與運算出來的結果居然和我們用取餘的方式得出的結果是一致的，為了更加確認我們的猜想，我們看看在HashMap進行擴容後，或者用不同的key來進行取餘和位與運算出來的結果是否一致。

• 總結

經過試驗我們可以做一個總結，因為在HashMap的容量為 2的N次冪時，我們使用 HashCode % HashMap容量 與 HashCode &（HashMap容量 -1） 計算方式得到的運算結果是一樣的，而我們把容量改成其他數字就達不到這樣的效果了，所以HashMap的擴容機制必須是2的N次冪，因為位與運算的速度要遠高於取餘的方式，所以HashMap最終採用了這種演算法模式來決定一個key 會分配到哪個數組下標的位置去。

知識點四：在put數據的時候如何減少我們的哈希衝突？

這裡的減少哈希衝突其實就是讓我們的Key能合理均勻的分佈到我們數組的各個下標裡面，避免我們的元素都被集中分配到一個數組下標下面，這樣會使我們的數組不能合理的利用起來，也會降低我們的查詢效率，如果運氣不好元素分佈可能就和下圖一樣。

上圖就是當我們的不同的key產生哈希衝突時會被分配到同一個數組下面，這樣的數據會讓我們在get數據時需要做一些額外的檢查來判斷節點是否是我們需要的那個，從而影響整個HashMap的性能，所以我們需要一套更科學的方式盡量減少哈希碰撞。 我們從源碼中找到了這麼一段代碼。

這段代碼意思是把HashCode 與HashCode無符號右移16位的值進行異或處理，這個值纔是我們真正用於數組定位的HashCode值，那麼為什麼要進行這樣一個處理呢，不直接使用key.hashCoide()不就得了嗎。

這裡為了方便理解，我們換一個例子來說明一下這個演算法的意圖，比如：如果有兩個人，他們分別具備身高、年齡、性別、髮型指標；如果想最大化的區分兩個人的差異性，那麼我們肯定把不同維度的指標都進行匹配，因為多一個維度的指標就有可能出現差異性，身高年齡相同的很多，但是身高年齡髮型相同的幾率就會少很多，而這裡其實就是在HashCode上加一個維度的比較那麼產生哈希衝突的幾率就越少。

我們看HashMap用來定位數組位置的計算HashCode &（HashMap容量 -1），觀察這個過程我們就不難發現為什麼要加這個處理邏輯了。

我們通過上面的圖可以發現，我們在計算出HashCode與數組長度進行運算時，其實我們只用到了HashCode的一小部分數據參與了運算，那麼根據我們經驗得知，肯定是參與匹配的維度越多，那麼就越難出現哈希衝突，這HashMap中把HashCode 與HashCode無符號右移16位的值進行異或處理，正是出於想把其他沒有使用到的數據也合理的利用起來參與到運算中，從而達到減少哈希衝突的結果。

• 總結

多一個維度的比較就能減少重複，HashMap為了把HashCode充分的利用到數組位置計算中，從而達到減少哈希衝突，所以使用了上面的演算法，目的就是為了讓HashCode更多的數字參與到Key的位置計算中來。

知識點五：鏈表過長怎麼辦？

通過上面的知識我們知道，HashMap已經很努力的想辦法減少哈希衝突了，但是數組的長度終歸是有限的，這樣就必然造成一部分數據會分配到同一個數組下面，像下面的圖一樣，既難看，又影響我們的查詢效率。

遇到這種情況也沒辦法，必須得想個法子優化，要不然這麼長的鏈表，匹配數據的時候要一個個去比較，肯定會賊慢，所以HashMap把這個鏈表結構轉換成紅黑樹，這樣通過樹結構來來優化查詢的演算法，提高查詢的性能。

那麼什麼時候HashMap 會觸發鏈錶轉換成紅黑樹的操作呢，還有當紅黑樹的數據少於多少的時候又會轉回鏈表呢，這裡我們也可以從HashMap源碼中找到答案。

當進行put數據的時候，鏈表長度大於static final int TREEIFY_THRESHOLD = 8;

這個長度-1的時候就會進行鏈錶轉紅黑樹的操作。

因為我們的HashMap會進行擴容，擴容後我們的元素又可能會分配到別的數組小標裡面去，所以我們紅黑樹的節點也會減少，而當紅黑樹的節點數量減少到一定程度的時候，紅黑樹又會轉換成鏈表，而這個值是由static final int NTREEIFY_THRESHOLD = 6;來設定的，當紅黑樹的節點小於等於6的時候會完成轉換鏈表的操作，這個我們在resize()方法中有調用split()方法，從源碼中可以看到進行紅黑樹轉鏈表的操作。

• 總結

因為數組長度有限的，所以無法避免哈希衝突造成鏈表數據過多，當我們鏈表數據過長的時候會進行一些優化，把鏈錶轉換為紅黑樹優化查詢效率，當鏈表長度大於等於7的時候，進行鏈錶轉紅黑樹，當鏈表長度小於等於6的時候又會把紅黑樹還原成鏈表。

補充：HashMap get數據時是如何查找對應數據的？

其實我們明白了HashMap如何進行put數據了之後，後面如何查詢、修改和刪除數據其實都很簡單了，這裡作為補充簡單了走一下get數據的流程，修改和刪除整體流程和查找流程差不多隻是操作不同就不再另作說明。

get數據的流程：

1、先計算出key哈希值。

2、通過哈希值定位到Key存在哪個數組下標。

3、找到後看數組下標裡面有沒有節點。

4、有節點的話區分節點數據是紅黑樹還是鏈表，然後分別使用對應數據結構的查找方法。

5、根據查找的key和節點裡面存的Key 值判斷兩個key是不是equas() ，equas則返回對應的節點，否則繼續匹配下一個節點，直到匹配成功返回節點，或者沒有節點配後返回null;

推薦閱讀：