1. HashMap的底層數(shù)據(jù)結(jié)構(gòu)是什么？

在JDK1.7中和JDK1.8中有所區(qū)別：

在JDK1.7中，由”數(shù)組+鏈表“組成，數(shù)組是HashMap的主體，鏈表則是主要為了解決哈希沖突而存在的。

在JDK1.8中，有“數(shù)組+鏈表+紅黑樹”組成。當(dāng)鏈表過長，則會嚴(yán)重影響HashMap的性能，紅黑樹搜索時間復(fù)雜度是O(logn)，而鏈表是O(n)。因此，JDK1.8對數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化，引入了紅黑樹，鏈表和紅黑樹在達(dá)到一定條件會進(jìn)行轉(zhuǎn)換：

• 當(dāng)鏈表超過8且數(shù)組長度(數(shù)據(jù)總量)超過64才會轉(zhuǎn)為紅黑樹
• 將鏈表轉(zhuǎn)換成紅黑樹前會判斷，如果當(dāng)前數(shù)組的長度小于64，那么會選擇先進(jìn)行數(shù)組擴(kuò)容，而不是轉(zhuǎn)換為紅黑樹，以減少搜索時間。

2. 說一下HashMap的特點(diǎn)

• hashmap存取是無序的
• 鍵和值位置都可以是null，但是鍵位置只能是一個null
• 鍵位置是唯一的，底層的數(shù)據(jù)結(jié)構(gòu)是控制鍵的
• jdk1.8前數(shù)據(jù)結(jié)構(gòu)是：鏈表+數(shù)組jdk1.8之后是：數(shù)組+鏈表+紅黑樹
• 閾值（邊界值）>8并且數(shù)組長度大于64，才將鏈表轉(zhuǎn)換成紅黑樹，變成紅黑樹的目的是提高搜索速度，高效查詢

3. 解決hash沖突的辦法有哪些?HashMap用的哪種？

解決Hash沖突方法有：開放定址法、再哈希法、鏈地址法（HashMap中常見的拉鏈法）、簡歷公共溢出區(qū)。HashMap中采用的是鏈地址法。

• 開放定址法也稱為再散列法，基本思想就是，如果p=H(key)出現(xiàn)沖突時，則以p為基礎(chǔ)，再次hash，p1=H(p)，如果p1再次出現(xiàn)沖突，則以p1為基礎(chǔ)，以此類推，直到找到一個不沖突的哈希地址pi。因此開放定址法所需要的hash表的長度要大于等于所需要存放的元素，而且因?yàn)榇嬖谠俅蝖ash，所以只能在刪除的節(jié)點(diǎn)上做標(biāo)記，而不能真正刪除節(jié)點(diǎn)
• 再哈希法（雙重散列，多重散列），提供多個不同的hash函數(shù)，R1=H1(key1)發(fā)生沖突時，再計算R2=H2（key1），直到?jīng)]有沖突為止。這樣做雖然不易產(chǎn)生堆集，但增加了計算的時間。
• 鏈地址法（拉鏈法），將哈希值相同的元素構(gòu)成一個同義詞的單鏈表，并將單鏈表的頭指針存放在哈希表的第i個單元中，查找、插入和刪除主要在同義詞鏈表中進(jìn)行，鏈表法適用于經(jīng)常進(jìn)行插入和刪除的情況。
• 建立公共溢出區(qū)，將哈希表分為公共表和溢出表，當(dāng)溢出發(fā)生時，將所有溢出數(shù)據(jù)統(tǒng)一放到溢出區(qū)

注意開放定址法和再哈希法的區(qū)別是

• 開放定址法只能使用同一種hash函數(shù)進(jìn)行再次hash，再哈希法可以調(diào)用多種不同的hash函數(shù)進(jìn)行再次hash

4. 為什么要在數(shù)組長度大于64之后，鏈表才會進(jìn)化為紅黑樹

在數(shù)組比較小時如果出現(xiàn)紅黑樹結(jié)構(gòu)，反而會降低效率，而紅黑樹需要進(jìn)行左旋右旋，變色，這些操作來保持平衡，同時數(shù)組長度小于64時，搜索時間相對要快些，總之是為了加快搜索速度，提高性能

JDK1.8以前HashMap的實(shí)現(xiàn)是數(shù)組+鏈表，即使哈希函數(shù)取得再好，也很難達(dá)到元素百分百均勻分布。當(dāng)HashMap中有大量的元素都存放在同一個桶中時，這個桶下有一條長長的鏈表，此時HashMap就相當(dāng)于單鏈表，假如單鏈表有n個元素，遍歷的時間復(fù)雜度就從O（1）退化成O（n），完全失去了它的優(yōu)勢，為了解決此種情況，JDK1.8中引入了紅黑樹（查找的時間復(fù)雜度為O（logn））來優(yōu)化這種問題

