1：HashMap 的數(shù)據(jù)結(jié)構(gòu)伙狐？
A：哈希表結(jié)構(gòu)（鏈表散列：數(shù)組+鏈表）實(shí)現(xiàn)，結(jié)合數(shù)組和鏈表的優(yōu)點(diǎn)瞬欧。當(dāng)鏈表長(zhǎng)度超過(guò) 8 時(shí)贷屎，鏈表轉(zhuǎn)換為紅黑樹(shù)。
transientNode[]table;
2：HashMap 的工作原理艘虎？
HashMap 底層是 hash 數(shù)組和單向鏈表實(shí)現(xiàn)钮追，數(shù)組中的每個(gè)元素都是鏈表蛋勺，由 Node 內(nèi)部類(lèi)（實(shí)現(xiàn) Map.Entry接口）實(shí)現(xiàn)，HashMap 通過(guò) put & get 方法存儲(chǔ)和獲取吟孙。
存儲(chǔ)對(duì)象時(shí)，將 K/V 鍵值傳給 put() 方法：
①右犹、調(diào)用 hash(K) 方法計(jì)算 K 的 hash 值，然后結(jié)合數(shù)組長(zhǎng)度，計(jì)算的數(shù)組下標(biāo)绽昼；
②、調(diào)整數(shù)組大行胛稀（當(dāng)容器中的元素個(gè)數(shù)大于 capacity * loadfactor 時(shí)硅确，容器會(huì)進(jìn)行擴(kuò)容resize 為 2n）；
③唠粥、i.如果 K 的 hash 值在 HashMap 中不存在疏魏，則執(zhí)行插入，若存在晤愧，則發(fā)生碰撞大莫；
ii.如果 K 的 hash 值在 HashMap 中存在，且它們兩者 equals 返回 true官份，則更新鍵值對(duì)只厘；
iii. 如果 K 的 hash 值在 HashMap 中存在，且它們兩者 equals 返回 false舅巷，則插入鏈表的尾部（尾插法）或者紅黑樹(shù)中（樹(shù)的添加方式）羔味。（JDK 1.7 之前使用頭插法、JDK 1.8 使用尾插法）（注意：當(dāng)碰撞導(dǎo)致鏈表大于 TREEIFY_THRESHOLD = 8 時(shí)钠右，就把鏈表轉(zhuǎn)換成紅黑樹(shù)）
獲取對(duì)象時(shí)赋元，將 K 傳給 get() 方法：①、調(diào)用 hash(K) 方法（計(jì)算 K 的 hash 值）從而獲取該鍵值所在鏈表的數(shù)組下標(biāo)飒房；②搁凸、順序遍歷鏈表，equals()方法查找相同 Node 鏈表中 K 值對(duì)應(yīng)的 V 值狠毯。
hashCode 是定位的护糖，存儲(chǔ)位置；equals是定性的嚼松，比較兩者是否相等嫡良。
3.當(dāng)兩個(gè)對(duì)象的 hashCode 相同會(huì)發(fā)生什么？
因?yàn)?hashCode 相同献酗，不一定就是相等的（equals方法比較）寝受，所以?xún)蓚€(gè)對(duì)象所在數(shù)組的下標(biāo)相同，"碰撞"就此發(fā)生罕偎。又因?yàn)?HashMap 使用鏈表存儲(chǔ)對(duì)象羡蛾，這個(gè) Node 會(huì)存儲(chǔ)到鏈表中。
4.你知道 hash 的實(shí)現(xiàn)嗎？為什么要這樣實(shí)現(xiàn)痴怨？
JDK 1.8 中忙干，是通過(guò) hashCode() 的高 16 位異或低 16 位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度浪藻，功效和質(zhì)量來(lái)考慮的捐迫，減少系統(tǒng)的開(kāi)銷(xiāo)，也不會(huì)造成因?yàn)楦呶粵](méi)有參與下標(biāo)的計(jì)算爱葵，從而引起的碰撞施戴。
5.為什么要用異或運(yùn)算符？
保證了對(duì)象的 hashCode 的 32 位值只要有一位發(fā)生改變萌丈，整個(gè) hash() 返回值就會(huì)改變赞哗。盡可能的減少碰撞。
6.HashMap 的 table 的容量如何確定辆雾？loadFactor 是什么肪笋？該容量如何變化？這種變化會(huì)帶來(lái)什么問(wèn)題度迂？
①藤乙、table 數(shù)組大小是由 capacity 這個(gè)參數(shù)確定的，默認(rèn)是16惭墓，也可以構(gòu)造時(shí)傳入坛梁，最大限制是1<<30；
②腊凶、loadFactor 是裝載因子划咐，主要目的是用來(lái)確認(rèn)table 數(shù)組是否需要?jiǎng)討B(tài)擴(kuò)展，默認(rèn)值是0.75钧萍，比如table 數(shù)組大小為 16尖殃，裝載因子為 0.75 時(shí)，threshold 就是12划煮，當(dāng) table 的實(shí)際大小超過(guò) 12 時(shí)，table就需要?jiǎng)討B(tài)擴(kuò)容缔俄；
③弛秋、擴(kuò)容時(shí)，調(diào)用 resize() 方法俐载，將 table 長(zhǎng)度變?yōu)樵瓉?lái)的兩倍（注意是 table 長(zhǎng)度蟹略，而不是 threshold）
④、如果數(shù)據(jù)很大的情況下遏佣，擴(kuò)展時(shí)將會(huì)帶來(lái)性能的損失挖炬，在性能要求很高的地方，這種損失很可能很致命状婶。
7.HashMap中put方法的過(guò)程意敛？
答：“調(diào)用哈希函數(shù)獲取Key對(duì)應(yīng)的hash值馅巷，再計(jì)算其數(shù)組下標(biāo)；
如果沒(méi)有出現(xiàn)哈希沖突草姻，則直接放入數(shù)組钓猬；如果出現(xiàn)哈希沖突，則以鏈表的方式放在鏈表后面撩独；
如果鏈表長(zhǎng)度超過(guò)閥值( TREEIFY THRESHOLD==8)敞曹，就把鏈表轉(zhuǎn)成紅黑樹(shù)，鏈表長(zhǎng)度低于6综膀，就把紅黑樹(shù)轉(zhuǎn)回鏈表;
如果結(jié)點(diǎn)的key已經(jīng)存在澳迫，則替換其value即可；
如果集合中的鍵值對(duì)大于12剧劝，調(diào)用resize方法進(jìn)行數(shù)組擴(kuò)容橄登。”
8.數(shù)組擴(kuò)容的過(guò)程担平？
創(chuàng)建一個(gè)新的數(shù)組示绊，其容量為舊數(shù)組的兩倍，并重新計(jì)算舊數(shù)組中結(jié)點(diǎn)的存儲(chǔ)位置暂论。結(jié)點(diǎn)在新數(shù)組中的位置只有兩種面褐，原下標(biāo)位置或原下標(biāo)+舊數(shù)組的大小。
9.拉鏈法導(dǎo)致的鏈表過(guò)深問(wèn)題為什么不用二叉查找樹(shù)代替取胎，而選擇紅黑樹(shù)展哭？為什么不一直使用紅黑樹(shù)？
之所以選擇紅黑樹(shù)是為了解決二叉查找樹(shù)的缺陷闻蛀，二叉查找樹(shù)在特殊情況下會(huì)變成一條線(xiàn)性結(jié)構(gòu)（這就跟原來(lái)使用鏈表結(jié)構(gòu)一樣了匪傍，造成很深的問(wèn)題），遍歷查找會(huì)非常慢觉痛。
而紅黑樹(shù)在插入新數(shù)據(jù)后可能需要通過(guò)左旋役衡，右旋、變色這些操作來(lái)保持平衡薪棒，引入紅黑樹(shù)就是為了查找數(shù)據(jù)塊手蝎，解決鏈表查詢(xún)深度的問(wèn)題，我們知道紅黑樹(shù)屬于平衡二叉樹(shù)俐芯，但是為了保持“平衡”是需要付出代價(jià)的棵介，但是該代價(jià)所損耗的資源要比遍歷線(xiàn)性鏈表要少，所以當(dāng)長(zhǎng)度大于8的時(shí)候吧史，會(huì)使用紅黑樹(shù)邮辽，如果鏈表長(zhǎng)度很短的話(huà)，根本不需要引入紅黑樹(shù)，引入反而會(huì)慢吨述。
10.說(shuō)說(shuō)你對(duì)紅黑樹(shù)的見(jiàn)解岩睁？
每個(gè)節(jié)點(diǎn)非紅即黑
根節(jié)點(diǎn)總是黑色的
如果節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的（反之不一定）
每個(gè)葉子節(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中對(duì)HashMap做了哪些改變笙僚？
在java 1.8中，如果鏈表的長(zhǎng)度超過(guò)了8灵再，那么鏈表將轉(zhuǎn)換為紅黑樹(shù)肋层。（桶的數(shù)量必須大于64，小于64的時(shí)候只會(huì)擴(kuò)容）關(guān)注微信公眾號(hào)：Java大后端翎迁，在后臺(tái)回復(fù)：資料栋猖，可以獲取架構(gòu)師資源干貨。
發(fā)生hash碰撞時(shí)汪榔，java 1.7 會(huì)在鏈表的頭部插入蒲拉，而java 1.8會(huì)在鏈表的尾部插入
在java 1.8中，Entry被Node替代(換了一個(gè)馬甲)痴腌。
12.HashMap雌团，LinkedHashMap，TreeMap 有什么區(qū)別士聪？
LinkedHashMap 保存了記錄的插入順序锦援，在用 Iterator 遍歷時(shí)，先取到的記錄肯定是先插入的剥悟；遍歷比 HashMap 慢灵寺；
TreeMap 實(shí)現(xiàn) SortMap 接口，能夠把它保存的記錄根據(jù)鍵排序（默認(rèn)按鍵值升序排序区岗，也可以指定排序的比較器）
13.HashMap & TreeMap & LinkedHashMap 使用場(chǎng)景略板？
一般情況下，使用最多的是 HashMap慈缔。
HashMap：在 Map 中插入叮称、刪除和定位元素時(shí)；
TreeMap：在需要按自然順序或自定義順序遍歷鍵的情況下藐鹤；
LinkedHashMap：在需要輸出的順序和輸入的順序相同的情況下瓤檐。
14.HashMap 和 HashTable 有什么區(qū)別？
①教藻、HashMap 是線(xiàn)程不安全的，HashTable 是線(xiàn)程安全的右锨；
②括堤、由于線(xiàn)程安全，所以 HashTable 的效率比不上 HashMap；
③悄窃、HashMap最多只允許一條記錄的鍵為null讥电，允許多條記錄的值為null，而 HashTable不允許轧抗；
④恩敌、HashMap 默認(rèn)初始化數(shù)組的大小為16，HashTable 為 11横媚，前者擴(kuò)容時(shí)纠炮，擴(kuò)大兩倍，后者擴(kuò)大兩倍+1灯蝴；
⑤恢口、HashMap 需要重新計(jì)算 hash 值，而 HashTable 直接使用對(duì)象的 hashCode
15.Java 中的另一個(gè)線(xiàn)程安全的與 HashMap 極其類(lèi)似的類(lèi)是什么穷躁？同樣是線(xiàn)程安全耕肩，它與 HashTable 在線(xiàn)程同步上有什么不同？
ConcurrentHashMap 類(lèi)（是 Java并發(fā)包 java.util.concurrent 中提供的一個(gè)線(xiàn)程安全且高效的 HashMap 實(shí)現(xiàn)）问潭。
HashTable 是使用 synchronize 關(guān)鍵字加鎖的原理（就是對(duì)對(duì)象加鎖）猿诸；
而針對(duì) ConcurrentHashMap，在 JDK 1.7 中采用 分段鎖的方式狡忙；JDK 1.8 中直接采用了CAS（無(wú)鎖算法）+ synchronized梳虽。
16.HashMap & ConcurrentHashMap 的區(qū)別？
除了加鎖去枷，原理上無(wú)太大區(qū)別怖辆。另外，HashMap 的鍵值對(duì)允許有null删顶，但是ConCurrentHashMap 都不允許竖螃。
17.為什么 ConcurrentHashMap 比 HashTable 效率要高？
HashTable 使用一把鎖（鎖住整個(gè)鏈表結(jié)構(gòu)）處理并發(fā)問(wèn)題逗余，多個(gè)線(xiàn)程競(jìng)爭(zhēng)一把鎖特咆，容易阻塞；
ConcurrentHashMap
JDK 1.7 中使用分段鎖（ReentrantLock + Segment + HashEntry）录粱，相當(dāng)于把一個(gè) HashMap 分成多個(gè)段腻格，每段分配一把鎖，這樣支持多線(xiàn)程訪(fǎng)問(wèn)啥繁。鎖粒度：基于 Segment菜职，包含多個(gè) HashEntry。
JDK 1.8 中使用 CAS + synchronized + Node + 紅黑樹(shù)旗闽。鎖粒度：Node（首結(jié)點(diǎn)）（實(shí)現(xiàn) Map.Entry）酬核。鎖粒度降低了蜜另。
18.針對(duì) ConcurrentHashMap 鎖機(jī)制具體分析（JDK 1.7 VS JDK 1.8）？
JDK 1.7 中嫡意，采用分段鎖的機(jī)制举瑰，實(shí)現(xiàn)并發(fā)的更新操作，底層采用數(shù)組+鏈表的存儲(chǔ)結(jié)構(gòu)蔬螟，包括兩個(gè)核心靜態(tài)內(nèi)部類(lèi) Segment 和 HashEntry此迅。
①、Segment 繼承 ReentrantLock（重入鎖） 用來(lái)充當(dāng)鎖的角色旧巾，每個(gè) Segment 對(duì)象守護(hù)每個(gè)散列映射表的若干個(gè)桶耸序；
②、HashEntry 用來(lái)封裝映射表的鍵-值對(duì)菠齿；
③佑吝、每個(gè)桶是由若干個(gè) HashEntry 對(duì)象鏈接起來(lái)的鏈表
JDK 1.8 中，采用Node + CAS + Synchronized來(lái)保證并發(fā)安全绳匀。取消類(lèi) Segment芋忿，直接用 table 數(shù)組存儲(chǔ)鍵值對(duì)；當(dāng) HashEntry 對(duì)象組成的鏈表長(zhǎng)度超過(guò) TREEIFY_THRESHOLD 時(shí)疾棵，鏈表轉(zhuǎn)換為紅黑樹(shù)戈钢，提升性能。底層變更為數(shù)組 + 鏈表 + 紅黑樹(shù)是尔。
19.ConcurrentHashMap 在 JDK 1.8 中殉了，為什么要使用內(nèi)置鎖 synchronized 來(lái)代替重入鎖 ReentrantLock？
①拟枚、粒度降低了薪铜；
②、JVM 開(kāi)發(fā)團(tuán)隊(duì)沒(méi)有放棄 synchronized恩溅，而且基于 JVM 的 synchronized 優(yōu)化空間更大隔箍，更加自然。
③脚乡、在大量的數(shù)據(jù)操作下蜒滩，對(duì)于 JVM 的內(nèi)存壓力，基于 API 的 ReentrantLock 會(huì)開(kāi)銷(xiāo)更多的內(nèi)存奶稠。
20.ConcurrentHashMap 簡(jiǎn)單介紹俯艰？
①、重要的常量：
private transient volatile int sizeCtl;
當(dāng)為負(fù)數(shù)時(shí)锌订，-1 表示正在初始化竹握，-N 表示 N - 1 個(gè)線(xiàn)程正在進(jìn)行擴(kuò)容；
當(dāng)為 0 時(shí)辆飘，表示 table 還沒(méi)有初始化啦辐；
當(dāng)為其他正數(shù)時(shí)污秆，表示初始化或者下一次進(jìn)行擴(kuò)容的大小。
②昧甘、數(shù)據(jù)結(jié)構(gòu)：
Node 是存儲(chǔ)結(jié)構(gòu)的基本單元，繼承 HashMap 中的 Entry战得，用于存儲(chǔ)數(shù)據(jù)充边；
TreeNode 繼承 Node，但是數(shù)據(jù)結(jié)構(gòu)換成了二叉樹(shù)結(jié)構(gòu)常侦，是紅黑樹(shù)的存儲(chǔ)結(jié)構(gòu)浇冰，用于紅黑樹(shù)中存儲(chǔ)數(shù)據(jù)；
TreeBin 是封裝 TreeNode 的容器聋亡，提供轉(zhuǎn)換紅黑樹(shù)的一些條件和鎖的控制肘习。
③、存儲(chǔ)對(duì)象時(shí)（put() 方法）：
如果沒(méi)有初始化坡倔，就調(diào)用 initTable() 方法來(lái)進(jìn)行初始化漂佩；
如果沒(méi)有 hash 沖突就直接 CAS 無(wú)鎖插入；
如果需要擴(kuò)容罪塔，就先進(jìn)行擴(kuò)容投蝉；
如果存在 hash 沖突，就加鎖來(lái)保證線(xiàn)程安全征堪，兩種情況：一種是鏈表形式就直接遍歷到尾端插入瘩缆，一種是紅黑樹(shù)就按照紅黑樹(shù)結(jié)構(gòu)插入；
如果該鏈表的數(shù)量大于閥值 8佃蚜，就要先轉(zhuǎn)換成紅黑樹(shù)的結(jié)構(gòu)庸娱，break 再一次進(jìn)入循環(huán)
如果添加成功就調(diào)用 addCount() 方法統(tǒng)計(jì) size，并且檢查是否需要擴(kuò)容谐算。
④熟尉、擴(kuò)容方法 transfer()：默認(rèn)容量為 16，擴(kuò)容時(shí)氯夷，容量變?yōu)樵瓉?lái)的兩倍臣樱。
helpTransfer()：調(diào)用多個(gè)工作線(xiàn)程一起幫助進(jìn)行擴(kuò)容，這樣的效率就會(huì)更高腮考。
⑤雇毫、獲取對(duì)象時(shí)（get()方法）：
計(jì)算 hash 值，定位到該 table 索引位置踩蔚，如果是首結(jié)點(diǎn)符合就返回棚放；
如果遇到擴(kuò)容時(shí)，會(huì)調(diào)用標(biāo)記正在擴(kuò)容結(jié)點(diǎn) ForwardingNode.find()方法馅闽，查找該結(jié)點(diǎn)飘蚯，匹配就返回馍迄；
以上都不符合的話(huà)，就往下遍歷結(jié)點(diǎn)局骤，匹配就返回攀圈，否則最后就返回 null。
21.ConcurrentHashMap 的并發(fā)度是什么峦甩？
程序運(yùn)行時(shí)能夠同時(shí)更新 ConccurentHashMap 且不產(chǎn)生鎖競(jìng)爭(zhēng)的最大線(xiàn)程數(shù)赘来。默認(rèn)為 16，且可以在構(gòu)造函數(shù)中設(shè)置凯傲。
當(dāng)用戶(hù)設(shè)置并發(fā)度時(shí)犬辰，ConcurrentHashMap 會(huì)使用大于等于該值的最小2冪指數(shù)作為實(shí)際并發(fā)度（假如用戶(hù)設(shè)置并發(fā)度為17，實(shí)際并發(fā)度則為32）
</article>
33人點(diǎn)贊
