1：HashMap 的數(shù)據(jù)結(jié)構(gòu)？
A：哈希表結(jié)構(gòu)（鏈表散列：數(shù)組+鏈表）實現(xiàn)，結(jié)合數(shù)組和鏈表的優(yōu)點。當(dāng)鏈表長度超過 8 時，鏈表轉(zhuǎn)換為紅黑樹。
transient Node<K,V>[] table;
2：HashMap 的工作原理？
HashMap 底層是 hash 數(shù)組和單向鏈表實現(xiàn)，數(shù)組中的每個元素都是鏈表，由 Node 內(nèi)部類（實現(xiàn) Map.Entry接口）實現(xiàn)，HashMap 通過 put & get 方法存儲和獲取。
存儲對象時，將 K/V 鍵值傳給 put() 方法：
①、調(diào)用 hash(K) 方法計算 K 的 hash 值，然后結(jié)合數(shù)組長度，計算得數(shù)組下標(biāo)；
②、調(diào)整數(shù)組大?。ó?dāng)容器中的元素個數(shù)大于 capacity * loadfactor 時，容器會進(jìn)行擴容resize 為 2n）；
③、i.如果 K 的 hash 值在 HashMap 中不存在，則執(zhí)行插入，若存在，則發(fā)生碰撞；
ii.如果 K 的 hash 值在 HashMap 中存在，且它們兩者 equals 返回 true，則更新鍵值對；
iii. 如果 K 的 hash 值在 HashMap 中存在，且它們兩者 equals 返回 false，則插入鏈表的尾部（尾插法）或者紅黑樹中（樹的添加方式）。
（JDK 1.7 之前使用頭插法、JDK 1.8 使用尾插法）（注意：當(dāng)碰撞導(dǎo)致鏈表大于 TREEIFY_THRESHOLD = 8 時，就把鏈表轉(zhuǎn)換成紅黑樹）
獲取對象時，將 K 傳給 get() 方法：①、調(diào)用 hash(K) 方法（計算 K 的 hash 值）從而獲取該鍵值所在鏈表的數(shù)組下標(biāo)；②、順序遍歷鏈表，equals()方法查找相同 Node 鏈表中 K 值對應(yīng)的 V 值。
hashCode 是定位的，存儲位置；equals是定性的，比較兩者是否相等。
3.當(dāng)兩個對象的 hashCode 相同會發(fā)生什么？
[因為 hashCode 相同，不一定就是相等的（equals方法比較），所以兩個對象所在數(shù)組的下標(biāo)相同，"碰撞"就此發(fā)生。又因為 HashMap 使用鏈表存儲對象，這個 Node 會存儲到鏈表中。為什么要重寫 hashcode 和 equals 方法？推薦看下。]
4.你知道 hash 的實現(xiàn)嗎？為什么要這樣實現(xiàn)？
JDK 1.8 中，是通過 hashCode() 的高 16 位異或低 16 位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度，功效和質(zhì)量來考慮的，減少系統(tǒng)的開銷，也不會造成因為高位沒有參與下標(biāo)的計算，從而引起的碰撞。
5.為什么要用異或運算符？
保證了對象的 hashCode 的 32 位值只要有一位發(fā)生改變，整個 hash() 返回值就會改變。盡可能的減少碰撞。
6.HashMap 的 table 的容量如何確定？loadFactor 是什么？該容量如何變化？這種變化會帶來什么問題？
①、table 數(shù)組大小是由 capacity 這個參數(shù)確定的，默認(rèn)是16，也可以構(gòu)造時傳入，最大限制是1<<30；
②、loadFactor 是裝載因子，主要目的是用來確認(rèn)table 數(shù)組是否需要動態(tài)擴展，默認(rèn)值是0.75，比如table 數(shù)組大小為 16，裝載因子為 0.75 時，threshold 就是12，當(dāng) table 的實際大小超過 12 時，table就需要動態(tài)擴容；
③、擴容時，調(diào)用 resize() 方法，將 table 長度變?yōu)樵瓉淼膬杀叮ㄗ⒁馐?table 長度，而不是 threshold）
④、如果數(shù)據(jù)很大的情況下，擴展時將會帶來性能的損失，在性能要求很高的地方，這種損失很可能很致命。
7.HashMap中put方法的過程？
答：“調(diào)用哈希函數(shù)獲取Key對應(yīng)的hash值，再計算其數(shù)組下標(biāo)；
如果沒有出現(xiàn)哈希沖突，則直接放入數(shù)組；如果出現(xiàn)哈希沖突，則以鏈表的方式放在鏈表后面；
如果鏈表長度超過閥值( TREEIFY THRESHOLD==8)，就把鏈表轉(zhuǎn)成紅黑樹，鏈表長度低于6，就把紅黑樹轉(zhuǎn)回鏈表;
如果結(jié)點的key已經(jīng)存在，則替換其value即可；
如果集合中的鍵值對大于12，調(diào)用resize方法進(jìn)行數(shù)組擴容。”
8.數(shù)組擴容的過程？
創(chuàng)建一個新的數(shù)組，其容量為舊數(shù)組的兩倍，并重新計算舊數(shù)組中結(jié)點的存儲位置。結(jié)點在新數(shù)組中的位置只有兩種，原下標(biāo)位置或原下標(biāo)+舊數(shù)組的大小。
9.拉鏈法導(dǎo)致的鏈表過深問題為什么不用二叉查找樹代替，而選擇紅黑樹？為什么不一直使用紅黑樹？
之所以選擇紅黑樹是為了解決二叉查找樹的缺陷，二叉查找樹在特殊情況下會變成一條線性結(jié)構(gòu)（這就跟原來使用鏈表結(jié)構(gòu)一樣了，造成很深的問題），遍歷查找會非常慢。推薦：面試問紅黑樹，我臉都綠了。
而紅黑樹在插入新數(shù)據(jù)后可能需要通過左旋，右旋、變色這些操作來保持平衡，引入紅黑樹就是為了查找數(shù)據(jù)快，解決鏈表查詢深度的問題，我們知道紅黑樹屬于平衡二叉樹，但是為了保持“平衡”是需要付出代價的，但是該代價所損耗的資源要比遍歷線性鏈表要少，所以當(dāng)長度大于8的時候，會使用紅黑樹，如果鏈表長度很短的話，根本不需要引入紅黑樹，引入反而會慢。
10.說說你對紅黑樹的見解？
- 每個節(jié)點非紅即黑
- 根節(jié)點總是黑色的
- 如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（反之不一定）
- 每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）
- 從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑，必須包含相同數(shù)目的黑色節(jié)點（即相同的黑色高度）
