為什么HashMap的加載因子是0.75呢？

加載因子指的是，實(shí)際個(gè)數(shù)/容量，實(shí)際個(gè)數(shù)指的是key-value對(duì)，容量指的是桶的數(shù)量

答：
從實(shí)際上考慮：加載因子過(guò)高，例如為1，雖然減少了空間開銷，提高了空間利用率，但同時(shí)也增加了查詢時(shí)間成本；

加載因子過(guò)低，例如0.5，雖然可以減少查詢時(shí)間成本，但是空間利用率很低，同時(shí)提高了rehash操作的次數(shù)。

在設(shè)置初始容量時(shí)應(yīng)該考慮到映射中所需的條目數(shù)及其加載因子，以便最大限度地減少rehash操作次數(shù)，所以，一般在使用HashMap時(shí)建議根據(jù)預(yù)估值設(shè)置初始容量，減少擴(kuò)容操作。

選擇0.75作為默認(rèn)的加載因子，完全是時(shí)間和空間成本上尋求的一種折衷選擇，

從統(tǒng)計(jì)學(xué)上考慮：

因?yàn)樵诩虞d因子為0.75的條件下，鏈表的長(zhǎng)度與概率符合泊松分布，而當(dāng)長(zhǎng)度為8時(shí)，概率已經(jīng)是0.00000006，基本上已經(jīng)是不可能事件了，所以選擇這個(gè)參數(shù)作為加載因子

HashMap的擴(kuò)容過(guò)程（雖然閾值是通過(guò)數(shù)組大小×負(fù)載因子得到的，但是實(shí)際上是添加的節(jié)點(diǎn)數(shù)大于閾值，就回?cái)U(kuò)容）？

答：

1. JDK7中的擴(kuò)容機(jī)制（先插入，后擴(kuò)容，兩次hash）

JDK7的擴(kuò)容機(jī)制相對(duì)簡(jiǎn)單，有以下特性：

• 空參數(shù)的構(gòu)造函數(shù)：以默認(rèn)容量、默認(rèn)負(fù)載因子、默認(rèn)閾值初始化數(shù)組。內(nèi)部數(shù)組是空數(shù)組。
• 有參構(gòu)造函數(shù)：根據(jù)參數(shù)確定容量、負(fù)載因子、閾值等。
• 第一次put時(shí)會(huì)初始化數(shù)組，其容量變?yōu)?strong>不小于指定容量的2的冪數(shù)。然后根據(jù)負(fù)載因子確定閾值。
• 如果不是第一次擴(kuò)容，則新容量=久容量×2 新閾值＝新容量×負(fù)載因子

2. JDK8的擴(kuò)容機(jī)制（先擴(kuò)容，在插入，一次hash）

JDK8的擴(kuò)容做了許多調(diào)整。

HashMap的容量變化通常存在以下幾種情況：

1. 空參數(shù)的構(gòu)造函數(shù)：實(shí)例化的HashMap默認(rèn)內(nèi)部數(shù)組是null，即沒(méi)有實(shí)例化。第一次調(diào)用put方法時(shí)，則會(huì)開始第一次初始化擴(kuò)容，長(zhǎng)度為16。
2. 有參構(gòu)造函數(shù)：用于指定容量。會(huì)根據(jù)指定的正整數(shù)找到不小于指定容量的2的冪數(shù)，將這個(gè)數(shù)設(shè)置賦值給閾值（threshold）。第一次調(diào)用put方法時(shí)，會(huì)將閾值賦值給容量，然后讓閾值 ＝容量負(fù)載因子*。（因此并不是我們手動(dòng)指定了容量就一定不會(huì)觸發(fā)擴(kuò)容，超過(guò)閾值后一樣會(huì)擴(kuò)容?。。?/li>
3. 如果不是第一次擴(kuò)容，則容量變?yōu)樵瓉?lái)的2倍，閾值也變?yōu)樵瓉?lái)的2倍。（容量和閾值都變?yōu)樵瓉?lái)的2倍時(shí)，負(fù)載因子還是不變）

