一文帶你解讀所有HashMap的面試題
關(guān)于 HashMap 阿粉相信大家再面試的時(shí)候,是非常容易被問(wèn)到的,為什么呢?因?yàn)橹辽偈窃?JDK8 出來(lái)之后,非常容易被問(wèn)到關(guān)于 HashMap 的知識(shí)點(diǎn),而如果對(duì)于沒(méi)有研究過(guò)他的源代碼的同學(xué)來(lái)說(shuō),這個(gè)可能只是說(shuō)出一部分來(lái),比如線(xiàn)程安全,鏈表+紅黑樹(shù),以及他的擴(kuò)容等等,今天阿粉就來(lái)把 HashMap 上面大部分會(huì)被在面試中問(wèn)到的內(nèi)容,做個(gè)總結(jié)。
HashMap
說(shuō)到 HashMap 想必大家從腦海中直接復(fù)現(xiàn)出了一大堆的面試題,
- HashMap 的數(shù)據(jù)結(jié)構(gòu)
- JDK7 和 JDK8 HashMap哪里不一樣
- HashMap是否安全
- HashMap 的擴(kuò)容機(jī)制
說(shuō)到這里,我們就來(lái)挨著分析一下這個(gè) HashMap 的這寫(xiě)面試題。
HashMap 的數(shù)據(jù)結(jié)構(gòu)
這個(gè) HashMap 的數(shù)據(jù)結(jié)構(gòu),面試官這個(gè)問(wèn)題,屬于那種可大可小的,往大了說(shuō),那就是需要你把所有的關(guān)于 HashMap 中的內(nèi)容都詳細(xì)的解釋明白,但是如果要是往小了說(shuō),那就是介紹一下內(nèi)部結(jié)構(gòu),就可以了。
阿粉今天來(lái)分析一下這個(gè)數(shù)據(jù)結(jié)構(gòu)了。
HashMap 里面有幾個(gè)比較重要的參數(shù):
//默認(rèn)初始容量——必須是2的冪 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//當(dāng)沒(méi)有構(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ò)容的另外一個(gè)參數(shù) static?final?int?MIN_TREEIFY_CAPACITY?=?64;
參數(shù)我們都看到了上述的這些內(nèi)容了,如果用大白話(huà),怎么去形容這些參數(shù)呢?其實(shí)這就涉及到這個(gè)后面的 JDK8 中的 HashMap 不一樣的結(jié)構(gòu)了,
我們也知道 JDK8 中的 HashMap ,如果在橫向上是數(shù)組的話(huà),那么他的縱向的每一個(gè)元素上面,都是一個(gè)單項(xiàng)的鏈表,而這個(gè)鏈表,會(huì)根據(jù)長(zhǎng)度,來(lái)進(jìn)行不通的演化,而這個(gè)演化就是擴(kuò)容成為樹(shù)結(jié)構(gòu)和降容成為鏈表結(jié)構(gòu)的關(guān)鍵,而這些關(guān)鍵,都是通過(guò)這些參數(shù)來(lái)進(jìn)行的定義。
CAPACITY
就相當(dāng)于是 HashMap 中的默認(rèn)初始容量。
LOAD_FACTOR
負(fù)載因子
TREEIFY_THRESHOLD
樹(shù)化的閾值,也就是說(shuō)table的node中的鏈表長(zhǎng)度超過(guò)這個(gè)閾值的時(shí)候,該鏈表會(huì)變成樹(shù)
UNTREEIFY_THRESHOLD
樹(shù)降級(jí)成為鏈表的閾值(也就是說(shuō)table的node中的樹(shù)長(zhǎng)度低于這個(gè)閾值的時(shí)候,樹(shù)會(huì)變成鏈表)
MIN_TREEIFY_CAPACITY
樹(shù)化的另一個(gè)參數(shù),就是當(dāng)hashmap中的node的個(gè)數(shù)大于這個(gè)值的時(shí)候,hashmap中的有些鏈表才會(huì)變成樹(shù)。
transient Node<K,V>[] table
Hash 表
有些小伙伴在面試的時(shí)候,就會(huì)說(shuō),當(dāng) HashMap中的某個(gè) node 鏈表長(zhǎng)度大于 8 的時(shí)候,HashMap 中的這個(gè)鏈表就會(huì)變成樹(shù),實(shí)際上不是的,這個(gè)還和 MIN_TREEIFY_CAPACITY
有關(guān)系,也就是說(shuō)整個(gè) HashMap 的 node 數(shù)量大于64,node 的鏈表長(zhǎng)度大于 8 才會(huì)變成樹(shù)。
JDK7 和 JDK8 HashMap哪里不一樣
JDK7我們大家也都知道,如果按照橫向是數(shù)組,那么他的縱向每個(gè)元素上面,都是一個(gè)單向的鏈表,而橫向上,每一個(gè)實(shí)體,就相當(dāng)于是一個(gè) Entry 的實(shí)例。
而這每一個(gè) Entry 中都包含了四個(gè)屬性,
- key
- value
- hash值
- 用于單項(xiàng)列表的next
就像下圖這個(gè)樣子
JDK7
所以 JDK7 的 HashMap 的數(shù)據(jù)結(jié)構(gòu)就是 數(shù)組+鏈表 的形式構(gòu)成
而 JDK8 就不一樣了,因?yàn)樗麄兊膬?nèi)部很巧妙的給增加了紅黑樹(shù),如下圖
JDK8
所以 JDK8 的 HashMap 的數(shù)據(jù)結(jié)構(gòu)就是 數(shù)組+鏈表+紅黑樹(shù)
的形式構(gòu)成了。
HashMap是否安全
一說(shuō)這個(gè),肯定都是非?;A(chǔ)的面試題,都知道 HashMap 是屬于那種線(xiàn)程不安全的類(lèi),為什么不安全,他不安全到底會(huì)提現(xiàn)在哪個(gè)地方,難道面試的時(shí)候,你就只會(huì)說(shuō)他的內(nèi)部沒(méi)有被 synchronize 關(guān)鍵字控制么?
所以,說(shuō)起 HashMap 的不安全,那么就得從 put 和 get 方法說(shuō)起了。
這個(gè)直接先看內(nèi)部實(shí)現(xiàn),我們先來(lái)看 put 方法,然后去分析這個(gè) 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; ????????//通過(guò)?Hash?值計(jì)算在?Hash?表中的位置,并將這個(gè)位置的元素賦值給P?如果等于空的話(huà)創(chuàng)建一個(gè)新的?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)存在了元素,向這個(gè)元素后追加鏈表 ????????????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)?{ ????????????????????//新建接點(diǎn),并且追加到列表 ????????????????????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; ????}
看到源碼之后,我們猜想一下都會(huì)有哪些地方會(huì)出問(wèn)題呢?比如,這時(shí)候如果有兩個(gè)線(xiàn)程同時(shí)去執(zhí)行 put
一個(gè)線(xiàn)程 A 執(zhí)行put("1","A");
一個(gè)線(xiàn)程 B 執(zhí)行put("2","B");
如果這個(gè)時(shí)候線(xiàn)程 A 和 B 都執(zhí)行了 if ((p = tab[i = (n - 1) & hash]) == null)
但是,如果這個(gè)時(shí)候線(xiàn)程 A 先執(zhí)行了 tab[i] = newNode(hash, key, value, null);
這時(shí)候,內(nèi)部是沒(méi)啥問(wèn)題的,已經(jīng)放進(jìn)去了,
這時(shí)候如果線(xiàn)程 B 去執(zhí)行 tab[i] = newNode(hash, key, value, null);
就會(huì)導(dǎo)致 A 線(xiàn)程中的 key 為 1 的元素 A 丟失。直接被線(xiàn)程 B 進(jìn)行了覆蓋,這也是為什么會(huì)有一些人說(shuō), JDK7 中是對(duì)擴(kuò)容時(shí)會(huì)造成環(huán)形鏈或數(shù)據(jù)丟失,而在 JDK8 中是會(huì)會(huì)發(fā)生數(shù)據(jù)覆蓋的情況。
就會(huì)出現(xiàn) null 的問(wèn)題,這個(gè)問(wèn)題,不論是 JDK7 還是 JDK8 全都有這個(gè)問(wèn)題,如果面試的時(shí)候,能夠從這個(gè)地方分析一下的,至少這個(gè)線(xiàn)程不安全,你確實(shí)是自己去研究了一下,所以這就可以完美的解釋了,HashMap 的線(xiàn)程不安全的問(wèn)題了。
HashMap 的擴(kuò)容機(jī)制
我們?cè)谏厦嬉捕剂信e了一下 HashMap 的一些關(guān)鍵參數(shù),接下來(lái),就來(lái)分析他的擴(kuò)容是怎么實(shí)現(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); ????}
這段代碼,寫(xiě)的看起來(lái)非常的舒服,指定了初始容量和加載因子,下一次需要擴(kuò)容的容量 threshold
值由 tableSizeFor
方法得出
static?final?int?tableSizeFor(int?cap)?{ ????????int?n?=?cap?-?1; ????????//??>>>:無(wú)符號(hào)右移。無(wú)論是正數(shù)還是負(fù)數(shù),高位通通補(bǔ)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
這個(gè)方法是用于計(jì)算出大于等于 cap 值的最大的2的冪值,而后續(xù) HashMap 需要擴(kuò)容時(shí),每次 table 數(shù)組長(zhǎng)度都擴(kuò)展為原來(lái)的兩倍,所以,table 數(shù)組長(zhǎng)度總是為2的冪值。
為什么用位移運(yùn)算,不直接使用.pow的方法, 這個(gè)東西,很明顯, 位運(yùn)算這種方式,效率可比.pow的效率要高很多,接下來(lái)就是正兒八經(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è)為最大值,這樣不會(huì)發(fā)生下次擴(kuò)容 ????????????????return?oldTab; ????????????} ????????????//?擴(kuò)容容量為上一次容量的兩倍 ????????????else?if?((newCap?=?oldCap?<<?1)?<?MAXIMUM_CAPACITY?&& ?????????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY) ????????????????newThr?=?oldThr?<<?1;?//?下次擴(kuò)容閾值等于本次擴(kuò)容閾值*2,因?yàn)閿U(kuò)容會(huì)擴(kuò)為原來(lái)容量的兩倍,所以依然滿(mǎn)足?newThr?=?newCap?*?loadFactor ????????} ????????else?if?(oldThr?>?0)?//?第一次擴(kuò)容,并且用戶(hù)指定了初始容量 ????????????newCap?=?oldThr;?//?擴(kuò)展的容量為閾值 ????????else?{???????????????//?第一次擴(kuò)容,并且初始容量和加載因子使用的默認(rèn)值 ????????????newCap?=?DEFAULT_INITIAL_CAPACITY; ????????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY); ????????} ????????if?(newThr?==?0)?{??//?如果用戶(hù)指定了初始容量時(shí),并且是第一次擴(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ù)移動(dòng)到新數(shù)組 ????????????????Node<K,V>?e; ????????????????if?((e?=?oldTab[j])?!=?null)?{ ????????????????????oldTab[j]?=?null; ????????????????????if?(e.next?==?null)?//?如果還不是鏈表或紅黑樹(shù),把數(shù)據(jù)直接移動(dòng)到新數(shù)組中對(duì)應(yīng)位置 ????????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e; ????????????????????else?if?(e?instanceof?TreeNode)?//紅黑樹(shù)時(shí)的移動(dòng)數(shù)據(jù) ????????????????????????((TreeNode<K,V>)e).split(this,?newTab,?j,?oldCap); ????????????????????else?{?//?鏈表時(shí)移動(dòng)數(shù)據(jù) ????????????????????????//?原來(lái)的key的hash值對(duì)應(yīng)的數(shù)組位置可能會(huì)發(fā)生變化 ?????????????????????//?因?yàn)樵谧雠c操作時(shí),現(xiàn)有的數(shù)組長(zhǎng)度多了兩倍,也就是多了一位的與計(jì)算 ?????????????????????//?所以,鏈表或紅黑樹(shù)中的元素可能在原來(lái)位置,或者在原來(lái)位置?+?原來(lái)數(shù)組長(zhǎng)度?的位置 ????????????????????????Node<K,V>?loHead?=?null,?loTail?=?null; ????????????????????????Node<K,V>?hiHead?=?null,?hiTail?=?null; ????????????????????????Node<K,V>?next; ????????????????????????do?{ ????????????????????????....省略不分 ????????????????????} ????????????????} ????????????} ????????} ????????return?newTab; ????}
總的來(lái)說(shuō),擴(kuò)容就是創(chuàng)建一個(gè)新的數(shù)組,數(shù)組長(zhǎng)度為原來(lái)的兩倍,并將下一次需要擴(kuò)容的閾值設(shè)置為新數(shù)組乘以加載因子的大小。
然后將原來(lái)數(shù)組中的數(shù)據(jù)移動(dòng)到新數(shù)組中。
如果數(shù)組中的元素不是鏈表和紅黑樹(shù),那么直接移動(dòng)到原來(lái)舊數(shù)組中下標(biāo)的位置。
否則如果是鏈表或紅黑樹(shù),那么其中的數(shù)據(jù)可能會(huì)在原來(lái)的位置,或者在原來(lái)的位置+原來(lái)數(shù)組長(zhǎng)度的位置,此時(shí)將原來(lái)的鏈表或紅黑樹(shù)分為兩個(gè)鏈表或紅黑樹(shù),再把數(shù)據(jù)移動(dòng)到相應(yīng)位置。
到此這篇關(guān)于一文帶你解讀所有HashMap的面試題的文章就介紹到這了,更多相關(guān)HashMap面試題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java實(shí)現(xiàn)解析json復(fù)雜數(shù)據(jù)的方法詳解
這篇文章主要為大家詳細(xì)介紹了java如何實(shí)現(xiàn)解析json復(fù)雜數(shù)據(jù),文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,感興趣的小伙伴可以學(xué)習(xí)一下2024-01-01淺談Java中浮點(diǎn)型數(shù)據(jù)保留兩位小數(shù)的四種方法
今天在進(jìn)行開(kāi)發(fā)的過(guò)程中遇到了一個(gè)小問(wèn)題,是關(guān)于如何將double類(lèi)型的數(shù)據(jù)保留兩位小數(shù)。具有一定的參考價(jià)值,本文就詳細(xì)的介紹一下2021-09-09Java tomcat環(huán)境變量及idea配置解析
這篇文章主要介紹了Java tomcat環(huán)境變量及idea配置解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-12-12Spring Boot 使用 logback、logstash、ELK 記錄日志文件的方法
這篇文章主要介紹了Spring Boot 使用 logback、logstash、ELK 記錄日志文件的思路詳解,文中給大家提到了logback 取代 log4j的理由,需要的朋友可以參考下2017-12-12Springboot如何設(shè)置靜態(tài)資源緩存一年
這篇文章主要介紹了Springboot如何設(shè)置靜態(tài)資源緩存一年,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11詳談Java泛型中T和問(wèn)號(hào)(通配符)的區(qū)別
下面小編就為大家?guī)?lái)一篇詳談Java泛型中T和問(wèn)號(hào)(通配符)的區(qū)別。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-10-10部署springboot項(xiàng)目到云服務(wù)器的兩種方式(jar+war)
本文主要介紹了部署springboot項(xiàng)目到云服務(wù)器的兩種方式,主要介紹了jar和war兩種方式,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-12-12Java使用JSONObject需要的6個(gè)jar包下載地址
這篇文章主要介紹了Java使用JSONObject需要的6個(gè)jar包下載地址,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11Springboot項(xiàng)目對(duì)數(shù)據(jù)庫(kù)用戶(hù)名密碼實(shí)現(xiàn)加密過(guò)程解析
這篇文章主要介紹了Springboot項(xiàng)目對(duì)數(shù)據(jù)庫(kù)用戶(hù)名密碼實(shí)現(xiàn)加密過(guò)程解析,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-06-06