1：HashMap 的數(shù)據(jù)結(jié)構(gòu)？
A：哈希表結(jié)構(gòu)（鏈表散列：數(shù)組+鏈表）實(shí)現(xiàn)旱物，結(jié)合數(shù)組和鏈表的優(yōu)點(diǎn)遥缕。當(dāng)鏈表長度超過 8 時，鏈表轉(zhuǎn)換為紅黑樹宵呛。
transient Node<K,V>[] table;
2：HashMap 的工作原理单匣？
HashMap 底層是 hash 數(shù)組和單向鏈表實(shí)現(xiàn)，數(shù)組中的每個元素都是鏈表宝穗，由 Node 內(nèi)部類（實(shí)現(xiàn) Map.Entry接口）實(shí)現(xiàn)户秤，HashMap 通過 put & get 方法存儲和獲取。
存儲對象時逮矛，將 K/V 鍵值傳給 put() 方法：
①鸡号、調(diào)用 hash(K) 方法計(jì)算 K 的 hash 值，然后結(jié)合數(shù)組長度须鼎，計(jì)算的數(shù)組下標(biāo)鲸伴；
②府蔗、調(diào)整數(shù)組大小（當(dāng)容器中的元素個數(shù)大于 capacity * loadfactor 時汞窗，容器會進(jìn)行擴(kuò)容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) 方法（計(jì)算 K 的 hash 值）從而獲取該鍵值所在鏈表的數(shù)組下標(biāo)忠寻；②惧浴、順序遍歷鏈表，equals()方法查找相同 Node 鏈表中 K 值對應(yīng)的 V 值奕剃。
hashCode 是定位的衷旅，存儲位置；equals是定性的纵朋，比較兩者是否相等柿顶。
3.當(dāng)兩個對象的 hashCode 相同會發(fā)生什么？
因?yàn)?hashCode 相同操软，不一定就是相等的（equals方法比較）嘁锯，所以兩個對象所在數(shù)組的下標(biāo)相同，"碰撞"就此發(fā)生聂薪。又因?yàn)?HashMap 使用鏈表存儲對象猪钮，這個 Node 會存儲到鏈表中。
4.你知道 hash 的實(shí)現(xiàn)嗎胆建？
為什么要這樣實(shí)現(xiàn)烤低？ JDK 1.8 中，是通過 hashCode() 的高 16 位異或低 16 位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)笆载，主要是從速度扑馁，功效和質(zhì)量來考慮的涯呻，減少系統(tǒng)的開銷，也不會造成因?yàn)楦呶粵]有參與下標(biāo)的計(jì)算腻要，從而引起的碰撞复罐。
5.為什么要用異或運(yùn)算符？
保證了對象的 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)擴(kuò)展，默認(rèn)值是0.75素挽，比如table 數(shù)組大小為 16限匣，裝載因子為 0.75 時，threshold 就是12毁菱，當(dāng) table 的實(shí)際大小超過 12 時米死，table就需要動態(tài)擴(kuò)容；
③贮庞、擴(kuò)容時峦筒，調(diào)用 resize() 方法，將 table 長度變?yōu)樵瓉淼膬杀叮ㄗ⒁馐?table 長度窗慎，而不是 threshold）
④物喷、如果數(shù)據(jù)很大的情況下，擴(kuò)展時將會帶來性能的損失遮斥，在性能要求很高的地方峦失，這種損失很可能很致命。
7.HashMap中put方法的過程术吗？
答：“調(diào)用哈希函數(shù)獲取Key對應(yīng)的hash值尉辑，再計(jì)算其數(shù)組下標(biāo)；
如果沒有出現(xiàn)哈希沖突较屿，則直接放入數(shù)組隧魄；如果出現(xiàn)哈希沖突卓练，則以鏈表的方式放在鏈表后面；
如果鏈表長度超過閥值( TREEIFY THRESHOLD==8)购啄，就把鏈表轉(zhuǎn)成紅黑樹襟企，鏈表長度低于6，就把紅黑樹轉(zhuǎn)回鏈表;
如果結(jié)點(diǎn)的key已經(jīng)存在狮含，則替換其value即可顽悼；
如果集合中的鍵值對大于12，調(diào)用resize方法進(jìn)行數(shù)組擴(kuò)容几迄∥盗”
8.數(shù)組擴(kuò)容的過程？
創(chuàng)建一個新的數(shù)組乓旗，其容量為舊數(shù)組的兩倍府蛇，并重新計(jì)算舊數(shù)組中結(jié)點(diǎn)的存儲位置集索。結(jié)點(diǎn)在新數(shù)組中的位置只有兩種屿愚，原下標(biāo)位置或原下標(biāo)+舊數(shù)組的大小。
9.拉鏈法導(dǎo)致的鏈表過深問題為什么不用二叉查找樹代替务荆，而選擇紅黑樹妆距？
為什么不一直使用紅黑樹？ 之所以選擇紅黑樹是為了解決二叉查找樹的缺陷函匕，二叉查找樹在特殊情況下會變成一條線性結(jié)構(gòu)（這就跟原來使用鏈表結(jié)構(gòu)一樣了娱据，造成很深的問題），遍歷查找會非常慢盅惜。
而紅黑樹在插入新數(shù)據(jù)后可能需要通過左旋中剩，右旋、變色這些操作來保持平衡抒寂，引入紅黑樹就是為了查找數(shù)據(jù)塊结啼，解決鏈表查詢深度的問題，我們知道紅黑樹屬于平衡二叉樹屈芜，但是為了保持“平衡”是需要付出代價的郊愧，但是該代價所損耗的資源要比遍歷線性鏈表要少，所以當(dāng)長度大于8的時候井佑，會使用紅黑樹属铁，如果鏈表長度很短的話，根本不需要引入紅黑樹躬翁，引入反而會慢焦蘑。
10.說說你對紅黑樹的見解？
每個節(jié)點(diǎn)非紅即黑 根節(jié)點(diǎn)總是黑色的 如果節(jié)點(diǎn)是紅色的盒发，則它的子節(jié)點(diǎn)必須是黑色的（反之不一定） 每個葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)） 從根節(jié)點(diǎn)到葉節(jié)點(diǎn)或空子節(jié)點(diǎn)的每條路徑喇肋，必須包含相同數(shù)目的黑色節(jié)點(diǎn)（即相同的黑色高度） 11.jdk8中對HashMap做了哪些改變坟乾？ 在java 1.8中，如果鏈表的長度超過了8蝶防，那么鏈表將轉(zhuǎn)換為紅黑樹甚侣。（桶的數(shù)量必須大于64，小于64的時候只會擴(kuò)容）
發(fā)生hash碰撞時间学，java 1.7 會在鏈表的頭部插入殷费，而java 1.8會在鏈表的尾部插入
在java 1.8中，Entry被Node替代(換了一個馬甲)低葫。
12.HashMap详羡，LinkedHashMap，TreeMap 有什么區(qū)別嘿悬？
LinkedHashMap 保存了記錄的插入順序实柠，在用 Iterator 遍歷時，先取到的記錄肯定是先插入的善涨；遍歷比 HashMap 慢窒盐；
TreeMap 實(shí)現(xiàn) SortMap 接口，能夠把它保存的記錄根據(jù)鍵排序（默認(rèn)按鍵值升序排序钢拧，也可以指定排序的比較器）
13.HashMap & TreeMap & LinkedHashMap 使用場景蟹漓？
一般情況下，使用最多的是 HashMap源内。
HashMap：在 Map 中插入葡粒、刪除和定位元素時；
TreeMap：在需要按自然順序或自定義順序遍歷鍵的情況下膜钓；
LinkedHashMap：在需要輸出的順序和輸入的順序相同的情況下嗽交。
14.HashMap 和 HashTable 有什么區(qū)別？
①颂斜、HashMap 是線程不安全的夫壁，HashTable 是線程安全的；
②焚鲜、由于線程安全掌唾，所以 HashTable 的效率比不上 HashMap；
③忿磅、HashMap最多只允許一條記錄的鍵為null糯彬，允許多條記錄的值為null，而 HashTable不允許葱她；
④撩扒、HashMap 默認(rèn)初始化數(shù)組的大小為16，HashTable 為 11，前者擴(kuò)容時搓谆，擴(kuò)大兩倍炒辉，后者擴(kuò)大兩倍+1；
⑤泉手、HashMap 需要重新計(jì)算 hash 值黔寇，而 HashTable 直接使用對象的 hashCode
15.Java 中的另一個線程安全的與 HashMap 極其類似的類是什么？同樣是線程安全斩萌，它與 HashTable 在線程同步上有什么不同缝裤？
ConcurrentHashMap 類（是 Java并發(fā)包 java.util.concurrent 中提供的一個線程安全且高效的 HashMap 實(shí)現(xiàn)）。
HashTable 是使用 synchronize 關(guān)鍵字加鎖的原理（就是對對象加鎖）颊郎；
而針對 ConcurrentHashMap憋飞，在 JDK 1.7 中采用 分段鎖的方式；JDK 1.8 中直接采用了CAS（無鎖算法）+ synchronized姆吭。
16.HashMap & ConcurrentHashMap 的區(qū)別榛做？
除了加鎖，原理上無太大區(qū)別内狸。另外检眯，HashMap 的鍵值對允許有null，但是ConCurrentHashMap 都不允許答倡。
17.為什么 ConcurrentHashMap 比 HashTable 效率要高轰传？
HashTable 使用一把鎖（鎖住整個鏈表結(jié)構(gòu)）處理并發(fā)問題驴党，多個線程競爭一把鎖瘪撇，容易阻塞；
ConcurrentHashMap
JDK 1.7 中使用分段鎖（ReentrantLock + Segment + HashEntry）港庄，相當(dāng)于把一個 HashMap 分成多個段倔既，每段分配一把鎖，這樣支持多線程訪問鹏氧。鎖粒度：基于 Segment渤涌，包含多個 HashEntry。
JDK 1.8 中使用 CAS + synchronized + Node + 紅黑樹把还。鎖粒度：Node（首結(jié)點(diǎn)）（實(shí)現(xiàn) Map.Entry）实蓬。鎖粒度降低了。
?18.針對 ConcurrentHashMap 鎖機(jī)制具體分析（JDK 1.7 VS JDK 1.8）吊履？
JDK 1.7 中安皱，采用分段鎖的機(jī)制，實(shí)現(xiàn)并發(fā)的更新操作艇炎，底層采用數(shù)組+鏈表的存儲結(jié)構(gòu)酌伊，包括兩個核心靜態(tài)內(nèi)部類 Segment 和 HashEntry。
①缀踪、Segment 繼承 ReentrantLock（重入鎖） 用來充當(dāng)鎖的角色居砖，每個 Segment 對象守護(hù)每個散列映射表的若干個桶虹脯；
②、HashEntry 用來封裝映射表的鍵-值對奏候；
③循集、每個桶是由若干個 HashEntry 對象鏈接起來的鏈表
JDK 1.8 中，采用Node + CAS + Synchronized來保證并發(fā)安全蔗草。取消類 Segment暇榴，直接用 table 數(shù)組存儲鍵值對；當(dāng) HashEntry 對象組成的鏈表長度超過 TREEIFY_THRESHOLD 時蕉世，鏈表轉(zhuǎn)換為紅黑樹蔼紧，提升性能。底層變更為數(shù)組 + 鏈表 + 紅黑樹狠轻。
19.ConcurrentHashMap 在 JDK 1.8 中奸例，為什么要使用內(nèi)置鎖 synchronized 來代替重入鎖 ReentrantLock？
①向楼、粒度降低了查吊；
②、JVM 開發(fā)團(tuán)隊(duì)沒有放棄 synchronized湖蜕，而且基于 JVM 的 synchronized 優(yōu)化空間更大逻卖，更加自然。
③昭抒、在大量的數(shù)據(jù)操作下评也，對于 JVM 的內(nèi)存壓力，基于 API 的 ReentrantLock 會開銷更多的內(nèi)存灭返。
20.ConcurrentHashMap 簡單介紹盗迟？
①、重要的常量：
private transient volatile int sizeCtl;
當(dāng)為負(fù)數(shù)時熙含，-1 表示正在初始化罚缕，-N 表示 N - 1 個線程正在進(jìn)行擴(kuò)容；
當(dāng)為 0 時怎静，表示 table 還沒有初始化邮弹；
當(dāng)為其他正數(shù)時，表示初始化或者下一次進(jìn)行擴(kuò)容的大小蚓聘。
②腌乡、數(shù)據(jù)結(jié)構(gòu)：
Node 是存儲結(jié)構(gòu)的基本單元，繼承 HashMap 中的 Entry或粮，用于存儲數(shù)據(jù)导饲；
TreeNode 繼承 Node，但是數(shù)據(jù)結(jié)構(gòu)換成了二叉樹結(jié)構(gòu)，是紅黑樹的存儲結(jié)構(gòu)渣锦，用于紅黑樹中存儲數(shù)據(jù)硝岗；
TreeBin 是封裝 TreeNode 的容器，提供轉(zhuǎn)換紅黑樹的一些條件和鎖的控制袋毙。
③型檀、存儲對象時（put() 方法）：
如果沒有初始化，就調(diào)用 initTable() 方法來進(jìn)行初始化听盖；
如果沒有 hash 沖突就直接 CAS 無鎖插入胀溺；
如果需要擴(kuò)容，就先進(jìn)行擴(kuò)容皆看；
如果存在 hash 沖突仓坞，就加鎖來保證線程安全，兩種情況：一種是鏈表形式就直接遍歷到尾端插入腰吟，一種是紅黑樹就按照紅黑樹結(jié)構(gòu)插入无埃；
如果該鏈表的數(shù)量大于閥值 8，就要先轉(zhuǎn)換成紅黑樹的結(jié)構(gòu)毛雇，break 再一次進(jìn)入循環(huán)
如果添加成功就調(diào)用 addCount() 方法統(tǒng)計(jì) size嫉称，并且檢查是否需要擴(kuò)容。
④灵疮、擴(kuò)容方法 transfer()：默認(rèn)容量為 16织阅，擴(kuò)容時，容量變?yōu)樵瓉淼膬杀丁?/b>
helpTransfer()：調(diào)用多個工作線程一起幫助進(jìn)行擴(kuò)容震捣，這樣的效率就會更高荔棉。
⑤、獲取對象時（get()方法）：
計(jì)算 hash 值伍派，定位到該 table 索引位置江耀，如果是首結(jié)點(diǎn)符合就返回剩胁；
如果遇到擴(kuò)容時诉植，會調(diào)用標(biāo)記正在擴(kuò)容結(jié)點(diǎn) ForwardingNode.find()方法，查找該結(jié)點(diǎn)昵观，匹配就返回晾腔；
以上都不符合的話，就往下遍歷結(jié)點(diǎn)啊犬，匹配就返回灼擂，否則最后就返回 null。
21.ConcurrentHashMap 的并發(fā)度是什么觉至？
程序運(yùn)行時能夠同時更新 ConccurentHashMap 且不產(chǎn)生鎖競爭的最大線程數(shù)剔应。默認(rèn)為 16，且可以在構(gòu)造函數(shù)中設(shè)置。
當(dāng)用戶設(shè)置并發(fā)度時峻贮，ConcurrentHashMap 會使用大于等于該值的最小2冪指數(shù)作為實(shí)際并發(fā)度（假如用戶設(shè)置并發(fā)度為17席怪，實(shí)際并發(fā)度則為32）
最后
1000道面試題資料+面試簡歷模板+java資料+全套架構(gòu)師學(xué)習(xí)資料和視頻【全部免費(fèi)】領(lǐng)取
祝大家面試順利，都能進(jìn)大廠纤控，走向人生巔峰挂捻！