5. 為什么加載因子設(shè)置為0.75，初始化臨界值是12？

HashMap中的threshold是HashMap所能容納鍵值對的最大值。計算公式為length*LoadFactory。也就是說，在數(shù)組定義好長度之后，負(fù)載因子越大，所能容納的鍵值對個數(shù)也越大

loadFactory越趨近于1，那么數(shù)組中存放的數(shù)據(jù)（entry也就越來越多），數(shù)據(jù)也就越密集，也就會有更多的鏈表長度處于更長的數(shù)值，我們的查詢效率就會越低，當(dāng)我們添加數(shù)據(jù)，產(chǎn)生hash沖突的概率也會更高

默認(rèn)的loadFactory是0.75，loadFactory越小，越趨近于0，數(shù)組中個存放的數(shù)據(jù)(entry)也就越少，表現(xiàn)得更加稀疏

0.75是對空間和時間效率的一種平衡選擇

如果負(fù)載因子小一些比如是0.4，那么初始長度16*0.4=6，數(shù)組占滿6個空間就進(jìn)行擴(kuò)容，很多空間可能元素很少甚至沒有元素，會造成大量的空間被浪費(fèi)

如果負(fù)載因子大一些比如是0.9，這樣會導(dǎo)致擴(kuò)容之前查找元素的效率非常低

loadfactory設(shè)置為0.75是經(jīng)過多重計算檢驗(yàn)得到的可靠值，可以最大程度的減少rehash的次數(shù)，避免過多的性能消耗

6. 哈希表底層采用何種算法計算hash值？還有哪些算法可以計算出hash值？

hashCode方法是Object中的方法，所有的類都可以對其進(jìn)行使用，首先底層通過調(diào)用hashCode方法生成初始hash值h1，然后將h1無符號右移16位得到h2，之后將h1與h2進(jìn)行按位異或（^）運(yùn)算得到最終hash值h3，之后將h3與(length-1)進(jìn)行按位與（&）運(yùn)算得到hash表索引

其他可以計算出hash值的算法有

• 平方取中法
• 取余數(shù)
• 偽隨機(jī)數(shù)法

7. 當(dāng)兩個對象的hashCode相等時會怎樣

hashCode相等產(chǎn)生hash碰撞，hashCode相等會調(diào)用equals方法比較內(nèi)容是否相等，內(nèi)容如果相等則會進(jìn)行覆蓋，內(nèi)容如果不等則會連接到鏈表后方，鏈表長度超過8且數(shù)組長度超過64，會轉(zhuǎn)變成紅黑樹節(jié)點(diǎn)

8. 何時發(fā)生哈希碰撞和什么是哈希碰撞，如何解決哈希碰撞？

只要兩個元素的key計算的hash碼值相同就會發(fā)生hash碰撞，jdk8之前使用鏈表解決哈希碰撞，jdk8之后使用鏈表+紅黑樹解決哈希碰撞

9. HashMap的put方法流程

以jdk8為例，簡要流程如下：

1. 首先根據(jù)key的值計算hash值，找到該元素在數(shù)組中存儲的下標(biāo)
2. 如果數(shù)組是空的，則調(diào)用resize進(jìn)行初始化；
3. 如果沒有哈希沖突直接放在對應(yīng)的數(shù)組下標(biāo)里
4. 如果沖突了，且key已經(jīng)存在，就覆蓋掉value
5. 如果沖突后是鏈表結(jié)構(gòu)，就判斷該鏈表是否大于8，如果大于8并且數(shù)組容量小于64，就進(jìn)行擴(kuò)容；如果鏈表節(jié)點(diǎn)數(shù)量大于8并且數(shù)組的容量大于64，則將這個結(jié)構(gòu)轉(zhuǎn)換成紅黑樹；否則，鏈表插入鍵值對，若key存在，就覆蓋掉value
6. 如果沖突后，發(fā)現(xiàn)該節(jié)點(diǎn)是紅黑樹，就將這個節(jié)點(diǎn)掛在樹上

10. HashMap的擴(kuò)容方式

HashMap在容量超過負(fù)載因子所定義的容量之后，就會擴(kuò)容。java里的數(shù)組是無法自己擴(kuò)容的，將HashMap的大小擴(kuò)大為原來數(shù)組的兩倍

我們來看jdk1.8擴(kuò)容的源碼

