面試造飛機系列：用心整理的HashMap面試題，以后都不用擔(dān)心了
來自：非科班的科班
本文思維導(dǎo)圖
HashMap簡介
HashMap 是很常用的一種集合框架，其底層實現(xiàn)方式在 JDK 1.7和 JDK 1.8中卻有很大區(qū)別。
HashMap 是用來存儲數(shù)據(jù)的，它底層在JDK 1.7是數(shù)組+鏈表實現(xiàn)的，而JDK 1.8是使用數(shù)組+鏈表+紅黑樹實現(xiàn)，通過對 key 進行哈希計算等操作后得到數(shù)組下標，把 value 等信息存放在鏈表或紅黑樹存在此位置。
如果兩個不同的 key 運算后獲取的數(shù)組下標一致，就出現(xiàn)了哈希沖突。數(shù)組默認長度是16，如果實際數(shù)組長度超過一定的值，就會進行擴容。
HashMap的面試不管小廠還是大廠都是高頻問點，特別是大廠一定會深究底層，采用持續(xù)的追問，知道你懷疑人生，在Java7和Java8中對HashMap的數(shù)據(jù)結(jié)構(gòu)進行了很大的優(yōu)化。
今天這篇文章就以HashMap的高頻問點為主，層層的剖析HasMap的底層實現(xiàn)，話不多說，直接進入正題。
問點一：你了解HashMap的底層數(shù)據(jù)結(jié)構(gòu)嗎？
對于HashMap的底層數(shù)據(jù)結(jié)構(gòu)在Java7和Java8中的實現(xiàn)是不同的，在Java7中是采用數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)進行實現(xiàn)，而在Java8中是采用數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的。
說時遲那時快，剛話說完，從兜里拿出筆和紙，啪地一聲放在桌子上畫了起來，許久之后，出現(xiàn)了兩幅jdk7和jdk8的HashMap的內(nèi)部結(jié)構(gòu)圖：
上圖是
jdk7內(nèi)部結(jié)構(gòu)圖，以
Entry<K,V>[]數(shù)組作為
哈希桶，每個哈希桶的后面又可以連著一條
單向鏈表，在鏈表中以
k，v的形式存儲數(shù)據(jù)，并且每一個節(jié)點有指向下一節(jié)點的
指針。
上圖是
jdk8的
HashMap的內(nèi)部結(jié)構(gòu)圖，此時在源碼源碼中就不再使用
Entry<K,V>[]作為數(shù)組，而是使用
Node<K,V>[]數(shù)組作為
哈希桶，每個哈希桶的后面也可能連著一條
單向鏈表或者
紅黑樹。
當單向鏈表的值>8的時候，鏈表就會轉(zhuǎn)換為紅黑樹進行存儲數(shù)據(jù)，具體詳細的紅黑樹介紹之前已經(jīng)寫過一篇，這里就不再贅述，未詳細了解的請移至這一篇[B樹、B-樹、B+樹、B*樹圖文詳解]。
在面試大廠的時候，其實答到這里，還是不完整的，為什么呢？因為你想你說的上面的實際由jdk7和jdk8轉(zhuǎn)變的一個結(jié)果，但是重要的為什么要這樣做？你還沒有回答。
如果你聰明點的話，就不會等著面試官拋出接下來的問題？而是自己去回答這個為什么？不是等著面試官繼續(xù)拋出這個為什么？一個會聊天的人他會去猜測對方想知道什么？
問點二：為什么JDK 7使用數(shù)組+鏈表？JDK8中為什么要使用紅黑樹？哈希沖突是怎么回事？HashMap又是怎么解決的？
在深入這些問題之前，首先要了解一些概念，比如什么是hash函數(shù)，對于hash函數(shù)，之前已經(jīng)詳細的寫過一篇，這里就不再贅述，詳細參考這一篇[大白話之哈希表和哈希算法]。
哈希沖突是怎么回事呢？當<k,v>的數(shù)據(jù)將要存進HashMap中的時候，會先，把k值經(jīng)過hash函數(shù)進行計算得到hash值，再通過hash值進行計算得到數(shù)據(jù)在數(shù)組的下標，在jdk7中的源碼如下：
//key 進行哈希計算
int hash = hash(key);
//獲取數(shù)組下標
int i = indexFor(hash, table.length);
通過計算后的下標，從而得到數(shù)組的對應(yīng)下標的位置，最后把k，v值存進去，同樣的當再次第二次存值的時候，同樣把k，v傳進來，當k再次進行計算出數(shù)組下標index，有可能和第一次計算的index的值相同。
為什么有可能相同呢？這個是hash函數(shù)的原因，看完上面推薦的那篇hash函數(shù)詳細介紹你就懂了。當兩次的計算index相同，這就是hash沖突。
但是，兩次的需要存進去的value值是不同的，這就出現(xiàn)了同一個數(shù)組后面有一條鏈表，會比較鏈表上的每一個value值與當前的value是否相同，若是不相同，通過頭插法，將數(shù)值插入鏈表中。如下圖所示：
接下來通通過源碼進行分析，在jdk 7插入的put 方法源碼如下：
public V put(K key, V value) {
//數(shù)組為空就進行初始化
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
//key 進行哈希計算
int hash = hash(key);
//獲取數(shù)組下標
int i = indexFor(hash, table.length);
//如果此下標有值，遍歷鏈表上的元素，key 一致的話就替換 value 的值
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++;
//新增一個key
addEntry(hash, key, value, i);
return null;
}
put方法中主要做了以下幾件事：
判斷
table數(shù)組是否為空，若為空進行初始化table數(shù)組。判斷key值是否為
null，將null是作為key存進去。若
key不為空，通過key計算出數(shù)組下標，判斷table[i]是否為空。若是不為空通過鏈表循環(huán)，判斷在鏈表中是否存在與該
key相等，若是存在，直接將value替換成新的value。若是table[i]為空或者鏈表中不存在與之相同的key，就addEntry(hash, key, value, i)新增一個節(jié)點。
接下來看看addEntry(hash, key, value, i)新增節(jié)點的源碼如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
//數(shù)組長度大于閾值且存在哈希沖突（即當前數(shù)組下標有元素），就將數(shù)組擴容至2倍
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
這個方法很簡單，直接就是判斷當前數(shù)組的大小是否>=threshold并且table[bucketIndex]是否為null。若成立擴容，然后rehash，重新得到新數(shù)組的下標值，最后 createEntry(hash, key, value, bucketIndex)創(chuàng)建新節(jié)點。
最后來看一下createEntry(hash, key, value, bucketIndex)創(chuàng)建新節(jié)點的源碼如下：
void createEntry(int hash, K key, V value, int bucketIndex) {
//此位置有元素，就在鏈表頭部插入新元素（頭插法）
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
該方法就是通過頭插法加入新節(jié)點，方法非常簡單，相信都能看懂。經(jīng)過上面對put方法的源碼分析，在jdk 7 中put操作的原理圖如下所示：
在
JDK 7中，鏈表存儲有一個缺點，就是當數(shù)據(jù)很多的時候，鏈表就會很長，每次查詢都會遍歷很長的鏈表。
因此在JDK 8中為了優(yōu)化HashMap的查詢效率，將內(nèi)部的結(jié)構(gòu)改為數(shù)組+鏈表+和紅黑樹，當一個哈希桶后面的鏈表長度>8的時候，就會將鏈表轉(zhuǎn)化為紅黑樹，紅黑樹是二分查找，提高了查詢的效率。接下來通過JDK 8的put源碼分析如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//數(shù)組為空就初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//當前下標為空，就直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//key 相同就覆蓋原來的值
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//樹節(jié)點插入數(shù)據(jù)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
//鏈表，尾插法插入數(shù)據(jù)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表長度超過8，就把鏈表轉(zhuǎn)為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key相同就覆蓋原來的值
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//數(shù)組長度大于閾值，就擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
通過分析源碼，上面的方法主要做了以下幾件事：
判斷當前桶是否為空，空的就需要初始化（
resize中會判斷是否進行初始化）。根據(jù)當前
key的hashcode定位到具體的桶中并判斷是否為空，為空表明沒有Hash沖突就直接在當前位置創(chuàng)建一個新桶即可。如果當前桶有值（ Hash 沖突），那么就要比較當前桶中的
key、key的hashcode與寫入的key是否相等，相等就賦值給 e。如果當前桶為紅黑樹，那就要按照紅黑樹的方式寫入數(shù)據(jù)。
如果是個鏈表，就需要將當前的
key、value封裝成一個新節(jié)點寫入到當前桶的后面（形成鏈表）。接著判斷當前鏈表的大小是否大于預(yù)設(shè)的閾值，大于時就要轉(zhuǎn)換為紅黑樹。
如果在遍歷過程中找到
key相同時直接退出遍歷。如果
e != null就相當于存在相同的key,那就需要將值覆蓋。最后判斷是否需要進行擴容。
繼續(xù)看下 treeifyBin 的源碼：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//鏈表轉(zhuǎn)為紅黑樹時，若此時數(shù)組長度小于64，擴容數(shù)組
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
//鏈表轉(zhuǎn)為樹結(jié)構(gòu)
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
由此可以看到1.8中，數(shù)組有兩種情況會發(fā)生擴容：
一是超過閾值
二是鏈表轉(zhuǎn)為紅黑樹且數(shù)組元素小于64時
由此在jdk1.8中，默認長度為16情況下，要么元素一直放在同一下標，鏈表轉(zhuǎn)為紅黑樹且數(shù)組元素小于64時就會擴容，要么超過閾值12時才會擴容。
依據(jù)上面的源碼分析，在JDK 1.8中put方法的執(zhí)行的原理圖如下：
通過上面的分析，我們可以看到
jdk1.7和
1.8情況下
hashmap實現(xiàn)方式區(qū)別是非常大的。在源碼的分析中，也可以找到下面問題的答案。
問點三：HashMap的擴容機制是怎么樣的？JDK7與JDK8有什么不同嗎？
JDK 1.7的擴容條件是數(shù)組長度大于閾值且存在哈希沖突，在JDK 7中的擴容的源碼如下：
void addEntry(int hash, K key, V value, int bucketIndex) {
//數(shù)組長度大于閾值且存在哈希沖突（即當前數(shù)組下標有元素），就將數(shù)組擴容至2倍
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
而JDK 1.8擴容條件是數(shù)組長度大于閾值或鏈表轉(zhuǎn)為紅黑樹且數(shù)組元素小于64時，源碼中的體現(xiàn)如下所示：
//數(shù)組長度大于閾值，就擴容
if (++size > threshold)
resize();
//鏈表轉(zhuǎn)為紅黑樹時，若此時數(shù)組長度小于64，擴容數(shù)組
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
問點四：HashMap中的鍵值可以為Null嗎？能簡單說一下原理嗎？
在JDK7中是允許null存進去的，通過 putForNullKey(value)方法來存儲key為null值，具體的實現(xiàn)的源代碼如下：
if (key == null)
return putForNullKey(value);
而在JDK 8中當傳進key為null值的時候，就直接將hash值取0，進行計算存入值的位置。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
問點五：HashMap中能put兩個相同的Key嗎？為什么能或為什么不能？
這個問題比較簡單，在JDK7和JDK8中的做法是一樣的，若是存入的key值一樣，就會將原來的key所對應(yīng)的value值直接替換掉，可以從源碼中看出：
// JDK1.7
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
// 直接替換原來的value值
e.value = value;
e.recordAccess(this);
return oldValue;
}
// JDK 1.8
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 存在key值相同
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
// 替換掉原來value值
e.value = value;
afterNodeAccess(e);
return oldValue;
}
問點六：聊一聊JDK 7的HashMap中的“死鎖”是怎么回事？
HashMap是線程不安全的，在HashMap的源碼中并未對其操作進行同步執(zhí)行，所以在并發(fā)訪問的時候就會出現(xiàn)線程安全的問題。
由于上一篇的ConcurrentHashMap篇中講到了死鎖，也畫了圖，但是很多讀者說看不懂，這里我的鍋，在這里詳細的進行圖解。
假設(shè)：有線程A和線程B，并發(fā)訪問HashMap中的數(shù)據(jù)。假設(shè)HashMap的長度為2(這里只是為了講解方便假設(shè)長度為2)，鏈表的結(jié)構(gòu)圖如下所示：
4和8都位于同一條鏈表上，其中的threshold為1，現(xiàn)在線程A和線程B都要進行put操作，首先線程A進行插入值。
此時，線程A執(zhí)行到transfer函數(shù)中（transfer函數(shù)是resize擴容方法中調(diào)用的另一個方法），當執(zhí)行（1）位置的時候，如下所示：
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next; ---------------------(1)
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} // while
}
}
此時線程A掛起，在此時在線程A的棧中就會存在如下值：
e = 4
next = 8
此時線程B執(zhí)行put的操作，并發(fā)現(xiàn)在進行put操作的時候需要擴容，當線程B執(zhí)行 transfer函數(shù)中的while循環(huán)，即會把原來的table變成新一table（線程B自己的棧中），再寫入到內(nèi)存中。
執(zhí)行的過程如下圖所示（假設(shè)兩個元素在新的hash函數(shù)下也會映射到同一個位置）：
此時線程A有獲取到
cpu的執(zhí)行時間，接著執(zhí)行（但是纖層A中的數(shù)據(jù)仍是舊表數(shù)據(jù)），即從
transfer代碼（1）處接著執(zhí)行，當前的
e = 4, next = 8, 上面已經(jīng)描述，執(zhí)行的的過程若下圖所示：
當操作完成，執(zhí)行查找時，會陷入死循環(huán)！
問點七：HashMap是線程安全的嗎？為什么安全或者不安全？
從上圖JDK8的put操作原理圖中可以看出為HashMap的put方法的詳細過程，其中造成線程不安全的方法主要是resize(擴容)方法.
假設(shè)，現(xiàn)在有線程A 和線程B 共同對同一個HashMap進行put操作，假設(shè)A和B插入的Key-Value中key的hashcode是相同的,這說明該鍵值對將會插入到Table的同一個下標的,也就是會發(fā)生哈希碰撞。
此時HashMap按照平時的做法是形成一個鏈表(若超過八個節(jié)點則是紅黑樹),現(xiàn)在我們插入的下標為null(Table[i]==null)則進行正常的插入。
此時線程A進行到了這一步正準備插入，這時候線程A堵塞，線程B獲得運行時間，進行同樣操作，也是Table[i]==null 。此時它直接運行完整個put方法,成功將元素插入.。
隨后，線程A獲得運行時間接上上面的判斷繼續(xù)運行，進行了Table[i]==null的插入(此時其實應(yīng)該是Table[i]!=null的操作，因為前面線程B已經(jīng)插入了一個元素了)，這樣就會直接把原來線程B插入的數(shù)據(jù)直接覆蓋了，如此一來就造成了線程不安全問題.
問點八：為什么重寫對象的Equals方法時，要重寫HashCode方法？這個和HashMap有關(guān)系嗎？為什么？
對于這個問題，我之前已經(jīng)詳細寫過一篇文章，這里就不再做贅述。
特別推薦一個分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：
長按訂閱更多精彩▼
如有收獲，點個在看，誠摯感謝
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