此外還有幾個(gè)細(xì)節(jié)需要注意：

• 首次put時(shí)，先會(huì)觸發(fā)擴(kuò)容（算是初始化），然后存入數(shù)據(jù)，然后判斷是否需要擴(kuò)容；
• 不是首次put，則不再初始化，直接存入數(shù)據(jù)，然后判斷是否需要擴(kuò)容；

JDK7的元素遷移

JDK7中，HashMap的內(nèi)部數(shù)據(jù)保存的都是鏈表。因此邏輯相對(duì)簡(jiǎn)單：在準(zhǔn)備好新的數(shù)組后，map會(huì)遍歷數(shù)組的每個(gè)“桶”，然后遍歷桶中的每個(gè)Entity，重新計(jì)算其hash值（也有可能不計(jì)算），找到新數(shù)組中的對(duì)應(yīng)位置，以頭插法插入新的鏈表。

這里有幾個(gè)注意點(diǎn)：

是否要重新計(jì)算hash值的條件這里不深入討論，讀者可自行查閱源碼。
因?yàn)槭穷^插法，因此新舊鏈表的元素位置會(huì)發(fā)生轉(zhuǎn)置現(xiàn)象。
元素遷移的過(guò)程中在多線程情境下有可能會(huì)觸發(fā)死循環(huán)（無(wú)限進(jìn)行鏈表反轉(zhuǎn)）。

JDK8的元素遷移
JDK8則因?yàn)榍擅畹脑O(shè)計(jì)，性能有了大大的提升：由于數(shù)組的容量是以2的冪次方擴(kuò)容的，那么一個(gè)Entity在擴(kuò)容時(shí)，新的位置要么在原位置，要么在原長(zhǎng)度+原位置的位置。原因如下圖：

移位圖

例子

JDK8的HashMap還有以下細(xì)節(jié)：

JDK8在遷移元素時(shí)是正序的，不會(huì)出現(xiàn)鏈表轉(zhuǎn)置的發(fā)生。
如果某個(gè)桶內(nèi)的元素超過(guò)8個(gè)，則會(huì)將鏈表轉(zhuǎn)化成紅黑樹，加快數(shù)據(jù)查詢效率。

為什么HashMap1.7用頭插法，而1.8用尾插法？

答：因?yàn)樵诙嗑€程的情況下，擴(kuò)容的時(shí)候可能會(huì)導(dǎo)致鏈表成環(huán)，因?yàn)轭^插法的話再重新Hash后插入的時(shí)候，順序是跟原來(lái)相反的具體例子看參考鏈接

JDK1.8對(duì)hash算法進(jìn)行了哪些優(yōu)化？

1、hash算法：JDK1.7中通過(guò)key.hashcode()得到關(guān)鍵字的hash值，JDK1.8將hash值的高16位與低16位進(jìn)行異或運(yùn)算，使得hash值的低16位同時(shí)保留高16位和低16位的特征，對(duì)于兩個(gè)hash值低16位相等，高16位不等的情況，減少hash沖突。

2、尋址算法：JDK1.7位hash值對(duì)數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算，JDK1.8變?yōu)?strong>hash&(n-1)，n為數(shù)組長(zhǎng)度。當(dāng)數(shù)組長(zhǎng)度是2的冪次時(shí)，hash值對(duì)數(shù)組長(zhǎng)度取模和hash&(n-1)的效果是一樣的，但是與運(yùn)算的性能更高。

為什么HashMap的數(shù)組長(zhǎng)度要取2的整數(shù)冪？

答：首先我們要知道key散列到相應(yīng)的數(shù)組下標(biāo)的hash規(guī)則，就是index=key&（N-1），其實(shí)本來(lái)是index%N，換成這樣首先是因?yàn)槲贿\(yùn)算更快，因?yàn)楸热?6-1=15。2進(jìn)制表示是00000000 00000000 00001111。和某散列值做“與”操作如下，結(jié)果就是截取了最低的四位值。也就是取值是0-15，這也就相當(dāng)于%的效果了。

