無(wú)論是在實(shí)際工作中還是在面試中，HashMap 無(wú)疑是使用頻率最高的知識(shí)點(diǎn)之一，所以我們需要搞懂每一個(gè)關(guān)于 HashMap 的知識(shí)點(diǎn)才行。

哈嘍，大家好，我是老王，歡迎來(lái)到 Java 面試突擊，我們今天來(lái)開(kāi)始第 6 期的內(nèi)容。

本期的問(wèn)題是：HashMap 為什會(huì)導(dǎo)致 CPU 運(yùn)行 100%？這是一個(gè)比較常見(jiàn)的經(jīng)典問(wèn)題了，但是有很多人讀者朋友給我反饋，尼瑪，看文章根本看不懂啊？Sun 公司都不知道這個(gè)問(wèn)題的原因吧？不，是 Oracle 公司都不知道這個(gè)問(wèn)題的原因吧？面試官怕也不知道這個(gè)的答案吧？

咳咳，作為一個(gè)很正經(jīng)的面試官，我覺(jué)得這個(gè)問(wèn)題一點(diǎn)都不重要，重要的是你不知道答案啊。好的，下一位面試者請(qǐng)進(jìn)，您先回去等通知吧。

為了避免這種尷尬的事情發(fā)生，今天我們來(lái)好好聊一下這個(gè)問(wèn)題，畢竟技能再手，才能吊打面試官不是？

正文

這個(gè)問(wèn)題相關(guān)的知識(shí)點(diǎn)，有以下幾個(gè)：

HashMap 的底層數(shù)據(jù)結(jié)構(gòu)是什么？

什么是哈希碰撞？如何該解決這個(gè)問(wèn)題？

什么是擴(kuò)展因子？它有什么用？

還有對(duì) HashMap 源碼的理解，為什么 HashMap 會(huì)導(dǎo)致死循環(huán)？

視頻版答案

視頻內(nèi)容如下：

圖文答案

1.HashMap?的底層數(shù)據(jù)結(jié)構(gòu)

先來(lái)說(shuō) HashMap 的底層數(shù)據(jù)結(jié)構(gòu)，看過(guò) HashMap 的源碼我們就會(huì)發(fā)現(xiàn)，JDK 1.7 和 JDK 1.8 HashMap 的組成是不同的，JDK 1.7 HashMap 的組成是數(shù)組 +?鏈表的形式，而 JDK 1.8 新增了紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)，當(dāng) HashMap 中的鏈表長(zhǎng)度大于 8 時(shí)，鏈表結(jié)構(gòu)就會(huì)轉(zhuǎn)換為紅黑樹(shù)，如下圖所示：

2.哈希碰撞及解決方案

所謂的哈希碰撞指的是不同的值，經(jīng)過(guò)哈希之后得到的值確是相同的，這種情況就叫做哈希碰撞或哈希沖突。解決哈希碰撞的常用方法是：開(kāi)放定址法和鏈表地址法，而?HashMap?采用的就是鏈表地址法。它的實(shí)現(xiàn)原理就是將?HashMap?中相同的哈希值以鏈表的形式存儲(chǔ)起來(lái)。

3.擴(kuò)展因子

擴(kuò)展因子也叫加載因子或負(fù)載因子是 HashMap 中的一個(gè)屬性，如下圖所示：假如數(shù)組的默認(rèn)長(zhǎng)度為 10，擴(kuò)展因子為 0.5，那么當(dāng)數(shù)組超過(guò) 10*0.5=5 個(gè)時(shí)，HashMap 就會(huì)擴(kuò)容為之前容量的兩倍，所以說(shuō)擴(kuò)展因子就是用來(lái)判定 HashMap 是否滿足擴(kuò)容條件的。

4.HashMap死循環(huán)分析

HashMap 導(dǎo)致 CPU 100%?的原因就是因?yàn)?HashMap 死循環(huán)導(dǎo)致的，那 HashMap 是如何造成死循環(huán)的？接下來(lái)我們一起來(lái)看。

