本篇內(nèi)容介紹了“HashMap常問的面試題有哪些”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

為安溪等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及安溪網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、安溪網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

(1)HashMap的實(shí)現(xiàn)原理?

此題可以組成如下連環(huán)炮來問

• 你看過HashMap源碼嘛，知道原理嘛?

• 為什么用數(shù)組+鏈表？

• hash沖突你還知道哪些解決辦法？

• 我用LinkedList代替數(shù)組結(jié)構(gòu)可以么?

• 既然是可以的,為什么HashMap不用LinkedList,而選用數(shù)組?

你看過HashMap源碼嘛，知道原理嘛?

針對(duì)這個(gè)問題，嗯，當(dāng)然是必須看過HashMap源碼。至于原理，下面那張圖很清楚了:

HashMap采用Entry數(shù)組來存儲(chǔ)key-value對(duì)，每一個(gè)鍵值對(duì)組成了一個(gè)Entry實(shí)體，Entry類實(shí)際上是一個(gè)單向的鏈表結(jié)構(gòu)，它具有Next指針，可以連接下一個(gè)Entry實(shí)體。

只是在JDK1.8中，鏈表長(zhǎng)度大于8的時(shí)候，鏈表會(huì)轉(zhuǎn)成紅黑樹！

為什么用數(shù)組+鏈表？

數(shù)組是用來確定桶的位置，利用元素的key的hash值對(duì)數(shù)組長(zhǎng)度取模得到.

鏈表是用來解決hash沖突問題，當(dāng)出現(xiàn)hash值一樣的情形，就在數(shù)組上的對(duì)應(yīng)位置形成一條鏈表。ps:這里的hash值并不是指hashcode，而是將hashcode高低十六位異或過的。至于為什么要這么做，繼續(xù)往下看。

hash沖突你還知道哪些解決辦法？

比較出名的有四種(1)開放定址法(2)鏈地址法(3)再哈希法(4)公共溢出區(qū)域法

ps:大家有興趣拓展的，自己去搜一下就懂了，這個(gè)就不拓展了！

我用LinkedList代替數(shù)組結(jié)構(gòu)可以么?

這里我稍微說明一下，此題的意思是，源碼中是這樣的

Entry[] table = new Entry[capacity];

ps：Entry就是一個(gè)鏈表節(jié)點(diǎn)。

那我用下面這樣表示

List<Entry> table = new LinkedList<Entry>();

是否可行?

答案很明顯，必須是可以的。

既然是可以的,為什么HashMap不用LinkedList,而選用數(shù)組?

因?yàn)橛脭?shù)組效率最高！

在HashMap中，定位桶的位置是利用元素的key的哈希值對(duì)數(shù)組長(zhǎng)度取模得到。此時(shí)，我們已得到桶的位置。顯然數(shù)組的查找效率比LinkedList大。

那ArrayList，底層也是數(shù)組，查找也快啊，為啥不用ArrayList?

(煙哥寫到這里的時(shí)候，不禁覺得自己真有想法，自己把自己?jiǎn)査懒?，還好我靈機(jī)一動(dòng)想出了答案)

因?yàn)椴捎没緮?shù)組結(jié)構(gòu)，擴(kuò)容機(jī)制可以自己定義，HashMap中數(shù)組擴(kuò)容剛好是2的次冪，在做取模運(yùn)算的效率高。

而ArrayList的擴(kuò)容機(jī)制是1.5倍擴(kuò)容，那ArrayList為什么是1.5倍擴(kuò)容這就不在本文說明了。

(2)HashMap在什么條件下擴(kuò)容?

此題可以組成如下連環(huán)炮來問

• HashMap在什么條件下擴(kuò)容?

• 為什么擴(kuò)容是2的n次冪?

• 為什么為什么要先高16位異或低16位再取模運(yùn)算?

HashMap在什么條件下擴(kuò)容?

如果bucket滿了(超過load factor*current capacity)，就要resize。

load factor為0.75，為了大程度避免哈希沖突

current capacity為當(dāng)前數(shù)組大小。

為什么擴(kuò)容是2的次冪?

HashMap為了存取高效，要盡量較少碰撞，就是要盡量把數(shù)據(jù)分配均勻，每個(gè)鏈表長(zhǎng)度大致相同，這個(gè)實(shí)現(xiàn)就在把數(shù)據(jù)存到哪個(gè)鏈表中的算法；這個(gè)算法實(shí)際就是取模，hash%length。

但是，大家都知道這種運(yùn)算不如位移運(yùn)算快。

因此，源碼中做了優(yōu)化hash&(length-1)。

也就是說hash%length==hash&(length-1)

