99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

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

創(chuàng)新互聯(lián)主營海西網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,app軟件開發(fā),海西h5微信小程序搭建,海西網(wǎng)站營銷推廣歡迎海西等地區(qū)企業(yè)咨詢

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

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

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

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

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

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

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

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

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

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

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

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

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

鏈表是用來解決hash沖突問題，當(dāng)出現(xiàn)hash值一樣的情形，就在數(shù)組上的對應(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 table = new LinkedList();

是否可行?

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

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

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

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

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

(煙哥寫到這里的時(shí)候，不禁覺得自己真有想法，自己把自己問死了，還好我靈機(jī)一動想出了答案)

因?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è)鏈表長度大致相同，這個(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。

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

而長度為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對應(yīng)的哈希碼)對(16-1)與操作，對于多個(gè)key生成的hashCode，只要哈希碼的后4位為0，不論不論高位怎么變化，最終的結(jié)果均為0。

如下圖所示

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

可以看到: 擾動函數(shù)優(yōu)化前：1954974080 % 16 = 1954974080 & (16 - 1) = 0 擾動函數(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元素的過程是什么樣么?

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

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

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

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

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

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

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

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

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

如果有沖突，則通過key.equals(k)去查找對應(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ì)算方法還是比較簡單的，就是以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ò)容后，元素要么是在原位置，要么是在原位置再移動2次冪的位置，且鏈表順序不變。

最后一條是重點(diǎn)，因?yàn)樽詈笠粭l的變動，hashmap在1.8中，不會在出現(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)性能的。

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

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

那為什么閥值是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)算，覺得在長度為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左右徘徊，就會頻繁的發(fā)生樹轉(zhuǎn)鏈表、鏈表轉(zhuǎn)樹，效率會很低。

(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中的鍵，字符串的處理速度要快過其它的鍵對象。這就是HashMap中的鍵往往都使用字符串。

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

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

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

HashMap, Object> changeMap = new HashMap<>();
List 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è)知識點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如果構(gòu)造器傳入的對象直接賦值給成員變量，還是可以通過對傳入對象的修改進(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對象的值來改變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方法中，不要直接返回對象本身，而是克隆對象，并返回對象的拷貝

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

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

新聞標(biāo)題：HashMap常問的面試題有哪些
當(dāng)前鏈接：http://ef60e0e.cn/article/gsjjsi.html