深度解析HashMap高頻面試及底層實現(xiàn)架構(gòu)！

HashMap高頻面試題
1，Map接口和List接口是什么關(guān)系？

2、Map有哪些常用的實現(xiàn)類？

3、請闡述HashMap的put過程？

4、鏈表中是按照怎樣的順序存放數(shù)據(jù)的？

5、Hash(key)方法是如何實現(xiàn)的？

6、為什么HashMap的容量一直是2的倍數(shù)？

8、HashMap是如何擴容的？

9、擴容后元素怎么存放的？

10、JDK1.7和JDK1.8對HashMap的實現(xiàn)比較

Map接口大家應(yīng)該都聽說過吧？它是在Java中對鍵值對進行存儲的一種常用方式，同樣其中的HashMap我相信大家應(yīng)該也不會陌生，一說到HashMap，我想稍微知道點的小伙伴應(yīng)該都說是：**這是存儲鍵值對的，存儲方式是數(shù)組加鏈表的形式。**但是其中真正是如何進行存儲以及它的底層架構(gòu)是如何實現(xiàn)的，這些你有了解嗎？

可能很多小伙伴該說了，我只需要知道它怎么使用就可以了，不需要知道它的底層實現(xiàn)，但其實恰恰相反，只知道它怎么使用是完全不夠的，而且在Java開發(fā)的面試之中，HashMap底層實現(xiàn)的提問和考察已經(jīng)是司空見慣的了。所以今天我就來和大家分析一下Map接口的詳細使用以及HashMap的底層是如何實現(xiàn)的？

**小伙伴們慢慢往下看，看完絕對會讓你收獲滿滿的！

1，Map接口和List接口是什么關(guān)系？

對于這個問題，如果非要說這兩個接口之間存在怎樣的關(guān)系的話，**那無非就只有一個，就都是集合。存放數(shù)據(jù)的。**在其他上面，Map接口和List接口的聯(lián)系其實并不大，為什么這么說？

**先來看List接口，**關(guān)于List接口我在之前也和大家提到過，**它是繼承于Collection接口的，是Collection接口的子接口，只是用于對數(shù)據(jù)的單列存儲。**繼承關(guān)系如下圖：

而Map接口是一個頂層接口，下面包含了很多不同的實現(xiàn)類，它是 用于對鍵值對（key:value）進行存儲的 ，繼承關(guān)系如下圖：

所以Map接口和List接口的關(guān)系和使用不要混淆了！

2、Map有哪些常用的實現(xiàn)類？

上面關(guān)于Map的繼承結(jié)構(gòu)我們已經(jīng)了解了，我們也看了其中很多不同的實現(xiàn)類，這些類很多也是我們比較熟悉的，比如HashMap、TreeMap以及HashTable。在面試的時候，面試官往往就還會問，Map接口下有哪些常用的實現(xiàn)類以及它們的作用，那么接下來我們就來對這幾個接口進行簡單的介紹和分析一下，

**HashMap:**上面也說了，**HashMap的底層實現(xiàn)是數(shù)組+鏈表+紅黑樹的形式的， 同時它的 數(shù)組的默認初始容量是16、擴容因子為0.75，每次采用2倍的擴容。**也就是說，每當我們數(shù)組中的存儲容量達到75%的時候，就需要對數(shù)組容量進行2倍的擴容。

**HashTable:**HashTable接口是線程安全，但是很早之前有使用，現(xiàn)在幾乎屬于一個遺留類了， 在開發(fā)中不建議使用。

**ConcurrentHashMap:**這是現(xiàn)階段使用使用比較多的一種線程安全的Map實現(xiàn)類。 在1.7以前使用的是分段鎖機制實現(xiàn)的線程安全的。但是在1.8以后使用synchronized關(guān)鍵字實現(xiàn)的線程安全。

其中關(guān)于HashMap的考察和提問在面試中是最頻繁的，這也是在日常開發(fā)中最應(yīng)該深入理解和掌握的。所以接下來就主要和大家詳細分析一下HashMap的實現(xiàn)原理以及面試中的常考問題。

3、請闡述HashMap的put過程？

我們知道HaahMap使用put的方式進行數(shù)據(jù)的存儲，其中有兩個參數(shù)，分別是key和value，那么關(guān)于這個鍵值對是如何進行儲存的呢？我們接下來進行分析一下。

在HashMap中使用的是數(shù)組+鏈表的實現(xiàn)方式， 在HashMap的上層使用數(shù)組的形式對“相同”的key進行存儲，下層對相應(yīng)的key和value使用鏈表的形式進行鏈接和存儲。

注意：這里所說的相同并不一定是key的數(shù)值相同，而是存在某種相同的特征， 具體是哪種特征罵我們繼續(xù)往下看！

HashMap將將要存儲的值按照key計算其對應(yīng)的數(shù)組下標，如果對應(yīng)的數(shù)組下標的位置上是沒有元素的，那么就將存儲的元素存放上去，但是如果該位置上已經(jīng)存在元素了，那么這就需要用到我們上面所說的鏈表存儲了，將數(shù)據(jù)按照鏈表的存儲順序依次向下存儲就可以了。這就是put的簡單過程，存儲結(jié)果如下：