????final?Node[]?resize()?{
????????//oldTab：引用擴(kuò)容前的哈希表
????????Node[]?oldTab?=?table;
????????//oldCap：表示擴(kuò)容前的table數(shù)組的長度
????????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;
????????//獲得舊哈希表的擴(kuò)容閾值
????????int?oldThr?=?threshold;
????????//newCap:擴(kuò)容之后table數(shù)組大小
????????//newThr:擴(kuò)容之后下次觸發(fā)擴(kuò)容的條件
????????int?newCap,?newThr?=?0;
????????//條件成立說明hashMap中的散列表已經(jīng)初始化過了，是一次正常擴(kuò)容
????????if?(oldCap?>?0)?{
????????????//判斷舊的容量是否大于等于最大容量，如果是，則無法擴(kuò)容，并且設(shè)置擴(kuò)容條件為int最大值，
????????????//這種情況屬于非常少數(shù)的情況
????????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{
????????????????threshold?=?Integer.MAX_VALUE;
????????????????return?oldTab;
????????????}//設(shè)置newCap新容量為oldCap舊容量的二倍（<<1）,并且<最大容量，而且>=16，則新閾值等于舊閾值的兩倍
????????????else?if?((newCap?=?oldCap?<?????????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????????newThr?=?oldThr?<????????}
????????//如果oldCap=0并且邊界值大于0，說明散列表是null，但此時oldThr>0
????????//說明此時hashMap的創(chuàng)建是通過指定的構(gòu)造方法創(chuàng)建的,新容量直接等于閾值
????????//1.new?HashMap(intitCap,loadFactor)
????????//2.new?HashMap(initCap)
????????//3.new?HashMap(map)
????????else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold
????????????newCap?=?oldThr;
????????//這種情況下oldThr=0;oldCap=0，說明沒經(jīng)過初始化，創(chuàng)建hashMap
????????//的時候是通過new?HashMap()的方式創(chuàng)建的
????????else?{???????????????//?zero?initial?threshold?signifies?using?defaults
????????????newCap?=?DEFAULT_INITIAL_CAPACITY;
????????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);
????????}
????????//newThr為0時，通過newCap和loadFactor計算出一個newThr
????????if?(newThr?==?0)?{
????????????//容量*0.75
????????????float?ft?=?(float)newCap?*?loadFactor;
????????????newThr?=?(newCap?float)MAXIMUM_CAPACITY??
??????????????????????(int)ft?:?Integer.MAX_VALUE);
????????}
????????threshold?=?newThr;
????????@SuppressWarnings({"rawtypes","unchecked"})
????????????????//根據(jù)上面計算出的結(jié)果創(chuàng)建一個更長更大的數(shù)組
????????????Node[]?newTab?=?(Node[])new?Node[newCap];
????????//將table指向新創(chuàng)建的數(shù)組
????????table?=?newTab;
????????//本次擴(kuò)容之前table不為null
????????if?(oldTab?!=?null)?{
????????????//對數(shù)組中的元素進(jìn)行遍歷
????????????for?(int?j?=?0;?j?????????????????//設(shè)置e為當(dāng)前node節(jié)點(diǎn)
????????????????Node?e;
????????????????//當(dāng)前桶位數(shù)據(jù)不為空，但不能知道里面是單個元素，還是鏈表或紅黑樹，
????????????????//e?=?oldTab[j]，先用e記錄下當(dāng)前元素
????????????????if?((e?=?oldTab[j])?!=?null)?{
????????????????????//將老數(shù)組j桶位置為空，方便回收
????????????????????oldTab[j]?=?null;
????????????????????//如果e節(jié)點(diǎn)不存在下一個節(jié)點(diǎn)，說明e是單個元素，則直接放置在新數(shù)組的桶位
????????????????????if?(e.next?==?null)
????????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;
????????????????????//如果e是樹節(jié)點(diǎn)，證明該節(jié)點(diǎn)處于紅黑樹中
????????????????????else?if?(e?instanceof?TreeNode)
????????????????????????((TreeNode)e).split(this,?newTab,?j,?oldCap);
????????????????????//e為鏈表節(jié)點(diǎn)，則對鏈表進(jìn)行遍歷
????????????????????else?{?//?preserve?order
????????????????????????//低位鏈表：存放在擴(kuò)容之后的數(shù)組的下標(biāo)位置，與當(dāng)前數(shù)組下標(biāo)位置一致
????????????????????????//loHead：低位鏈表頭節(jié)點(diǎn)
????????????????????????//loTail低位鏈表尾節(jié)點(diǎn)
????????????????????????Node?loHead?=?null,?loTail?=?null;
????????????????????????//高位鏈表，存放擴(kuò)容之后的數(shù)組的下標(biāo)位置，=原索引+擴(kuò)容之前數(shù)組容量
????????????????????????//hiHead:高位鏈表頭節(jié)點(diǎn)
????????????????????????//hiTail:高位鏈表尾節(jié)點(diǎn)
????????????????????????Node?hiHead?=?null,?hiTail?=?null;
????????????????????????Node?next;
????????????????????????do?{
????????????????????????????next?=?e.next;
????????????????????????????//oldCap為16:10000，與e.hsah做&運(yùn)算可以得到高位為1還是0
????????????????????????????//高位為0，放在低位鏈表
????????????????????????????if?((e.hash?&?oldCap)?==?0)?{
????????????????????????????????if?(loTail?==?null)
????????????????????????????????????//loHead指向e
????????????????????????????????????loHead?=?e;
????????????????????????????????else
????????????????????????????????????loTail.next?=?e;
????????????????????????????????loTail?=?e;
????????????????????????????}
????????????????????????????//高位為1，放在高位鏈表
????????????????????????????else?{
????????????????????????????????if?(hiTail?==?null)
????????????????????????????????????hiHead?=?e;
????????????????????????????????else
????????????????????????????????????hiTail.next?=?e;
????????????????????????????????hiTail?=?e;
????????????????????????????}
????????????????????????}?while?((e?=?next)?!=?null);
????????????????????????//低位鏈表已成，將頭節(jié)點(diǎn)loHead指向在原位
????????????????????????if?(loTail?!=?null)?{
????????????????????????????loTail.next?=?null;
????????????????????????????newTab[j]?=?loHead;
????????????????????????}
????????????????????????//高位鏈表已成，將頭節(jié)點(diǎn)指向新索引
????????????????????????if?(hiTail?!=?null)?{
????????????????????????????hiTail.next?=?null;
????????????????????????????newTab[j?+?oldCap]?=?hiHead;
????????????????????????}
????????????????????}
????????????????}
????????????}
????????}
????????return?newTab;
????}

