一文帶你解讀所有HashMap的面試題

更新時間：2022年09月01日 15:52:36 作者：鴨血粉絲Tang

HashMap在面試的時候，是非常容易被問到的。因為在JDK8出來之后，非常容易被問到關(guān)于HashMap的知識點，而如果對于沒有研究過他的源代碼的同學(xué)來說，這個可能只是說出一部分來。本文就把HashMap上面大部分會被在面試中問到的內(nèi)容，做個總結(jié)，希望有所幫助

關(guān)于 HashMap 阿粉相信大家再面試的時候，是非常容易被問到的，為什么呢？因為至少是在 JDK8 出來之后，非常容易被問到關(guān)于 HashMap 的知識點，而如果對于沒有研究過他的源代碼的同學(xué)來說，這個可能只是說出一部分來，比如線程安全，鏈表+紅黑樹，以及他的擴(kuò)容等等，今天阿粉就來把 HashMap 上面大部分會被在面試中問到的內(nèi)容，做個總結(jié)。

HashMap

說到 HashMap 想必大家從腦海中直接復(fù)現(xiàn)出了一大堆的面試題，

HashMap 的數(shù)據(jù)結(jié)構(gòu)
JDK7 和 JDK8 HashMap哪里不一樣
HashMap是否安全
HashMap 的擴(kuò)容機(jī)制

說到這里，我們就來挨著分析一下這個 HashMap 的這寫面試題。

HashMap 的數(shù)據(jù)結(jié)構(gòu)

這個 HashMap 的數(shù)據(jù)結(jié)構(gòu)，面試官這個問題，屬于那種可大可小的，往大了說，那就是需要你把所有的關(guān)于 HashMap 中的內(nèi)容都詳細(xì)的解釋明白，但是如果要是往小了說，那就是介紹一下內(nèi)部結(jié)構(gòu)，就可以了。

阿粉今天來分析一下這個數(shù)據(jù)結(jié)構(gòu)了。

HashMap 里面有幾個比較重要的參數(shù)：

//默認(rèn)初始容量——必須是2的冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

//當(dāng)沒有構(gòu)造函數(shù)中指定使用的負(fù)載系數(shù)
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//擴(kuò)容的閾值，等于 CAPACITY * LOAD_FACTOR
static final int TREEIFY_THRESHOLD = 8;

//降容的閾值
static?final?int?UNTREEIFY_THRESHOLD?=?6;

//擴(kuò)容的另外一個參數(shù)
static?final?int?MIN_TREEIFY_CAPACITY?=?64;

參數(shù)我們都看到了上述的這些內(nèi)容了，如果用大白話，怎么去形容這些參數(shù)呢？其實這就涉及到這個后面的 JDK8 中的 HashMap 不一樣的結(jié)構(gòu)了，

我們也知道 JDK8 中的 HashMap ，如果在橫向上是數(shù)組的話，那么他的縱向的每一個元素上面，都是一個單項的鏈表，而這個鏈表，會根據(jù)長度，來進(jìn)行不通的演化，而這個演化就是擴(kuò)容成為樹結(jié)構(gòu)和降容成為鏈表結(jié)構(gòu)的關(guān)鍵，而這些關(guān)鍵，都是通過這些參數(shù)來進(jìn)行的定義。

CAPACITY 就相當(dāng)于是 HashMap 中的默認(rèn)初始容量。

LOAD_FACTOR 負(fù)載因子

TREEIFY_THRESHOLD 樹化的閾值，也就是說table的node中的鏈表長度超過這個閾值的時候，該鏈表會變成樹

UNTREEIFY_THRESHOLD 樹降級成為鏈表的閾值（也就是說table的node中的樹長度低于這個閾值的時候，樹會變成鏈表）

MIN_TREEIFY_CAPACITY 樹化的另一個參數(shù)，就是當(dāng)hashmap中的node的個數(shù)大于這個值的時候，hashmap中的有些鏈表才會變成樹。

transient Node<K,V>[] table Hash 表

有些小伙伴在面試的時候，就會說，當(dāng) HashMap中的某個 node 鏈表長度大于 8 的時候，HashMap 中的這個鏈表就會變成樹，實際上不是的，這個還和 MIN_TREEIFY_CAPACITY 有關(guān)系，也就是說整個 HashMap 的 node 數(shù)量大于64，node 的鏈表長度大于 8 才會變成樹。

JDK7 和 JDK8 HashMap哪里不一樣

JDK7我們大家也都知道，如果按照橫向是數(shù)組，那么他的縱向每個元素上面，都是一個單向的鏈表，而橫向上，每一個實體，就相當(dāng)于是一個 Entry 的實例。

而這每一個 Entry 中都包含了四個屬性，

key
value
hash值
用于單項列表的next

就像下圖這個樣子

JDK7

所以 JDK7 的 HashMap 的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組+鏈表的形式構(gòu)成

而 JDK8 就不一樣了，因為他們的內(nèi)部很巧妙的給增加了紅黑樹，如下圖