那為什么是2的n次方呢？

因?yàn)?的n次方實(shí)際就是1后面n個(gè)0，2的n次方-1，實(shí)際就是n個(gè)1。

例如長(zhǎng)度為8時(shí)候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞。

而長(zhǎng)度為5的時(shí)候，3&(5-1)=0 2&(5-1)=0，都在0上，出現(xiàn)碰撞了。

所以，保證容積是2的n次方，是為了保證在做(length-1)的時(shí)候，每一位都能&1 ，也就是和1111……1111111進(jìn)行與運(yùn)算。

為什么為什么要先高16位異或低16位再取模運(yùn)算?

我先曬一下，jdk1.8里的hash方法。1.7的比較復(fù)雜，咱就不看了。

hashmap這么做，只是為了降低hash沖突的幾率。

打個(gè)比方，當(dāng)我們的length為16的時(shí)候，哈希碼(字符串“abcabcabcabcabc”的key對(duì)應(yīng)的哈希碼)對(duì)(16-1)與操作，對(duì)于多個(gè)key生成的hashCode，只要哈希碼的后4位為0，不論不論高位怎么變化，最終的結(jié)果均為0。

如下圖所示

而加上高16位異或低16位的“擾動(dòng)函數(shù)”后，結(jié)果如下

可以看到: 擾動(dòng)函數(shù)優(yōu)化前：1954974080 % 16 = 1954974080 & (16 - 1) = 0 擾動(dòng)函數(shù)優(yōu)化后：1955003654 % 16 = 1955003654 & (16 - 1) = 6 很顯然，減少了碰撞的幾率。

(3)講講hashmap的get/put的過程?

此題可以組成如下連環(huán)炮來問

• 知道hashmap中put元素的過程是什么樣么?

• 知道hashmap中g(shù)et元素的過程是什么樣么？

• 你還知道哪些hash算法？

• 說說String中hashcode的實(shí)現(xiàn)?(此題很多大廠問過)

知道hashmap中put元素的過程是什么樣么?

對(duì)key的hashCode()做hash運(yùn)算，計(jì)算index;

如果沒碰撞直接放到bucket里；

如果碰撞了，以鏈表的形式存在buckets后；

如果碰撞導(dǎo)致鏈表過長(zhǎng)(大于等于TREEIFY_THRESHOLD)，就把鏈表轉(zhuǎn)換成紅黑樹(JDK1.8中的改動(dòng))；

如果節(jié)點(diǎn)已經(jīng)存在就替換old value(保證key的唯一性)

如果bucket滿了(超過load factor*current capacity)，就要resize。

知道hashmap中g(shù)et元素的過程是什么樣么?

對(duì)key的hashCode()做hash運(yùn)算，計(jì)算index;

如果在bucket里的第一個(gè)節(jié)點(diǎn)里直接命中，則直接返回；

如果有沖突，則通過key.equals(k)去查找對(duì)應(yīng)的Entry;

• 若為樹，則在樹中通過key.equals(k)查找，O(logn)；

• 若為鏈表，則在鏈表中通過key.equals(k)查找，O(n)。

你還知道哪些hash算法？

先說一下hash算法干嘛的，Hash函數(shù)是指把一個(gè)大范圍映射到一個(gè)小范圍。把大范圍映射到一個(gè)小范圍的目的往往是為了節(jié)省空間，使得數(shù)據(jù)容易保存。

比較出名的有MurmurHash、MD4、MD5等等

說說String中hashcode的實(shí)現(xiàn)?(此題頻率很高)

public int hashCode() {
 int h = hash;
 if (h == 0 && value.length > 0) {
 char val[] = value;
 for (int i = 0; i < value.length; i++) {
 h = 31 * h + val[i];
 }
 hash = h;
 }
 return h;
}

String類中的hashCode計(jì)算方法還是比較簡(jiǎn)單的，就是以31為權(quán)，每一位為字符的ASCII值進(jìn)行運(yùn)算，用自然溢出來等效取模。

哈希計(jì)算公式可以計(jì)為s[0]31^(n-1) + s[1]31^(n-2) + … + s[n-1]

那為什么以31為質(zhì)數(shù)呢?

主要是因?yàn)?1是一個(gè)奇質(zhì)數(shù)，所以31*i=32*i-i=(i<<5)-i，這種位移與減法結(jié)合的計(jì)算相比一般的運(yùn)算快很多。

(4)為什么hashmap的在鏈表元素?cái)?shù)量超過8時(shí)改為紅黑樹?

此題可以組成如下連環(huán)炮來問

• 知道jdk1.8中hashmap改了啥么?

