為什么HashMap的加載因子是0.75呢粥谬？
加載因子指的是吹害，實際個數(shù)/容量，實際個數(shù)指的是key-value對沃于，容量指的是桶的數(shù)量
答：
從實際上考慮：加載因子過高，例如為1海诲，雖然減少了空間開銷繁莹，提高了空間利用率，但同時也增加了查詢時間成本特幔；
加載因子過低咨演，例如0.5，雖然可以減少查詢時間成本蚯斯，但是空間利用率很低薄风，同時提高了rehash操作的次數(shù)。
在設置初始容量時應該考慮到映射中所需的條目數(shù)及其加載因子拍嵌，以便最大限度地減少rehash操作次數(shù)遭赂，所以，一般在使用HashMap時建議根據(jù)預估值設置初始容量横辆，減少擴容操作撇他。
選擇0.75作為默認的加載因子，完全是時間和空間成本上尋求的一種折衷選擇狈蚤，
從統(tǒng)計學上考慮：
因為在加載因子為0.75的條件下困肩，鏈表的長度與概率符合泊松分布，而當長度為8時脆侮，概率已經(jīng)是0.00000006锌畸，基本上已經(jīng)是不可能事件了，所以選擇這個參數(shù)作為加載因子
HashMap的擴容過程（雖然閾值是通過數(shù)組大小×負載因子得到的靖避，但是實際上是添加的節(jié)點數(shù)大于閾值潭枣，就回擴容）比默？
答：
1. JDK7中的擴容機制（先插入，后擴容卸耘，兩次hash）
JDK7的擴容機制相對簡單退敦，有以下特性：
- 空參數(shù)的構(gòu)造函數(shù)：以默認容量、默認負載因子蚣抗、默認閾值初始化數(shù)組侈百。內(nèi)部數(shù)組是空數(shù)組。
- 有參構(gòu)造函數(shù)：根據(jù)參數(shù)確定容量翰铡、負載因子钝域、閾值等。
- 第一次put時會初始化數(shù)組锭魔，其容量變?yōu)?strong>不小于指定容量的2的冪數(shù)例证。然后根據(jù)負載因子確定閾值。
- 如果不是第一次擴容迷捧，則新容量=久容量×2 新閾值＝新容量×負載因子
2. JDK8的擴容機制（先擴容织咧，在插入，一次hash）
JDK8的擴容做了許多調(diào)整漠秋。
HashMap的容量變化通常存在以下幾種情況：
- 空參數(shù)的構(gòu)造函數(shù)：實例化的HashMap默認內(nèi)部數(shù)組是null笙蒙，即沒有實例化。第一次調(diào)用put方法時庆锦，則會開始第一次初始化擴容捅位，長度為16。
- 有參構(gòu)造函數(shù)：用于指定容量搂抒。會根據(jù)指定的正整數(shù)找到不小于指定容量的2的冪數(shù)艇搀，將這個數(shù)設置賦值給閾值（threshold）。第一次調(diào)用put方法時求晶，會將閾值賦值給容量焰雕，然后讓閾值 ＝容量負載因子*。（因此并不是我們手動指定了容量就一定不會觸發(fā)擴容芳杏，超過閾值后一樣會擴容５砩ⅰ！）
- 如果不是第一次擴容蚜锨，則容量變?yōu)樵瓉淼?倍，閾值也變?yōu)樵瓉淼?倍慢蜓。（容量和閾值都變?yōu)樵瓉淼?倍時亚再，負載因子還是不變）
此外還有幾個細節(jié)需要注意：
- 首次put時，先會觸發(fā)擴容（算是初始化）晨抡，然后存入數(shù)據(jù)氛悬，然后判斷是否需要擴容则剃；
- 不是首次put，則不再初始化如捅，直接存入數(shù)據(jù)棍现，然后判斷是否需要擴容；
JDK7的元素遷移
JDK7中镜遣，HashMap的內(nèi)部數(shù)據(jù)保存的都是鏈表己肮。因此邏輯相對簡單：在準備好新的數(shù)組后，map會遍歷數(shù)組的每個“桶”悲关，然后遍歷桶中的每個Entity谎僻，重新計算其hash值（也有可能不計算），找到新數(shù)組中的對應位置寓辱，以頭插法插入新的鏈表艘绍。
這里有幾個注意點：
是否要重新計算hash值的條件這里不深入討論，讀者可自行查閱源碼秫筏。
因為是頭插法诱鞠，因此新舊鏈表的元素位置會發(fā)生轉(zhuǎn)置現(xiàn)象。
元素遷移的過程中在多線程情境下有可能會觸發(fā)死循環(huán)（無限進行鏈表反轉(zhuǎn)）这敬。
JDK8的元素遷移
JDK8則因為巧妙的設計航夺，性能有了大大的提升：由于數(shù)組的容量是以2的冪次方擴容的，那么一個Entity在擴容時鹅颊，新的位置要么在原位置敷存，要么在原長度+原位置的位置。原因如下圖：
數(shù)組長度變?yōu)樵瓉淼?倍堪伍，表現(xiàn)在二進制上就是多了一個高位參與數(shù)組下標確定锚烦。此時，一個元素通過hash轉(zhuǎn)換坐標的方法計算后帝雇，恰好出現(xiàn)一個現(xiàn)象：最高位是0則坐標不變涮俄，最高位是1則坐標變?yōu)椤?0000+原坐標”，即“原長度+原坐標”尸闸。如下圖：
因此彻亲，在擴容時，不需要重新計算元素的hash了吮廉，只需要判斷最高位是1還是0就好了苞尝。
JDK8的HashMap還有以下細節(jié)：
JDK8在遷移元素時是正序的，不會出現(xiàn)鏈表轉(zhuǎn)置的發(fā)生宦芦。
如果某個桶內(nèi)的元素超過8個宙址，則會將鏈表轉(zhuǎn)化成紅黑樹，加快數(shù)據(jù)查詢效率调卑。
為什么HashMap1.7用頭插法抡砂，而1.8用尾插法大咱？
答：因為在多線程的情況下，擴容的時候可能會導致鏈表成環(huán)注益，因為頭插法的話再重新Hash后插入的時候碴巾，順序是跟原來相反的具體例子看參考鏈接
JDK1.8對hash算法進行了哪些優(yōu)化？
1丑搔、hash算法：JDK1.7中通過key.hashcode()得到關鍵字的hash值厦瓢，JDK1.8將hash值的高16位與低16位進行異或運算，使得hash值的低16位同時保留高16位和低16位的特征低匙，對于兩個hash值低16位相等旷痕，高16位不等的情況，減少hash沖突顽冶。
2欺抗、尋址算法：JDK1.7位hash值對數(shù)組長度進行取模運算，JDK1.8變?yōu)?strong>hash&(n-1)强重，n為數(shù)組長度绞呈。當數(shù)組長度是2的冪次時，hash值對數(shù)組長度取模和hash&(n-1)的效果是一樣的间景，但是與運算的性能更高佃声。
為什么HashMap的數(shù)組長度要取2的整數(shù)冪？
答：首先我們要知道key散列到相應的數(shù)組下標的hash規(guī)則倘要，就是index=key&（N-1）圾亏，其實本來是index%N，換成這樣首先是因為位運算更快封拧，因為比如16-1=15志鹃。2進制表示是00000000 00000000 00001111。和某散列值做“與”操作如下泽西，結(jié)果就是截取了最低的四位值曹铃。也就是取值是0-15，這也就相當于%的效果了捧杉。
為什么采用hashcode的高16位和低16位異或能降低hash碰撞陕见？hash函數(shù)能不能直接用key的hashcode？
答：因為 key.hashCode() 函數(shù)調(diào)用的是key鍵值類型自帶的哈希函數(shù)味抖，返回int型散列值评甜。int值范圍為-2147483648~2147483647，前后加起來大概40億的映射空間仔涩。只要哈希函數(shù)映射得比較均勻松散忍坷，一般應用是很難出現(xiàn)碰撞的。但問題是一個40億長度的數(shù)組，內(nèi)存是放不下的承匣。你想，如果HashMap數(shù)組的初始大小才16锤悄，用之前需要對數(shù)組的長度取模運算韧骗，得到的余數(shù)才能用來訪問數(shù)組下標。比如說0 到10000的散列空間零聚，如果是1 1001 2001 3001 ...... 這樣在整個散列空間上是非常均勻的袍暴，但是一旦的取余了100了之后呢，全部沖突隶症。
但這時候問題就來了政模，這樣就算我的散列值分布再松散，要是只取最后幾位的話蚂会，碰撞也會很嚴重淋样。更要命的是如果散列本身做得不好，分布上成等差數(shù)列的漏洞胁住，如果正好讓最后幾個低位呈現(xiàn)規(guī)律性重復趁猴，就無比蛋疼。
右位移16位彪见，正好是32bit的一半儡司，自己的高半?yún)^(qū)和低半?yún)^(qū)做異或，就是為了混合原始哈希碼的高位和低位余指，以此來加大低位的隨機性捕犬。而且混合后的低位摻雜了高位的部分特征，這樣高位的信息也被變相保留下來酵镜。
Java中HashMap碉碉、LinkedHashMap和TreeMap區(qū)別使用場景？
答：
1. HashMap：不是按照插入順序笋婿，也不是按照大小順序誉裆。單純用來統(tǒng)計
2.LinkedHashMap：它內(nèi)部有一個鏈表，保持Key插入的順序缸濒。迭代的時候足丢，也是按照插入順序迭代，而且迭代比HashMap快庇配。
3. TreeMap：順序是Key的自然順序（如整數(shù)從小到大）斩跌，也可以指定比較函數(shù)。但不是插入的順序捞慌。
HashMap的默認容量（1.7與1.8）全都是16嗎耀鸦？為什么是16？初始容量300的HashMap，加301個元素（map擴容幾次）袖订？
答：為什么是16呢我個人覺得這個是經(jīng)驗得來的氮帐，因為我們這個容量的大小，如果太小的話洛姑，那么會導致沖突的幾率快上沐，并且會經(jīng)常擴容，但是如果太大的話楞艾，又會導致空間浪費参咙，所以我們的容量設置主要是要在這兩個方面去均衡，所以一般如果我們明確知道我們的Map數(shù)量最集中的取間是在哪硫眯，我們初始化的時候就設置容量會比較好蕴侧。
紅黑樹為什么比鏈表查找快？
答：
- 因為鏈表是線性表嗎两入，每次查詢都得遍歷整個鏈表直到查詢到想要的數(shù)據(jù)净宵。是o（n）
- 紅黑樹呢，是一種特殊的二叉查找樹谆刨，二叉查找樹塘娶，比如有完全二叉樹，他的查詢次數(shù)就是他的高度痊夭，但是這種維護成本太高了刁岸，所以就有了紅黑樹，紅黑樹的要求就沒完全二叉樹那么高了她我，但是他有一個特性虹曙，就是從任一結(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點，從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色結(jié)點番舆，那么這就可以知道紅黑樹的最長查詢距離不會超過最短查詢距離的兩倍酝碳，那么就可以知道紅黑樹的查詢時間復雜度為2log（n），這就大大提升了效率
