1：HashMap 的數(shù)據(jù)結構屎债？
2：HashMap 的工作原理仅政？
3.當兩個對象的 hashCode 相同會發(fā)生什么？
4.你知道 hash 的實現(xiàn)嗎盆驹？為什么要這樣實現(xiàn)圆丹？
5.為什么要用異或運算符？
6.HashMap 的 table 的容量如何確定躯喇？loadFactor 是什么辫封？該容量如何變化？這種變化會帶來什么問題廉丽？
7.HashMap中put方法的過程倦微？
8.數(shù)組擴容的過程？
9.拉鏈法導致的鏈表過深問題為什么不用二叉查找樹代替正压，而選擇紅黑樹欣福？為什么不一直使用紅黑樹？
10.說說你對紅黑樹的見解蔑匣？
11.jdk8中對HashMap做了哪些改變？
12.HashMap棕诵，LinkedHashMap裁良，TreeMap 有什么區(qū)別？
13.HashMap & TreeMap & LinkedHashMap 使用場景校套？
14.HashMap 和 HashTable 有什么區(qū)別价脾？
15.Java 中的另一個線程安全的與 HashMap 極其類似的類是什么？同樣是線程安全笛匙，它與 HashTable 在線程同步上有什么不同侨把？
16.HashMap & ConcurrentHashMap 的區(qū)別犀变？
17.為什么 ConcurrentHashMap 比 HashTable 效率要高？
18.針對 ConcurrentHashMap 鎖機制具體分析（JDK 1.7 VS JDK 1.8）
19.ConcurrentHashMap 在 JDK 1.8 中秋柄，為什么要使用內(nèi)置鎖 synchronized 來代替重入鎖 ReentrantLock获枝？
20.ConcurrentHashMap 簡單介紹？
21.ConcurrentHashMap 的并發(fā)度是什么骇笔？
1：HashMap 的數(shù)據(jù)結構省店？
A：哈希表結構（鏈表散列：數(shù)組+鏈表）實現(xiàn)，結合數(shù)組和鏈表的優(yōu)點笨触。當鏈表長度超過 8 時懦傍，鏈表轉換為紅黑樹。
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 值废麻，然后結合數(shù)組長度，計算得數(shù)組下標模庐；
②烛愧、調(diào)整數(shù)組大小（當容器中的元素個數(shù)大于 capacity * loadfactor 時掂碱，容器會進行擴容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 使用尾插法）（注意：當碰撞導致鏈表大于 TREEIFY_THRESHOLD = 8 時，就把鏈表轉換成紅黑樹）
獲取對象時，將 K 傳給 get() 方法：①颅崩、調(diào)用 hash(K) 方法（計算 K 的 hash 值）從而獲取該鍵值所在鏈表的數(shù)組下標几于；②、順序遍歷鏈表沿后，equals()方法查找相同 Node 鏈表中 K 值對應的 V 值沿彭。
hashCode 是定位的，存儲位置得运；equals是定性的膝蜈，比較兩者是否相等。
3.當兩個對象的 hashCode 相同會發(fā)生什么熔掺？
因為 hashCode 相同饱搏，不一定就是相等的（equals方法比較），所以兩個對象所在數(shù)組的下標相同置逻，"碰撞"就此發(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)的開銷他挎，也不會造成因為高位沒有參與下標的計算筝尾，從而引起的碰撞。
5.為什么要用異或運算符办桨？
保證了對象的 hashCode 的 32 位值只要有一位發(fā)生改變筹淫，整個 hash() 返回值就會改變。盡可能的減少碰撞呢撞。
6.HashMap 的 table 的容量如何確定损姜？loadFactor 是什么？該容量如何變化殊霞？這種變化會帶來什么問題摧阅？
①、table 數(shù)組大小是由 capacity 這個參數(shù)確定的脓鹃，默認是16逸尖，也可以構造時傳入古沥，最大限制是1<<30瘸右；
②娇跟、loadFactor 是裝載因子，主要目的是用來確認table 數(shù)組是否需要動態(tài)擴展太颤，默認值是0.75苞俘，比如table 數(shù)組大小為 16，裝載因子為 0.75 時龄章，threshold 就是12吃谣，當 table 的實際大小超過 12 時，table就需要動態(tài)擴容做裙；
③岗憋、擴容時，調(diào)用 resize() 方法锚贱，將 table 長度變?yōu)樵瓉淼膬杀叮ㄗ⒁馐?table 長度仔戈，而不是 threshold）
④、如果數(shù)據(jù)很大的情況下拧廊，擴展時將會帶來性能的損失监徘，在性能要求很高的地方，這種損失很可能很致命吧碾。
7.HashMap中put方法的過程凰盔？
答：“調(diào)用哈希函數(shù)獲取Key對應的hash值，再計算其數(shù)組下標倦春；
如果沒有出現(xiàn)哈希沖突户敬，則直接放入數(shù)組；如果出現(xiàn)哈希沖突溅漾，則以鏈表的方式放在鏈表后面山叮；
如果鏈表長度超過閥值( TREEIFY THRESHOLD==8)，就把鏈表轉成紅黑樹添履，鏈表長度低于6屁倔，就把紅黑樹轉回鏈表;
如果結點的key已經(jīng)存在，則替換其value即可暮胧；
如果集合中的鍵值對大于12锐借，調(diào)用resize方法進行數(shù)組擴容⊥裕”
8.數(shù)組擴容的過程钞翔？
創(chuàng)建一個新的數(shù)組，其容量為舊數(shù)組的兩倍席舍，并重新計算舊數(shù)組中結點的存儲位置布轿。結點在新數(shù)組中的位置只有兩種，原下標位置或原下標+舊數(shù)組的大小。
9.拉鏈法導致的鏈表過深問題為什么不用二叉查找樹代替汰扭，而選擇紅黑樹稠肘？為什么不一直使用紅黑樹？
之所以選擇紅黑樹是為了解決二叉查找樹的缺陷萝毛，二叉查找樹在特殊情況下會變成一條線性結構（這就跟原來使用鏈表結構一樣了项阴，造成很深的問題），遍歷查找會非常慢笆包。推薦：面試問紅黑樹环揽，我臉都綠了。
而紅黑樹在插入新數(shù)據(jù)后可能需要通過左旋庵佣，右旋歉胶、變色這些操作來保持平衡，引入紅黑樹就是為了查找數(shù)據(jù)快巴粪，解決鏈表查詢深度的問題跨扮，我們知道紅黑樹屬于平衡二叉樹，但是為了保持“平衡”是需要付出代價的验毡，但是該代價所損耗的資源要比遍歷線性鏈表要少衡创，所以當長度大于8的時候，會使用紅黑樹晶通，如果鏈表長度很短的話璃氢，根本不需要引入紅黑樹，引入反而會慢狮辽。
10.說說你對紅黑樹的見解一也？
每個節(jié)點非紅即黑
根節(jié)點總是黑色的
如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的（反之不一定）
每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）
從根節(jié)點到葉節(jié)點或空子節(jié)點的每條路徑喉脖，必須包含相同數(shù)目的黑色節(jié)點（即相同的黑色高度）
11.jdk8中對HashMap做了哪些改變椰苟？
在java 1.8中，如果鏈表的長度超過了8树叽，那么鏈表將轉換為紅黑樹舆蝴。（桶的數(shù)量必須大于64，小于64的時候只會擴容）
發(fā)生hash碰撞時题诵，java 1.7 會在鏈表的頭部插入洁仗，而java 1.8會在鏈表的尾部插入
在java 1.8中，Entry被Node替代(換了一個馬甲性锭。
12.HashMap赠潦，LinkedHashMap，TreeMap 有什么區(qū)別草冈？
HashMap 參考其他問題她奥；
LinkedHashMap 保存了記錄的插入順序瓮增，在用 Iterator 遍歷時，先取到的記錄肯定是先插入的哩俭；遍歷比 HashMap 慢钉赁；
TreeMap 實現(xiàn) SortMap 接口，能夠把它保存的記錄根據(jù)鍵排序（默認按鍵值升序排序携茂，也可以指定排序的比較器）
13.HashMap & TreeMap & LinkedHashMap 使用場景？
一般情況下诅岩，使用最多的是 HashMap讳苦。
HashMap：在 Map 中插入、刪除和定位元素時吩谦；
TreeMap：在需要按自然順序或自定義順序遍歷鍵的情況下鸳谜；
LinkedHashMap：在需要輸出的順序和輸入的順序相同的情況下。
14.HashMap 和 HashTable 有什么區(qū)別式廷？
①咐扭、HashMap 是線程不安全的，HashTable 是線程安全的滑废；
②蝗肪、由于線程安全，所以 HashTable 的效率比不上 HashMap蠕趁；
③薛闪、HashMap最多只允許一條記錄的鍵為null，允許多條記錄的值為null俺陋，而 HashTable不允許豁延；
④、HashMap 默認初始化數(shù)組的大小為16腊状，HashTable 為 11诱咏，前者擴容時，擴大兩倍缴挖，后者擴大兩倍+1袋狞；
⑤、HashMap 需要重新計算 hash 值映屋，而 HashTable 直接使用對象的 hashCode
15.Java 中的另一個線程安全的與 HashMap 極其類似的類是什么硕并？同樣是線程安全，它與 HashTable 在線程同步上有什么不同秧荆？
ConcurrentHashMap 類（是 Java并發(fā)包 java.util.concurrent 中提供的一個線程安全且高效的 HashMap 實現(xiàn)）倔毙。
HashTable 是使用 synchronize 關鍵字加鎖的原理（就是對對象加鎖）；
而針對 ConcurrentHashMap乙濒，在 JDK 1.7 中采用 分段鎖的方式陕赃；JDK 1.8 中直接采用了CAS（無鎖算法）+ synchronized卵蛉。
16.HashMap & ConcurrentHashMap 的區(qū)別？
除了加鎖么库，原理上無太大區(qū)別傻丝。另外，HashMap 的鍵值對允許有null诉儒，但是ConCurrentHashMap 都不允許葡缰。
17.為什么 ConcurrentHashMap 比 HashTable 效率要高？
HashTable 使用一把鎖（鎖住整個鏈表結構）處理并發(fā)問題忱反，多個線程競爭一把鎖泛释，容易阻塞；
ConcurrentHashMap
JDK 1.7 中使用分段鎖（ReentrantLock + Segment + HashEntry）温算，相當于把一個 HashMap 分成多個段怜校，每段分配一把鎖，這樣支持多線程訪問注竿。鎖粒度：基于 Segment茄茁，包含多個 HashEntry。
JDK 1.8 中使用 CAS + synchronized + Node + 紅黑樹巩割。鎖粒度：Node（首結 點）（實現(xiàn) Map.Entry）裙顽。鎖粒度降低了。
18.針對 ConcurrentHashMap 鎖機制具體分析（JDK 1.7 VS JDK 1.8）
JDK 1.7 中宣谈，采用分段鎖的機制锦庸，實現(xiàn)并發(fā)的更新操作，底層采用數(shù)組+鏈表的存儲結構蒲祈，包括兩個核心靜態(tài)內(nèi)部類 Segment 和 HashEntry甘萧。
①、Segment 繼承 ReentrantLock（重入鎖） 用來充當鎖的角色梆掸，每個 Segment 對象守護每個散列映射表的若干個桶扬卷；
②、HashEntry 用來封裝映射表的鍵-值對酸钦；
③怪得、每個桶是由若干個 HashEntry 對象鏈接起來的鏈表
JDK 1.8 中，采用Node + CAS + Synchronized來保證并發(fā)安全卑硫。取消類 Segment徒恋，直接用 table 數(shù)組存儲鍵值對；當 HashEntry 對象組成的鏈表長度超過 TREEIFY_THRESHOLD 時欢伏，鏈表轉換為紅黑樹入挣，提升性能。底層變更為數(shù)組 + 鏈表 + 紅黑樹硝拧。
19.ConcurrentHashMap 在 JDK 1.8 中径筏，為什么要使用內(nèi)置鎖 synchronized 來代替重入鎖 ReentrantLock葛假？
①、粒度降低了滋恬；
②聊训、JVM 開發(fā)團隊沒有放棄 synchronized，而且基于 JVM 的 synchronized 優(yōu)化空間更大恢氯，更加自然带斑。
③、在大量的數(shù)據(jù)操作下勋拟，對于 JVM 的內(nèi)存壓力勋磕，基于 API 的 ReentrantLock 會開銷更多的內(nèi)存。
20.ConcurrentHashMap 簡單介紹指黎？
①、重要的常量：
private transient volatile int sizeCtl;
當為負數(shù)時州丹，-1 表示正在初始化醋安，-N 表示 N - 1 個線程正在進行擴容；
當為 0 時墓毒，表示 table 還沒有初始化吓揪；
當為其他正數(shù)時，表示初始化或者下一次進行擴容的大小所计。
②柠辞、數(shù)據(jù)結構：
Node 是存儲結構的基本單元，繼承 HashMap 中的 Entry主胧，用于存儲數(shù)據(jù)叭首；
TreeNode 繼承 Node，但是數(shù)據(jù)結構換成了二叉樹結構踪栋，是紅黑樹的存儲結構焙格，用于紅黑樹中存儲數(shù)據(jù)；
TreeBin 是封裝 TreeNode 的容器夷都，提供轉換紅黑樹的一些條件和鎖的控制眷唉。
③、存儲對象時（put() 方法）：
如果沒有初始化囤官，就調(diào)用 initTable() 方法來進行初始化冬阳；
如果沒有 hash 沖突就直接 CAS 無鎖插入；
如果需要擴容党饮，就先進行擴容肝陪；
如果存在 hash 沖突，就加鎖來保證線程安全刑顺，兩種情況：一種是鏈表形式就直接遍歷
到尾端插入见坑，一種是紅黑樹就按照紅黑樹結構插入嚷掠；
如果該鏈表的數(shù)量大于閥值 8，就要先轉換成紅黑樹的結構荞驴，break 再一次進入循環(huán)
如果添加成功就調(diào)用 addCount() 方法統(tǒng)計 size不皆，并且檢查是否需要擴容。
④熊楼、擴容方法 transfer()：默認容量為 16霹娄，擴容時，容量變?yōu)樵瓉淼膬杀丁?/p>
helpTransfer()：調(diào)用多個工作線程一起幫助進行擴容鲫骗，這樣的效率就會更高犬耻。
⑤、獲取對象時（get()方法）：
計算 hash 值执泰，定位到該 table 索引位置枕磁，如果是首結點符合就返回；
如果遇到擴容時术吝，會調(diào)用標記正在擴容結點 ForwardingNode.find()方法计济，查找該結點，匹配就返回排苍；
以上都不符合的話沦寂，就往下遍歷結點，匹配就返回淘衙，否則最后就返回 null传藏。
21.ConcurrentHashMap 的并發(fā)度是什么？
程序運行時能夠同時更新 ConccurentHashMap 且不產(chǎn)生鎖競爭的最大線程數(shù)彤守。默認為 16，且可以在構造函數(shù)中設置具垫。整理了一份Java面試寶典完整版PDF
當用戶設置并發(fā)度時，ConcurrentHashMap 會使用大于等于該值的最小2冪指數(shù)作為實際并發(fā)度（假如用戶設置并發(fā)度為17做修，實際并發(fā)度則為32）