• 為什么在解決hash沖突的時(shí)候，不直接用紅黑樹?而選擇先用鏈表，再轉(zhuǎn)紅黑樹?

• 我不用紅黑樹，用二叉查找樹可以么?

• 那為什么閥值是8呢?

• 當(dāng)鏈表轉(zhuǎn)為紅黑樹后，什么時(shí)候退化為鏈表?

知道jdk1.8中hashmap改了啥么?

• 由數(shù)組+鏈表的結(jié)構(gòu)改為數(shù)組+鏈表+紅黑樹。

• 優(yōu)化了高位運(yùn)算的hash算法：h^(h>>>16)

• 擴(kuò)容后，元素要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置，且鏈表順序不變。

最后一條是重點(diǎn)，因?yàn)樽詈笠粭l的變動(dòng)，hashmap在1.8中，不會(huì)在出現(xiàn)死循環(huán)問題。

為什么在解決hash沖突的時(shí)候，不直接用紅黑樹?而選擇先用鏈表，再轉(zhuǎn)紅黑樹?

因?yàn)榧t黑樹需要進(jìn)行左旋，右旋，變色這些操作來保持平衡，而單鏈表不需要。

當(dāng)元素小于8個(gè)當(dāng)時(shí)候，此時(shí)做查詢操作，鏈表結(jié)構(gòu)已經(jīng)能保證查詢性能。當(dāng)元素大于8個(gè)的時(shí)候，此時(shí)需要紅黑樹來加快查詢速度，但是新增節(jié)點(diǎn)的效率變慢了。

因此，如果一開始就用紅黑樹結(jié)構(gòu)，元素太少，新增效率又比較慢，無疑這是浪費(fèi)性能的。

我不用紅黑樹，用二叉查找樹可以么?

可以。但是二叉查找樹在特殊情況下會(huì)變成一條線性結(jié)構(gòu)（這就跟原來使用鏈表結(jié)構(gòu)一樣了，造成很深的問題），遍歷查找會(huì)非常慢。

那為什么閥值是8呢?

不知道，等jdk作者來回答。

這道題，網(wǎng)上能找到的答案都是扯淡。

我隨便貼一網(wǎng)的答案，如下圖所示

看出bug沒？交點(diǎn)是6.64？交點(diǎn)分明是4，好么。

log4=2，4/2=2。

jdk作者選擇8，一定經(jīng)過了嚴(yán)格的運(yùn)算，覺得在長(zhǎng)度為8的時(shí)候，與其保證鏈表結(jié)構(gòu)的查找開銷，不如轉(zhuǎn)換為紅黑樹，改為維持其平衡開銷。

當(dāng)鏈表轉(zhuǎn)為紅黑樹后，什么時(shí)候退化為鏈表?

為6的時(shí)候退轉(zhuǎn)為鏈表。中間有個(gè)差值7可以防止鏈表和樹之間頻繁的轉(zhuǎn)換。假設(shè)一下，如果設(shè)計(jì)成鏈表個(gè)數(shù)超過8則鏈表轉(zhuǎn)換成樹結(jié)構(gòu)，鏈表個(gè)數(shù)小于8則樹結(jié)構(gòu)轉(zhuǎn)換成鏈表，如果一個(gè)HashMap不停的插入、刪除元素，鏈表個(gè)數(shù)在8左右徘徊，就會(huì)頻繁的發(fā)生樹轉(zhuǎn)鏈表、鏈表轉(zhuǎn)樹，效率會(huì)很低。

(5)HashMap的并發(fā)問題?

此題可以組成如下連環(huán)炮來問

• HashMap在并發(fā)編程環(huán)境下有什么問題啊?

• 在jdk1.8中還有這些問題么?

• 你一般怎么解決這些問題的？

HashMap在并發(fā)編程環(huán)境下有什么問題啊?

• (1)多線程擴(kuò)容，引起的死循環(huán)問題

• (2)多線程put的時(shí)候可能導(dǎo)致元素丟失

• (3)put非null元素后get出來的卻是null

在jdk1.8中還有這些問題么?

在jdk1.8中，死循環(huán)問題已經(jīng)解決。其他兩個(gè)問題還是存在。

你一般怎么解決這些問題的？

比如ConcurrentHashmap，Hashtable等線程安全等集合類。

(6)你一般用什么作為HashMap的key?

此題可以組成如下連環(huán)炮來問

• 健可以為Null值么?

• 你一般用什么作為HashMap的key?

• 我用可變類當(dāng)HashMap的key有什么問題?

• 如果讓你實(shí)現(xiàn)一個(gè)自定義的class作為HashMap的key該如何實(shí)現(xiàn)？