擴(kuò)容之后原位置的節(jié)點(diǎn)只有兩種調(diào)整

• 保持原位置不動（新bit位為0時）
• 散列原索引+擴(kuò)容大小的位置去（新bit位為1時）

擴(kuò)容之后元素的散列設(shè)置的非常巧妙，節(jié)省了計算hash值的時間，我們來看一 下具體的實(shí)現(xiàn)

當(dāng)數(shù)組長度從16到32，其實(shí)只是多了一個bit位的運(yùn)算，我們只需要在意那個多出來的bit為是0還是1，是0的話索引不變，是1的話索引變?yōu)楫?dāng)前索引值+擴(kuò)容的長度，比如5變成5+16=21

這樣的擴(kuò)容方式不僅節(jié)省了重新計算hash的時間，而且保證了當(dāng)前桶中的元素總數(shù)一定小于等于原來桶中的元素數(shù)量，避免了更嚴(yán)重的hash沖突，均勻的把之前沖突的節(jié)點(diǎn)分散到新的桶中去

11. 一般用什么作為HashMap的key？

一般用Integer、String這種不可變類當(dāng)HashMap當(dāng)key

• 因?yàn)镾tring是不可變的，當(dāng)創(chuàng)建字符串時，它的hashcode被緩存下來，不需要再次計算，相對于其他對象更快
• 因?yàn)楂@取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的，這些類很規(guī)范的重寫了hashCode()以及equals()方法

12. 為什么Map桶中節(jié)點(diǎn)個數(shù)超過8才轉(zhuǎn)為紅黑樹？

8作為閾值作為HashMap的成員變量，在源碼的注釋中并沒有說明閾值為什么是8

在HashMap中有這樣一段注釋說明，我們繼續(xù)看