以 JDK 1.7 為例，假設(shè) HashMap 的默認(rèn)大小為 2，HashMap 本身中有一個(gè)鍵值 key(5)，我們?cè)偈褂脙蓚€(gè)線程：t1 添加 key(3)，t2 添加 key(7)，首先兩個(gè)線程先把 key(3) 和 key(7) 都添加到 HashMap 中，此時(shí)因?yàn)?HashMap 的長(zhǎng)度不夠用了就會(huì)進(jìn)行擴(kuò)容操作，然后這時(shí)線程 t1 在執(zhí)行到 Entry<K,V> next = e.next; 時(shí)，交出了 CPU 的使用權(quán)，源代碼如下：

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; // 線程一執(zhí)行此處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;}} }

那么此時(shí)線程 t1 中的 e 指向了 key(3)，而 next 指向了 key(7) ；之后線程 t2 重新 rehash 之后鏈表的順序被反轉(zhuǎn)，鏈表的位置變成了 key(5) -> key(7) -> key(3)，其中 “->” 用來(lái)表示下一個(gè)元素，當(dāng) t1 重新獲得執(zhí)行權(quán)之后，先執(zhí)行 newTalbe[i] = e 把 key(3) 的 next 設(shè)置為 key(7)，而下次循環(huán)時(shí)查詢到 key(7) 的 e.next 為 key(3)，于是就形 成了 key(3) 和 key(7) 的環(huán)形引用，就導(dǎo)致了死循環(huán)的產(chǎn)生，如下圖所示：

HashMap 發(fā)生死循環(huán)的一個(gè)重要原因是 JDK 1.7 時(shí)鏈表的插入是首部倒序插入的，而 JDK 1.8 時(shí)已經(jīng)變成了尾部插入，有人把這個(gè)死循環(huán)的問(wèn)題反饋給了 Sun 公司，但它們認(rèn)為這不是一個(gè)問(wèn)題，因?yàn)?HashMap 本身就是非線程安全的，如果要在多線程使用建議使用 ConcurrentHashMap 替代 HashMap，但面試中這個(gè)問(wèn)題被問(wèn)的頻率比較高，所以在這里就特殊說(shuō)明一下。

小結(jié)

HashMap 是非線程安全的，以 JDK 1.7 為例，當(dāng)多線程并發(fā)擴(kuò)容時(shí)就會(huì)出現(xiàn)環(huán)形引用的問(wèn)題，從而導(dǎo)致死循環(huán)的出現(xiàn)，一直死循環(huán)就會(huì)導(dǎo)致 CPU 運(yùn)行 100%，所以在多線程使用時(shí)，我們需要使用 ConcurrentHashMap 來(lái)替代 HashMap，但只有懂得其中的因果關(guān)系才能吊打面試官，好了，本節(jié)內(nèi)容到這里就結(jié)束了，我們下期再見(jiàn)。

---

上期中獎(jiǎng)名單：皮卡皮卡、一步、好好學(xué)習(xí)、談笑、包子有話要講。

以上中獎(jiǎng)的朋友，請(qǐng)加我的微信：GG_Stone 領(lǐng)取獎(jiǎng)勵(lì)。

【END】

近期熱文

?

• 面試突擊 005 | Redis 是如何實(shí)現(xiàn)高可用的？它的實(shí)現(xiàn)方式有哪些？
  

• 面試突擊 004 | 如何排查 Redis 中的慢查詢？視頻實(shí)戰(zhàn)篇
  

• 面試突擊 003 | Redis 如何實(shí)現(xiàn)查詢附近的人？
  

• 面試突擊 002 | Redis 是如何處理已過(guò)期元素的？

• 面試突擊 001 | Redis 如何從海量數(shù)據(jù)中查詢出某一個(gè) Key？

• Java面試詳解(2020版)：500+ 面試題和核心知識(shí)點(diǎn)詳解

關(guān)注下方二維碼，訂閱更多精彩內(nèi)容

朕已閱?

總結(jié)

以上是生活随笔為你收集整理的HashMap 为什么会导致 CPU 100%？文章看不懂？来看这个视频吧！——面试突击 006 期...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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