健可以為Null值么?

必須可以，key為null的時(shí)候，hash算法最后的值以0來計(jì)算，也就是放在數(shù)組的第一個(gè)位置。

你一般用什么作為HashMap的key?

一般用Integer、String這種不可變類當(dāng)HashMap當(dāng)key，而且String最為常用。

• (1)因?yàn)樽址遣豢勺兊?，所以在它?chuàng)建的時(shí)候hashcode就被緩存了，不需要重新計(jì)算。這就使得字符串很適合作為Map中的鍵，字符串的處理速度要快過其它的鍵對(duì)象。這就是HashMap中的鍵往往都使用字符串。

• (2)因?yàn)楂@取對(duì)象的時(shí)候要用到equals()和hashCode()方法，那么鍵對(duì)象正確的重寫這兩個(gè)方法是非常重要的,這些類已經(jīng)很規(guī)范的覆寫了hashCode()以及equals()方法。

我用可變類當(dāng)HashMap的key有什么問題?

hashcode可能發(fā)生改變，導(dǎo)致put進(jìn)去的值，無法get出，如下所示

HashMap<List<String>, Object> changeMap = new HashMap<>();
List<String> list = new ArrayList<>();
list.add("hello");
Object objectValue = new Object();
changeMap.put(list, objectValue);
System.out.println(changeMap.get(list));
list.add("hello world");//hashcode發(fā)生了改變
System.out.println(changeMap.get(list));

輸出值如下

java.lang.Object@74a14482
null

如果讓你實(shí)現(xiàn)一個(gè)自定義的class作為HashMap的key該如何實(shí)現(xiàn)？

此題考察兩個(gè)知識(shí)點(diǎn)

• 重寫hashcode和equals方法注意什么?

• 如何設(shè)計(jì)一個(gè)不變類

針對(duì)問題一，記住下面四個(gè)原則即可

(1)兩個(gè)對(duì)象相等，hashcode一定相等

(2)兩個(gè)對(duì)象不等，hashcode不一定不等

(3)hashcode相等，兩個(gè)對(duì)象不一定相等

(4)hashcode不等，兩個(gè)對(duì)象一定不等

針對(duì)問題二，記住如何寫一個(gè)不可變類

(1)類添加final修飾符，保證類不被繼承。

如果類可以被繼承會(huì)破壞類的不可變性機(jī)制，只要繼承類覆蓋父類的方法并且繼承類可以改變成員變量值，那么一旦子類以父類的形式出現(xiàn)時(shí)，不能保證當(dāng)前類是否可變。

(2)保證所有成員變量必須私有，并且加上final修飾

通過這種方式保證成員變量不可改變。但只做到這一步還不夠，因?yàn)槿绻菍?duì)象成員變量有可能再外部改變其值。所以第4點(diǎn)彌補(bǔ)這個(gè)不足。

(3)不提供改變成員變量的方法，包括setter

避免通過其他接口改變成員變量的值，破壞不可變特性。

(4)通過構(gòu)造器初始化所有成員，進(jìn)行深拷貝(deep copy)

如果構(gòu)造器傳入的對(duì)象直接賦值給成員變量，還是可以通過對(duì)傳入對(duì)象的修改進(jìn)而導(dǎo)致改變內(nèi)部變量的值。例如：

public final class ImmutableDemo { 
 private final int[] myArray; 
 public ImmutableDemo(int[] array) { 
 this.myArray = array; // wrong 
 } 
}

這種方式不能保證不可變性，myArray和array指向同一塊內(nèi)存地址，用戶可以在ImmutableDemo之外通過修改array對(duì)象的值來改變myArray內(nèi)部的值。

為了保證內(nèi)部的值不被修改，可以采用深度copy來創(chuàng)建一個(gè)新內(nèi)存保存?zhèn)魅氲闹?。正確做法：

public final class MyImmutableDemo { 
 private final int[] myArray; 
 public MyImmutableDemo(int[] array) { 
 this.myArray = array.clone(); 
 } 
}

(5)在getter方法中，不要直接返回對(duì)象本身，而是克隆對(duì)象，并返回對(duì)象的拷貝

這種做法也是防止對(duì)象外泄，防止通過getter獲得內(nèi)部可變成員對(duì)象后對(duì)成員變量直接操作，導(dǎo)致成員變量發(fā)生改變。

“HashMap常問的面試題有哪些”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享文章：HashMap常問的面試題有哪些-創(chuàng)新互聯(lián)
本文URL：http://aaarwkj.com/article38/cogpsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、服務(wù)器托管、微信公眾號(hào)、靜態(tài)網(wǎng)站、ChatGPT、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)