為什么采用hashcode的高16位和低16位異或能降低hash碰撞？hash函數(shù)能不能直接用key的hashcode？

答：因?yàn)?key.hashCode() 函數(shù)調(diào)用的是key鍵值類型自帶的哈希函數(shù)，返回int型散列值。int值范圍為-2147483648~2147483647，前后加起來(lái)大概40億的映射空間。只要哈希函數(shù)映射得比較均勻松散，一般應(yīng)用是很難出現(xiàn)碰撞的。但問(wèn)題是一個(gè)40億長(zhǎng)度的數(shù)組，內(nèi)存是放不下的。你想，如果HashMap數(shù)組的初始大小才16，用之前需要對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算，得到的余數(shù)才能用來(lái)訪問(wèn)數(shù)組下標(biāo)。比如說(shuō)0 到10000的散列空間，如果是1 1001 2001 3001 ...... 這樣在整個(gè)散列空間上是非常均勻的，但是一旦的取余了100了之后呢，全部沖突。
但這時(shí)候問(wèn)題就來(lái)了，這樣就算我的散列值分布再松散，要是只取最后幾位的話，碰撞也會(huì)很嚴(yán)重。更要命的是如果散列本身做得不好，分布上成等差數(shù)列的漏洞，如果正好讓最后幾個(gè)低位呈現(xiàn)規(guī)律性重復(fù)，就無(wú)比蛋疼。
右位移16位，正好是32bit的一半，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位，以此來(lái)加大低位的隨機(jī)性。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來(lái)。

Java中HashMap、LinkedHashMap和TreeMap區(qū)別使用場(chǎng)景？

答：
1. HashMap：不是按照插入順序，也不是按照大小順序。單純用來(lái)統(tǒng)計(jì)
2.LinkedHashMap：它內(nèi)部有一個(gè)鏈表，保持Key插入的順序。迭代的時(shí)候，也是按照插入順序迭代，而且迭代比HashMap快。
3. TreeMap：順序是Key的自然順序（如整數(shù)從小到大），也可以指定比較函數(shù)。但不是插入的順序。

HashMap的默認(rèn)容量（1.7與1.8）全都是16嗎？為什么是16？初始容量300的HashMap，加301個(gè)元素（map擴(kuò)容幾次）？

答：為什么是16呢我個(gè)人覺(jué)得這個(gè)是經(jīng)驗(yàn)得來(lái)的，因?yàn)槲覀冞@個(gè)容量的大小，如果太小的話，那么會(huì)導(dǎo)致沖突的幾率快，并且會(huì)經(jīng)常擴(kuò)容，但是如果太大的話，又會(huì)導(dǎo)致空間浪費(fèi)，所以我們的容量設(shè)置主要是要在這兩個(gè)方面去均衡，所以一般如果我們明確知道我們的Map數(shù)量最集中的取間是在哪，我們初始化的時(shí)候就設(shè)置容量會(huì)比較好。

紅黑樹為什么比鏈表查找快？

答：

1. 因?yàn)殒湵硎蔷€性表嗎，每次查詢都得遍歷整個(gè)鏈表直到查詢到想要的數(shù)據(jù)。是o（n）
2. 紅黑樹呢，是一種特殊的二叉查找樹，二叉查找樹，比如有完全二叉樹，他的查詢次數(shù)就是他的高度，但是這種維護(hù)成本太高了，所以就有了紅黑樹，紅黑樹的要求就沒(méi)完全二叉樹那么高了，但是他有一個(gè)特性，就是從任一結(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點(diǎn)，從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色結(jié)點(diǎn)，那么這就可以知道紅黑樹的最長(zhǎng)查詢距離不會(huì)超過(guò)最短查詢距離的兩倍，那么就可以知道紅黑樹的查詢時(shí)間復(fù)雜度為2log（n），這就大大提升了效率