本篇內(nèi)容介紹了“HashMap常問(wèn)的面試題有哪些”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
創(chuàng)新互聯(lián)主營(yíng)海西網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,app軟件開(kāi)發(fā),海西h5微信小程序搭建,海西網(wǎng)站營(yíng)銷推廣歡迎海西等地區(qū)企業(yè)咨詢
(1)HashMap的實(shí)現(xiàn)原理?
此題可以組成如下連環(huán)炮來(lái)問(wèn)
你看過(guò)HashMap源碼嘛，知道原理嘛?
為什么用數(shù)組+鏈表？
hash沖突你還知道哪些解決辦法？
我用LinkedList代替數(shù)組結(jié)構(gòu)可以么?
既然是可以的,為什么HashMap不用LinkedList,而選用數(shù)組?
你看過(guò)HashMap源碼嘛，知道原理嘛?
針對(duì)這個(gè)問(wèn)題，嗯，當(dāng)然是必須看過(guò)HashMap源碼。至于原理，下面那張圖很清楚了:
HashMap采用Entry數(shù)組來(lái)存儲(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ù)組+鏈表？
數(shù)組是用來(lái)確定桶的位置，利用元素的key的hash值對(duì)數(shù)組長(zhǎng)度取模得到.
鏈表是用來(lái)解決hash沖突問(wèn)題，當(dāng)出現(xiàn)hash值一樣的情形，就在數(shù)組上的對(duì)應(yīng)位置形成一條鏈表。ps:這里的hash值并不是指hashcode，而是將hashcode高低十六位異或過(guò)的。至于為什么要這么做，繼續(xù)往下看。
hash沖突你還知道哪些解決辦法？
比較出名的有四種(1)開(kāi)放定址法(2)鏈地址法(3)再哈希法(4)公共溢出區(qū)域法
ps:大家有興趣拓展的，自己去搜一下就懂了，這個(gè)就不拓展了！
我用LinkedList代替數(shù)組結(jié)構(gòu)可以么?
這里我稍微說(shuō)明一下，此題的意思是，源碼中是這樣的
Entry[] table = new Entry[capacity];
ps：Entry就是一個(gè)鏈表節(jié)點(diǎn)。
那我用下面這樣表示
Listtable = new LinkedList ();
是否可行?
答案很明顯，必須是可以的。
既然是可以的,為什么HashMap不用LinkedList,而選用數(shù)組?
因?yàn)橛脭?shù)組效率最高！
在HashMap中，定位桶的位置是利用元素的key的哈希值對(duì)數(shù)組長(zhǎng)度取模得到。此時(shí)，我們已得到桶的位置。顯然數(shù)組的查找效率比LinkedList大。
那ArrayList，底層也是數(shù)組，查找也快啊，為啥不用ArrayList?
(煙哥寫(xiě)到這里的時(shí)候，不禁覺(jué)得自己真有想法，自己把自己?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ò)容這就不在本文說(shuō)明了。
(2)HashMap在什么條件下擴(kuò)容?
此題可以組成如下連環(huán)炮來(lái)問(wèn)
HashMap在什么條件下擴(kuò)容?
為什么擴(kuò)容是2的n次冪?
為什么為什么要先高16位異或低16位再取模運(yùn)算?
HashMap在什么條件下擴(kuò)容?
如果bucket滿了(超過(guò)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)。
也就是說(shuō)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的過(guò)程?
此題可以組成如下連環(huán)炮來(lái)問(wèn)
知道hashmap中put元素的過(guò)程是什么樣么?
知道hashmap中g(shù)et元素的過(guò)程是什么樣么？
你還知道哪些hash算法？
說(shuō)說(shuō)String中hashcode的實(shí)現(xiàn)?(此題很多大廠問(wèn)過(guò))
知道hashmap中put元素的過(guò)程是什么樣么?
對(duì)key的hashCode()做hash運(yùn)算，計(jì)算index;
如果沒(méi)碰撞直接放到bucket里；
如果碰撞了，以鏈表的形式存在buckets后；
如果碰撞導(dǎo)致鏈表過(guò)長(zhǎng)(大于等于TREEIFY_THRESHOLD)，就把鏈表轉(zhuǎn)換成紅黑樹(shù)(JDK1.8中的改動(dòng))；
如果節(jié)點(diǎn)已經(jīng)存在就替換old value(保證key的唯一性)
如果bucket滿了(超過(guò)load factor*current capacity)，就要resize。
知道hashmap中g(shù)et元素的過(guò)程是什么樣么?
對(duì)key的hashCode()做hash運(yùn)算，計(jì)算index;
如果在bucket里的第一個(gè)節(jié)點(diǎn)里直接命中，則直接返回；
如果有沖突，則通過(guò)key.equals(k)去查找對(duì)應(yīng)的Entry;
若為樹(shù)，則在樹(shù)中通過(guò)key.equals(k)查找，O(logn)；
若為鏈表，則在鏈表中通過(guò)key.equals(k)查找，O(n)。
你還知道哪些hash算法？
先說(shuō)一下hash算法干嘛的，Hash函數(shù)是指把一個(gè)大范圍映射到一個(gè)小范圍。把大范圍映射到一個(gè)小范圍的目的往往是為了節(jié)省空間，使得數(shù)據(jù)容易保存。
比較出名的有MurmurHash、MD4、MD5等等
說(shuō)說(shuō)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)算，用自然溢出來(lái)等效取模。
哈希計(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ù)量超過(guò)8時(shí)改為紅黑樹(shù)?
此題可以組成如下連環(huán)炮來(lái)問(wèn)
知道jdk1.8中hashmap改了啥么?
為什么在解決hash沖突的時(shí)候，不直接用紅黑樹(shù)?而選擇先用鏈表，再轉(zhuǎn)紅黑樹(shù)?
我不用紅黑樹(shù)，用二叉查找樹(shù)可以么?
那為什么閥值是8呢?
當(dāng)鏈表轉(zhuǎn)為紅黑樹(shù)后，什么時(shí)候退化為鏈表?
知道jdk1.8中hashmap改了啥么?
由數(shù)組+鏈表的結(jié)構(gòu)改為數(shù)組+鏈表+紅黑樹(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)問(wèn)題。
為什么在解決hash沖突的時(shí)候，不直接用紅黑樹(shù)?而選擇先用鏈表，再轉(zhuǎn)紅黑樹(shù)?
因?yàn)榧t黑樹(shù)需要進(jìn)行左旋，右旋，變色這些操作來(lái)保持平衡，而單鏈表不需要。
當(dāng)元素小于8個(gè)當(dāng)時(shí)候，此時(shí)做查詢操作，鏈表結(jié)構(gòu)已經(jīng)能保證查詢性能。當(dāng)元素大于8個(gè)的時(shí)候，此時(shí)需要紅黑樹(shù)來(lái)加快查詢速度，但是新增節(jié)點(diǎn)的效率變慢了。
因此，如果一開(kāi)始就用紅黑樹(shù)結(jié)構(gòu)，元素太少，新增效率又比較慢，無(wú)疑這是浪費(fèi)性能的。
我不用紅黑樹(shù)，用二叉查找樹(shù)可以么?
可以。但是二叉查找樹(shù)在特殊情況下會(huì)變成一條線性結(jié)構(gòu)（這就跟原來(lái)使用鏈表結(jié)構(gòu)一樣了，造成很深的問(wèn)題），遍歷查找會(huì)非常慢。
那為什么閥值是8呢?
不知道，等jdk作者來(lái)回答。
這道題，網(wǎng)上能找到的答案都是扯淡。
我隨便貼一網(wǎng)的答案，如下圖所示
看出bug沒(méi)？交點(diǎn)是6.64？交點(diǎn)分明是4，好么。
log4=2，4/2=2。
jdk作者選擇8，一定經(jīng)過(guò)了嚴(yán)格的運(yùn)算，覺(jué)得在長(zhǎng)度為8的時(shí)候，與其保證鏈表結(jié)構(gòu)的查找開(kāi)銷，不如轉(zhuǎn)換為紅黑樹(shù)，改為維持其平衡開(kāi)銷。
當(dāng)鏈表轉(zhuǎn)為紅黑樹(shù)后，什么時(shí)候退化為鏈表?
為6的時(shí)候退轉(zhuǎn)為鏈表。中間有個(gè)差值7可以防止鏈表和樹(shù)之間頻繁的轉(zhuǎn)換。假設(shè)一下，如果設(shè)計(jì)成鏈表個(gè)數(shù)超過(guò)8則鏈表轉(zhuǎn)換成樹(shù)結(jié)構(gòu)，鏈表個(gè)數(shù)小于8則樹(shù)結(jié)構(gòu)轉(zhuǎn)換成鏈表，如果一個(gè)HashMap不停的插入、刪除元素，鏈表個(gè)數(shù)在8左右徘徊，就會(huì)頻繁的發(fā)生樹(shù)轉(zhuǎn)鏈表、鏈表轉(zhuǎn)樹(shù)，效率會(huì)很低。
(5)HashMap的并發(fā)問(wèn)題?
此題可以組成如下連環(huán)炮來(lái)問(wèn)
HashMap在并發(fā)編程環(huán)境下有什么問(wèn)題啊?
在jdk1.8中還有這些問(wèn)題么?
你一般怎么解決這些問(wèn)題的？
HashMap在并發(fā)編程環(huán)境下有什么問(wèn)題啊?
(1)多線程擴(kuò)容，引起的死循環(huán)問(wèn)題
(2)多線程put的時(shí)候可能導(dǎo)致元素丟失
(3)put非null元素后get出來(lái)的卻是null
在jdk1.8中還有這些問(wèn)題么?
在jdk1.8中，死循環(huán)問(wèn)題已經(jīng)解決。其他兩個(gè)問(wèn)題還是存在。
你一般怎么解決這些問(wèn)題的？
比如ConcurrentHashmap，Hashtable等線程安全等集合類。
(6)你一般用什么作為HashMap的key?
此題可以組成如下連環(huán)炮來(lái)問(wèn)
健可以為Null值么?
你一般用什么作為HashMap的key?
我用可變類當(dāng)HashMap的key有什么問(wèn)題?
如果讓你實(shí)現(xiàn)一個(gè)自定義的class作為HashMap的key該如何實(shí)現(xiàn)？
健可以為Null值么?
必須可以，key為null的時(shí)候，hash算法最后的值以0來(lái)計(jì)算，也就是放在數(shù)組的第一個(gè)位置。
你一般用什么作為HashMap的key?
一般用Integer、String這種不可變類當(dāng)HashMap當(dāng)key，而且String最為常用。
(1)因?yàn)樽址遣豢勺兊?，所以在它?chuàng)建的時(shí)候hashcode就被緩存了，不需要重新計(jì)算。這就使得字符串很適合作為Map中的鍵，字符串的處理速度要快過(guò)其它的鍵對(duì)象。這就是HashMap中的鍵往往都使用字符串。
(2)因?yàn)楂@取對(duì)象的時(shí)候要用到equals()和hashCode()方法，那么鍵對(duì)象正確的重寫(xiě)這兩個(gè)方法是非常重要的,這些類已經(jīng)很規(guī)范的覆寫(xiě)了hashCode()以及equals()方法。
我用可變類當(dāng)HashMap的key有什么問(wèn)題?
hashcode可能發(fā)生改變，導(dǎo)致put進(jìn)去的值，無(wú)法get出，如下所示