JDK8

所以 JDK8 的 HashMap 的數(shù)據(jù)結(jié)構(gòu)就是 數(shù)組+鏈表+紅黑樹 的形式構(gòu)成了。

HashMap是否安全

一說這個，肯定都是非?；A(chǔ)的面試題，都知道 HashMap 是屬于那種線程不安全的類，為什么不安全，他不安全到底會提現(xiàn)在哪個地方，難道面試的時候，你就只會說他的內(nèi)部沒有被 synchronize 關(guān)鍵字控制么？

所以，說起 HashMap 的不安全，那么就得從 put 和 get 方法說起了。

這個直接先看內(nèi)部實現(xiàn)，我們先來看 put 方法，然后去分析這個 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;
????????//在這里先進(jìn)行?Hash表的初始化
????????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????????????n?=?(tab?=?resize()).length;
????????//通過?Hash?值計算在?Hash?表中的位置，并將這個位置的元素賦值給P?如果等于空的話創(chuàng)建一個新的?node
????????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????????tab[i]?=?newNode(hash,?key,?value,?null);
????????else?{
????????????Node<K,V>?e;?K?k;
????????????//Hash表的當(dāng)前的?index?已經(jīng)存在了元素，向這個元素后追加鏈表
????????????if?(p.hash?==?hash?&&
????????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????e?=?p;
????????????else?if?(p?instanceof?TreeNode)
????????????????e?=?((TreeNode<K,V>)p).putTreeVal(this,?tab,?hash,?key,?value);
????????????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;
????????????????????}
????????????????????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;
????????if?(++size?>?threshold)
????????????resize();
????????afterNodeInsertion(evict);
????????return?null;
????}

看到源碼之后，我們猜想一下都會有哪些地方會出問題呢？比如，這時候如果有兩個線程同時去執(zhí)行 put

一個線程 A 執(zhí)行put("1","A");

一個線程 B 執(zhí)行put("2","B");

如果這個時候線程 A 和 B 都執(zhí)行了 if ((p = tab[i = (n - 1) & hash]) == null) 但是，如果這個時候線程 A 先執(zhí)行了 tab[i] = newNode(hash, key, value, null); 這時候，內(nèi)部是沒啥問題的，已經(jīng)放進(jìn)去了，

這時候如果線程 B 去執(zhí)行 tab[i] = newNode(hash, key, value, null); 就會導(dǎo)致 A 線程中的 key 為 1 的元素 A 丟失。直接被線程 B 進(jìn)行了覆蓋，這也是為什么會有一些人說， JDK7 中是對擴(kuò)容時會造成環(huán)形鏈或數(shù)據(jù)丟失，而在 JDK8 中是會會發(fā)生數(shù)據(jù)覆蓋的情況。

就會出現(xiàn) null 的問題，這個問題，不論是 JDK7 還是 JDK8 全都有這個問題，如果面試的時候，能夠從這個地方分析一下的，至少這個線程不安全，你確實是自己去研究了一下，所以這就可以完美的解釋了，HashMap 的線程不安全的問題了。

HashMap 的擴(kuò)容機(jī)制

我們在上面也都列舉了一下 HashMap 的一些關(guān)鍵參數(shù)，接下來，就來分析他的擴(kuò)容是怎么實現(xiàn)的，

????public?HashMap(int?initialCapacity,?float?loadFactor)?{
????????if?(initialCapacity?<?0)
????????????throw?new?IllegalArgumentException("Illegal?initial?capacity:?"?+
???????????????????????????????????????????????initialCapacity);
????????if?(initialCapacity?>?MAXIMUM_CAPACITY)
????????????initialCapacity?=?MAXIMUM_CAPACITY;
????????if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))
????????????throw?new?IllegalArgumentException("Illegal?load?factor:?"?+
???????????????????????????????????????????????loadFactor);
????????this.loadFactor?=?loadFactor;
????????this.threshold?=?tableSizeFor(initialCapacity);
????}

這段代碼，寫的看起來非常的舒服，指定了初始容量和加載因子，下一次需要擴(kuò)容的容量 threshold 值由 tableSizeFor 方法得出

static?final?int?tableSizeFor(int?cap)?{
????????int?n?=?cap?-?1;
????????//??>>>：無符號右移。無論是正數(shù)還是負(fù)數(shù)，高位通通補0。
????????n?|=?n?>>>?1;
????????n?|=?n?>>>?2;
????????n?|=?n?>>>?4;
????????n?|=?n?>>>?8;
????????n?|=?n?>>>?16;
????????return?(n?<?0)???1?:?(n?>=?MAXIMUM_CAPACITY)???MAXIMUM_CAPACITY?:?n?+?1;
????}

而 tableSizeFor 這個方法是用于計算出大于等于 cap 值的最大的2的冪值,而后續(xù) HashMap 需要擴(kuò)容時，每次 table 數(shù)組長度都擴(kuò)展為原來的兩倍，所以，table 數(shù)組長度總是為2的冪值。