但是我們有時候存儲的數(shù)據(jù)會很多，那么如果一直使用鏈表的形式進行數(shù)據(jù)的存儲的話就或造成我們的鏈表的長度非常大，這樣無論在進行刪除還是在進行插入操作都是十分麻煩的，因此對于這種情況應(yīng)該怎么辦呢？

**這里就涉及到了一個鏈表中數(shù)據(jù)存儲時，進行“樹化”和“鏈化”的一個過程，**那么什么是“樹化”和“鏈化”呢？

當我們在對鍵值對進行存儲的時候，如果我們在同一個數(shù)組下標下存儲的數(shù)據(jù)過多的話，就會造成我們的鏈表長度過長，導(dǎo)致進行刪除和插入操作比較麻煩，所以在java中規(guī)定，**當鏈表長度大于8時，我們會對鏈表進行“樹化”操作，****將其轉(zhuǎn)換成一顆紅黑樹（一種二叉樹，左邊節(jié)點的值小于根節(jié)點，右邊節(jié)點的值大于根節(jié)點），**這樣我們在對元素進行查找時，就類似于進行二分查找了，這樣的查找效率就會大大增加。

但是當我們進行刪除操作，將其中的某些節(jié)點刪除了之后，鏈表的長度不再大于8了，這個時候怎么辦？難道就要趕緊將紅黑樹轉(zhuǎn)化為鏈表的形式嗎？其實并不是， 只有當鏈表的長度小于6的時候，我們才會將紅黑樹重新轉(zhuǎn)化為鏈表，這個過程就叫做“鏈化”。
過程圖示如下：

那么為什么要在長度8的時候進行“樹化”，而在長度小于6的時候才進行“鏈化”呢？為什么不直接在長度小于8的時候就進行“鏈化”？
**主要原因是因為：**當刪除一個元素，鏈表長度小于8的時候直接進行“鏈化”，而再增加一個元素，長度又等于8的時候，又要進行“樹化”，這樣反復(fù)的進行“鏈化”和“樹化”操作特別的消耗時間，而且也比較麻煩。所以程序就規(guī)定，只有當當鏈表長度大于等于8的時候才進行“樹化”，而長度小于6的時候才進行“鏈化”， 其中關(guān)于8樹化、6鏈化這兩個閾值希望大家牢記！

4、鏈表中是按照怎樣的順序存放數(shù)據(jù)的？

我們現(xiàn)在已經(jīng)知道了HashMap中的元素是如何存放的，但是有時候面試官可能還會問我們，在HashMap中，向鏈表中存儲元素是在頭結(jié)點存儲的還是在尾節(jié)點存儲的？

這個我們需要知道，對于HashMap中鏈表元素的存儲。
在JDK1.7以及前是在頭結(jié)點插入的，在JDK1.8之后是在尾節(jié)點插入的。

5、Hash(key)方法是如何實現(xiàn)的？

我們現(xiàn)在已經(jīng)知道了HashMap中的元素是如何存儲的了，那么現(xiàn)在就是如何應(yīng)該根據(jù)key值進行相應(yīng)的數(shù)組下標的計算呢？

我們知道HashMap的初始容量是16位，那么對于初始的16個數(shù)據(jù)位，如果將數(shù)據(jù)按照key的值進行計算存儲，一般最簡單的方法就是根據(jù)key值獲取到一個int值，方法是：
int hashCode = key.hashCode()
然后對獲取到的hashCode與16進行取余運算，
hashCode % 16 = 0~15
這樣得到的永遠都是0—15的下標。這也是最最原始的計算hash(key)的方法。

**但是在實際情況下，這種方法計算的hash(key)并不是最優(yōu)，**存放到數(shù)組中的元素并不是最分散的，而且在計算機中進行余運算其實是非常不方便的、

**所以為了計算結(jié)果盡可能的離散，現(xiàn)在計算數(shù)組下標最常用的方法是：**先根據(jù)key的值計算到一個hashCode，將hashCode的高18位二進制和低18位二進制進行異或運算，得到的結(jié)果再與當前數(shù)組長度減一進行與運算。最終得到一個數(shù)組下標，過程如下：
int hashCode = key.hashCode()
int hash = hash(key) = key.hashCode()的高16位^低16位&(n-1) 其中n是當前數(shù)組長度
同時在這里要提醒一點。
在JDK1.7和JDK1.8的時候?qū)ash(key)的計算是略有不同的
JDK1.8時，計算hash(key)進行了兩次擾動
JDK1.7時，計算hash(key)進行了九次擾動，分別是四次位運算和五次異或運算
其中擾動可能理解為運算次數(shù)
以上就是Hash(key)方法的實現(xiàn)過程。

6、為什么HashMap的容量一直是2的倍數(shù)？

HashMap的容量之所以一直是2的倍數(shù)， 其實是與上面所說的hash(key)算法有關(guān)的，

原因是只有參與hash(key)的算法的（n-1）的值盡可能都是1的時候，得到的值才是離散的。假如我們當前的數(shù)組長度是16，二進制表示是10000，n-1之后是01111，使得n-1的值盡可能都是1，對于其他是2的倍數(shù)的值減1之后得到值也是這樣的。

所以只有當數(shù)組的容量長度是2的倍數(shù)的時候，計算得到的hash(key)的值才有可能是相對離散的，

7、Hash沖突如何解決？

什么是Hash沖突？就是當我計算到某一個數(shù)組下標的時候，該下標上已經(jīng)存放元素了，這就叫Hash沖突，很顯然，如果我們計算數(shù)組下標的算法不夠優(yōu)秀的時候，很容易將存儲的數(shù)據(jù)積累到同一個下標上面，造成過多的Hash沖突。
那么如何解決hash沖突？
最應(yīng)該解決的其實就是讓存儲的key計算得到的數(shù)組下標盡可能的離散，也就是要求hash(key)盡可能的優(yōu)化，數(shù)組長度是2的倍數(shù)。這也就是Hash沖突的主要解決方法。
具體可以查看下面HashMap關(guān)鍵部分的底層源碼：
Hash(key)的底層實現(xiàn)

/*** Applies a supplemental hash function to a given hashCode, which* defends against poor quality hash functions. This is critical* because HashMap uses power-of-two length hash tables, that* otherwise encounter collisions for hashCodes that do not differ* in lower bits. Note: Null keys always map to hash 0, thus index 0.*/static int hash(int h) {// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}

put(key,value)方法的底層實現(xiàn)

/*** 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>.)*/public V put(K key, V value) {if (key == null)return putForNullKey(value);int hash = hash(key.hashCode());int i = indexFor(hash, table.length);for (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}modCount++;addEntry(hash, key, value, i);return null;}

8、HashMap是如何擴容的？

我們在上面說到了HashMap的數(shù)組的初始容量是16，但是很顯然16個存儲位是顯然不夠的，那么HashMap應(yīng)該如何擴容呢？
在這里需要用到一個參數(shù)叫“擴容因子”，在HashMap中“擴容因子”的大小是0.75，
**我們上面也提到過，對于初始長度為16的數(shù)組，當其中存儲的數(shù)據(jù)長度等于16*0.75=12時。就會對數(shù)組元素進行擴容，擴容量是原來數(shù)組容量的2倍，**也就是當前是15話，再擴容就是擴容32個數(shù)據(jù)位。

9、擴容后元素怎么存放的？

我們知道HashMap的數(shù)組在進行擴容之后，數(shù)組長度是增加的，那么這個時候，后面新擴容的部分就是空的。但是這個時候我們就應(yīng)該讓后面的數(shù)據(jù)位空著嗎？顯然是不可能的，這樣會造成內(nèi)存的很大浪費。

因此在HashMap的數(shù)組擴容之后，原先HashMap數(shù)組中存放的數(shù)據(jù)元素會進行重新的位置分配，重新將元素在新數(shù)組中進行存儲。以充分利用數(shù)組空間。

10、JDK1.7和JDK1.8對HashMap的實現(xiàn)比較

在JDK1.7和JDK1.8中對HashMap的實現(xiàn)是略有不同的，最后我們根據(jù)上面的講解對JDK1.7和JDK1.8在HashMap的實現(xiàn)中的不同進行分析比較。
（1）、底層數(shù)據(jù)結(jié)構(gòu)不同
在HashMap的put過程中，JDK1.7時是沒有紅黑樹這一概念的，直接是進行的鏈表存儲， 在JDK1.8之后才引入了紅黑樹的概念，來優(yōu)化存儲和查找。

（2）、鏈表的插入方式不同
在HashMap向鏈表中插入元素的過程中，JDK1.7時是在表頭節(jié)點插入的，JDK1.8之后是在尾節(jié)點插入的。

（3）、Hash(key)的計算方式不同
在Hash(key)的計算中，JDK1.7進行了九次擾亂，分別是四次位運算和五次異或運算，JDK1.8之后只進行了兩次擾動。

（4）、擴容后數(shù)存儲位置的計算方式不同
在擴容后對存儲數(shù)據(jù)的重新排列上，JDK1.7是將所有數(shù)據(jù)的位置打亂，然后根據(jù)hash(key)進行重新的計算， 而在JDK1.8之后是對原來的數(shù)據(jù)下標進行了兩次for循環(huán)。計算出新下標位置只能是在原下標位置或者在原下標位置加上原容量位置。

好了，關(guān)于Map接口和HashMap的底層實現(xiàn)的過程，以及在面試中參考的核心問題就和大家分析到這里！

記得關(guān)注Remi醬呀~

總結(jié)

以上是生活随笔為你收集整理的深度解析HashMap高频面试及底层实现架构！的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。