?*?Because?TreeNodes?are?about?twice?the?size?of?regular?nodes,?we
?*?use?them?only?when?bins?contain?enough?nodes?to?warrant?use
?*?(see?TREEIFY_THRESHOLD).?And?when?they?become?too?small?(due?to
?*?removal?or?resizing)?they?are?converted?back?to?plain?bins.??In
?*?usages?with?well-distributed?user?hashCodes,?tree?bins?are
?*?rarely?used.??Ideally,?under?random?hashCodes,?the?frequency?of
?*?nodes?in?bins?follows?a?Poisson?distribution
?*?(http://en.wikipedia.org/wiki/Poisson_distribution)?with?a
?*?parameter?of?about?0.5?on?average?for?the?default?resizing
?*?threshold?of?0.75,?although?with?a?large?variance?because?of
?*?resizing?granularity.?Ignoring?variance,?the?expected
?*?occurrences?of?list?size?k?are?(exp(-0.5)?*?pow(0.5,?k)?/
?*?factorial(k)).

翻譯

因?yàn)闃涔?jié)點(diǎn)的大小大約是普通節(jié)點(diǎn)的兩倍，所以我們只在箱子包含足夠的節(jié)點(diǎn)時才使用樹節(jié)點(diǎn)（參見TREEIFY_THRESHOLD）。
當(dāng)他們邊的太?。ㄓ捎趧h除或調(diào)整大小）時，就會被轉(zhuǎn)換回普通的桶，在使用分布良好的hashcode時，很少使用樹箱。
理想情況下，在隨機(jī)哈希碼下，箱子中節(jié)點(diǎn)的頻率服從泊松分布
第一個值是：

?*?0:????0.60653066
?*?1:????0.30326533
?*?2:????0.07581633
?*?3:????0.01263606
?*?4:????0.00157952
?*?5:????0.00015795
?*?6:????0.00001316
?*?7:????0.00000094
?*?8:????0.00000006
?*?more:?less?than?1?in?ten?million

樹節(jié)點(diǎn)占用空間是普通Node的兩倍，如果鏈表節(jié)點(diǎn)不夠多卻轉(zhuǎn)換成紅黑樹，無疑會耗費(fèi)大量的空間資源，并且在隨機(jī)hash算法下的所有bin節(jié)點(diǎn)分布頻率遵從泊松分布，鏈表長度達(dá)到8的概率只有0.00000006，幾乎是不可能事件，所以8的計算是經(jīng)過重重科學(xué)考量的

• 從平均查找長度來看，紅黑樹的平均查找長度是logn，如果長度為8，則logn=3，而鏈表的平均查找長度為n/4，長度為8時，n/2=4，所以閾值8能大大提高搜索速度
• 當(dāng)長度為6時紅黑樹退化為鏈表是因?yàn)閘ogn=log6約等于2.6，而n/2=6/2=3，兩者相差不大，而紅黑樹節(jié)點(diǎn)占用更多的內(nèi)存空間，所以此時轉(zhuǎn)換最為友好

13. HashMap為什么線程不安全？

• 多線程下擴(kuò)容死循環(huán)。JDK1.7中的HashMap使用頭插法插入元素，在多線程的環(huán)境下，擴(kuò)容的時候有可能導(dǎo)致環(huán)形鏈表的出現(xiàn)，形成死循環(huán)。因此JDK1.8使用尾插法插入元素，在擴(kuò)容時會保持鏈表元素原本的順序，不會出現(xiàn)環(huán)形鏈表的問題
• 多線程的put可能導(dǎo)致元素的丟失。多線程同時執(zhí)行put操作，如果計算出來的索引位置是相同的，那會造成前一個key被后一個key覆蓋，從而導(dǎo)致元素的丟失。此問題在JDK1.7和JDK1.8中都存在
• put和get并發(fā)時，可能導(dǎo)致get為null。線程1執(zhí)行put時，因?yàn)樵貍€數(shù)超出threshold而導(dǎo)致rehash，線程2此時執(zhí)行g(shù)et，有可能導(dǎo)致這個問題，此問題在JDK1.7和JDK1.8中都存在

14. 計算hash值時為什么要讓低16bit和高16bit進(jìn)行異或處理

• 我們計算索引需要將hashCode值與length-1進(jìn)行按位與運(yùn)算，如果數(shù)組長度很小，比如16，這樣的值和hashCode做異或?qū)嶋H上只有hashCode值的后4位在進(jìn)行運(yùn)算，hash值是一個隨機(jī)值，而如果產(chǎn)生的hashCode值高位變化很大，而低位變化很小，那么有很大概率造成哈希沖突，所以我們?yōu)榱耸乖馗玫纳⒘?，將hash值的高位也利用起來\

舉個例子

如果我們不對hashCode進(jìn)行按位異或，直接將hash和length-1進(jìn)行按位與運(yùn)算就有可能出現(xiàn)以下的情況

如果下一次生成的hashCode值高位起伏很大，而低位幾乎沒有變化時，高位無法參與運(yùn)算

可以看到，兩次計算出的hash相等，產(chǎn)生了hash沖突

所以無符號右移16位的目的是使高混亂度地區(qū)與地混亂度地區(qū)做一個中和，提高低位的隨機(jī)性，減少哈希沖突