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