為什么用位移運算，不直接使用.pow的方法，這個東西，很明顯，位運算這種方式，效率可比.pow的效率要高很多，接下來就是正兒八經(jīng)的擴(kuò)容方法了。

????final?Node<K,V>[]?resize()?{
????????Node<K,V>[]?oldTab?=?table;
????????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;?//舊容量
????????int?oldThr?=?threshold;//?舊的需要擴(kuò)容的閾值
????????int?newCap,?newThr?=?0;
????????if?(oldCap?>?0)?{//如果不是第一次擴(kuò)容
????????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{
????????????????threshold?=?Integer.MAX_VALUE;//?如果容量大于最大值，將閾值設(shè)為最大值，這樣不會發(fā)生下次擴(kuò)容
????????????????return?oldTab;
????????????}
????????????//?擴(kuò)容容量為上一次容量的兩倍
????????????else?if?((newCap?=?oldCap?<<?1)?<?MAXIMUM_CAPACITY?&&
?????????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????????newThr?=?oldThr?<<?1;?//?下次擴(kuò)容閾值等于本次擴(kuò)容閾值*2，因為擴(kuò)容會擴(kuò)為原來容量的兩倍，所以依然滿足?newThr?=?newCap?*?loadFactor
????????}
????????else?if?(oldThr?>?0)?//?第一次擴(kuò)容，并且用戶指定了初始容量
????????????newCap?=?oldThr;?//?擴(kuò)展的容量為閾值
????????else?{???????????????//?第一次擴(kuò)容，并且初始容量和加載因子使用的默認(rèn)值
????????????newCap?=?DEFAULT_INITIAL_CAPACITY;
????????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);
????????}
????????if?(newThr?==?0)?{??//?如果用戶指定了初始容量時，并且是第一次擴(kuò)容
????????????float?ft?=?(float)newCap?*?loadFactor;
????????????//?下次擴(kuò)容閾值為?newCap?*?loadFactor
????????????newThr?=?(newCap?<?MAXIMUM_CAPACITY?&&?ft?<?(float)MAXIMUM_CAPACITY??
??????????????????????(int)ft?:?Integer.MAX_VALUE);
????????}
????????threshold?=?newThr;
????????@SuppressWarnings({"rawtypes","unchecked"})
????????Node<K,V>[]?newTab?=?(Node<K,V>[])new?Node[newCap];//?新的數(shù)組
????????table?=?newTab;
????????if?(oldTab?!=?null)?{
????????????for?(int?j?=?0;?j?<?oldCap;?++j)?{?//將舊數(shù)組數(shù)據(jù)移動到新數(shù)組
????????????????Node<K,V>?e;
????????????????if?((e?=?oldTab[j])?!=?null)?{
????????????????????oldTab[j]?=?null;
????????????????????if?(e.next?==?null)?//?如果還不是鏈表或紅黑樹，把數(shù)據(jù)直接移動到新數(shù)組中對應(yīng)位置
????????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;
????????????????????else?if?(e?instanceof?TreeNode)?//紅黑樹時的移動數(shù)據(jù)
????????????????????????((TreeNode<K,V>)e).split(this,?newTab,?j,?oldCap);
????????????????????else?{?//?鏈表時移動數(shù)據(jù)
????????????????????????//?原來的key的hash值對應(yīng)的數(shù)組位置可能會發(fā)生變化
?????????????????????//?因為在做與操作時，現(xiàn)有的數(shù)組長度多了兩倍，也就是多了一位的與計算
?????????????????????//?所以，鏈表或紅黑樹中的元素可能在原來位置，或者在原來位置?+?原來數(shù)組長度?的位置
????????????????????????Node<K,V>?loHead?=?null,?loTail?=?null;
????????????????????????Node<K,V>?hiHead?=?null,?hiTail?=?null;
????????????????????????Node<K,V>?next;
????????????????????????do?{
????????????????????????....省略不分
????????????????????}
????????????????}
????????????}
????????}
????????return?newTab;
????}

總的來說，擴(kuò)容就是創(chuàng)建一個新的數(shù)組，數(shù)組長度為原來的兩倍，并將下一次需要擴(kuò)容的閾值設(shè)置為新數(shù)組乘以加載因子的大小。

然后將原來數(shù)組中的數(shù)據(jù)移動到新數(shù)組中。

如果數(shù)組中的元素不是鏈表和紅黑樹，那么直接移動到原來舊數(shù)組中下標(biāo)的位置。

否則如果是鏈表或紅黑樹，那么其中的數(shù)據(jù)可能會在原來的位置，或者在原來的位置+原來數(shù)組長度的位置，此時將原來的鏈表或紅黑樹分為兩個鏈表或紅黑樹，再把數(shù)據(jù)移動到相應(yīng)位置。

到此這篇關(guān)于一文帶你解讀所有HashMap的面試題的文章就介紹到這了,更多相關(guān)HashMap面試題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: