1：HashMap 的資料結構？
A：哈希表結構（連結清單散列：數組+連結清單）實作，結合數組和連結清單的優點。當連結清單長度超過 8 時，連結清單轉換為紅黑樹。
transient Node<K,V>\[\] table; 2：HashMap 的工作原理？
HashMap 底層是 hash 數組和單向連結清單實作，數組中的每個元素都是連結清單，由 Node 内部類（實作 Map.Entry接口）實作，HashMap 通過 put & get 方法存儲和擷取。
存儲對象時，将 K/V 鍵值傳給 put() 方法：
①、調用 hash(K) 方法計算 K 的 hash 值，然後結合數組長度，計算得數組下标；
②、調整數組大小（當容器中的元素個數大于 capacity * loadfactor 時，容器會進行擴容resize 為 2n）；
③、i.如果 K 的 hash 值在 HashMap 中不存在，則執行插入，若存在，則發生碰撞；
ii.如果 K 的 hash 值在 HashMap 中存在，且它們兩者 equals 傳回 true，則更新鍵值對；
iii. 如果 K 的 hash 值在 HashMap 中存在，且它們兩者 equals 傳回 false，則插傳入連結表的尾部（尾插法）或者紅黑樹中（樹的添加方式）。
（JDK 1.7 之前使用頭插法、JDK 1.8 使用尾插法）（注意：當碰撞導緻連結清單大于 TREEIFY_THRESHOLD = 8 時，就把連結清單轉換成紅黑樹）
擷取對象時，将 K 傳給 get() 方法：①、調用 hash(K) 方法（計算 K 的 hash 值）進而擷取該鍵值所在連結清單的數組下标；②、順序周遊連結清單，equals()方法查找相同 Node 連結清單中 K 值對應的 V 值。
hashCode 是定位的，存儲位置；equals是定性的，比較兩者是否相等。
3.當兩個對象的 hashCode 相同會發生什麼？
因為 hashCode 相同，不一定就是相等的（equals方法比較），是以兩個對象所在數組的下标相同，"碰撞"就此發生。又因為 HashMap 使用連結清單存儲對象，這個 Node 會存儲到連結清單中。
4.你知道 hash 的實作嗎？為什麼要這樣實作？
JDK 1.8 中，是通過 hashCode() 的高 16 位異或低 16 位實作的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度，功效和品質來考慮的，減少系統的開銷，也不會造成因為高位沒有參與下标的計算，進而引起的碰撞。
5.為什麼要用異或運算符？
保證了對象的 hashCode 的 32 位值隻要有一位發生改變，整個 hash() 傳回值就會改變。盡可能的減少碰撞。
6.HashMap 的 table 的容量如何确定？loadFactor 是什麼？該容量如何變化？這種變化會帶來什麼問題？
①、table 數組大小是由 capacity 這個參數确定的，預設是16，也可以構造時傳入，最大限制是1<<30；
②、loadFactor 是裝載因子，主要目的是用來确認table 數組是否需要動态擴充，預設值是0.75，比如table 數組大小為 16，裝載因子為 0.75 時，threshold 就是12，當 table 的實際大小超過 12 時，table就需要動态擴容；
③、擴容時，調用 resize() 方法，将 table 長度變為原來的兩倍（注意是 table 長度，而不是 threshold）
④、如果資料很大的情況下，擴充時将會帶來性能的損失，在性能要求很高的地方，這種損失很可能很緻命。
7.HashMap中put方法的過程？
答：“調用哈希函數擷取Key對應的hash值，再計算其數組下标；
如果沒有出現哈希沖突，則直接放入數組；如果出現哈希沖突，則以連結清單的方式放在連結清單後面；
如果連結清單長度超過閥值( TREEIFY THRESHOLD==8)，就把連結清單轉成紅黑樹，連結清單長度低于6，就把紅黑樹轉回連結清單;
如果結點的key已經存在，則替換其value即可；
如果集合中的鍵值對大于12，調用resize方法進行數組擴容。”
8.數組擴容的過程？
建立一個新的數組，其容量為舊數組的兩倍，并重新計算舊數組中結點的存儲位置。結點在新數組中的位置隻有兩種，原下标位置或原下标+舊數組的大小。
9.拉鍊法導緻的連結清單過深問題為什麼不用二叉查找樹代替，而選擇紅黑樹？為什麼不一直使用紅黑樹？
之是以選擇紅黑樹是為了解決二叉查找樹的缺陷，二叉查找樹在特殊情況下會變成一條線性結構（這就跟原來使用連結清單結構一樣了，造成很深的問題），周遊查找會非常慢。推薦：面試問紅黑樹，我臉都綠了。
而紅黑樹在插入新資料後可能需要通過左旋，右旋、變色這些操作來保持平衡，引入紅黑樹就是為了查找資料快，解決連結清單查詢深度的問題，我們知道紅黑樹屬于平衡二叉樹，但是為了保持“平衡”是需要付出代價的，但是該代價所損耗的資源要比周遊線性連結清單要少，是以當長度大于8的時候，會使用紅黑樹，如果連結清單長度很短的話，根本不需要引入紅黑樹，引入反而會慢。
10.說說你對紅黑樹的見解？
- 每個節點非紅即黑
- 根節點總是黑色的
- 如果節點是紅色的，則它的子節點必須是黑色的（反之不一定）
- 每個葉子節點都是黑色的空節點（NIL節點）
- 從根節點到葉節點或空子節點的每條路徑，必須包含相同數目的黑色節點（即相同的黑色高度）
11.jdk8中對HashMap做了哪些改變？
在java 1.8中，如果連結清單的長度超過了8，那麼連結清單将轉換為紅黑樹。（桶的數量必須大于64，小于64的時候隻會擴容）
發生hash碰撞時，java 1.7 會在連結清單的頭部插入，而java 1.8會在連結清單的尾部插入
在java 1.8中，Entry被Node替代(換了一個馬甲。
12.HashMap，LinkedHashMap，TreeMap 有什麼差別？
LinkedHashMap 儲存了記錄的插入順序，在用 Iterator 周遊時，先取到的記錄肯定是先插入的；周遊比 HashMap 慢；
TreeMap 實作 SortMap 接口，能夠把它儲存的記錄根據鍵排序（預設按鍵值升序排序，也可以指定排序的比較器）
13.HashMap & TreeMap & LinkedHashMap 使用場景？
一般情況下，使用最多的是 HashMap。
HashMap：在 Map 中插入、删除和定位元素時；
TreeMap：在需要按自然順序或自定義順序周遊鍵的情況下；
LinkedHashMap：在需要輸出的順序和輸入的順序相同的情況下。
14.HashMap 和 HashTable 有什麼差別？
①、HashMap 是線程不安全的，HashTable 是線程安全的；
②、由于線程安全，是以 HashTable 的效率比不上 HashMap；
③、HashMap最多隻允許一條記錄的鍵為null，允許多條記錄的值為null，而 HashTable不允許；
④、HashMap 預設初始化數組的大小為16，HashTable 為 11，前者擴容時，擴大兩倍，後者擴大兩倍+1；
⑤、HashMap 需要重新計算 hash 值，而 HashTable 直接使用對象的 hashCode
15.Java 中的另一個線程安全的與 HashMap 極其類似的類是什麼？同樣是線程安全，它與 HashTable 線上程同步上有什麼不同？
ConcurrentHashMap 類（是 Java并發包 java.util.concurrent 中提供的一個線程安全且高效的 HashMap 實作）。
HashTable 是使用 synchronize 關鍵字加鎖的原理（就是對對象加鎖）；
而針對 ConcurrentHashMap，在 JDK 1.7 中采用 分段鎖的方式；JDK 1.8 中直接采用了CAS（無鎖算法）+ synchronized。
16.HashMap & ConcurrentHashMap 的差別？
除了加鎖，原理上無太大差別。另外，HashMap 的鍵值對允許有null，但是ConCurrentHashMap 都不允許。
17.為什麼 ConcurrentHashMap 比 HashTable 效率要高？
HashTable 使用一把鎖（鎖住整個連結清單結構）處理并發問題，多個線程競争一把鎖，容易阻塞；
ConcurrentHashMap
- JDK 1.7 中使用分段鎖（ReentrantLock + Segment + HashEntry），相當于把一個 HashMap 分成多個段，每段配置設定一把鎖，這樣支援多線程通路。鎖粒度：基于 Segment，包含多個 HashEntry。
- JDK 1.8 中使用 CAS + synchronized + Node + 紅黑樹。鎖粒度：Node（首結點）（實作 Map.Entry）。鎖粒度降低了。
18.針對 ConcurrentHashMap 鎖機制具體分析（JDK 1.7 VS JDK 1.8）
JDK 1.7 中，采用分段鎖的機制，實作并發的更新操作，底層采用數組+連結清單的存儲結構，包括兩個核心靜态内部類 Segment 和 HashEntry。
①、Segment 繼承 ReentrantLock（重入鎖） 用來充當鎖的角色，每個 Segment 對象守護每個散列映射表的若幹個桶；
②、HashEntry 用來封裝映射表的鍵-值對；
③、每個桶是由若幹個 HashEntry 對象連結起來的連結清單
JDK 1.8 中，采用Node + CAS + Synchronized來保證并發安全。取消類 Segment，直接用 table 數組存儲鍵值對；當 HashEntry 對象組成的連結清單長度超過 TREEIFY_THRESHOLD 時，連結清單轉換為紅黑樹，提升性能。底層變更為數組 + 連結清單 + 紅黑樹。
19.ConcurrentHashMap 在 JDK 1.8 中，為什麼要使用内置鎖 synchronized 來代替重入鎖 ReentrantLock？
①、粒度降低了；
②、JVM 開發團隊沒有放棄 synchronized，而且基于 JVM 的 synchronized 優化空間更大，更加自然。
③、在大量的資料操作下，對于 JVM 的記憶體壓力，基于 API 的 ReentrantLock 會開銷更多的記憶體。
20.ConcurrentHashMap 簡單介紹？
①、重要的常量：
private transient volatile int sizeCtl;
當為負數時，-1 表示正在初始化，-N 表示 N - 1 個線程正在進行擴容；
當為 0 時，表示 table 還沒有初始化；
當為其他正數時，表示初始化或者下一次進行擴容的大小。
②、資料結構：
Node 是存儲結構的基本單元，繼承 HashMap 中的 Entry，用于存儲資料；
TreeNode 繼承 Node，但是資料結構換成了二叉樹結構，是紅黑樹的存儲結構，用于紅黑樹中存儲資料；
TreeBin 是封裝 TreeNode 的容器，提供轉換紅黑樹的一些條件和鎖的控制。
③、存儲對象時（put() 方法）：
如果沒有初始化，就調用 initTable() 方法來進行初始化；
如果沒有 hash 沖突就直接 CAS 無鎖插入；
如果需要擴容，就先進行擴容；
如果存在 hash 沖突，就加鎖來保證線程安全，兩種情況：一種是連結清單形式就直接周遊到尾端插入，一種是紅黑樹就按照紅黑樹結構插入；
如果該連結清單的數量大于閥值 8，就要先轉換成紅黑樹的結構，break 再一次進入循環
如果添加成功就調用 addCount() 方法統計 size，并且檢查是否需要擴容。
④、擴容方法 transfer()：預設容量為 16，擴容時，容量變為原來的兩倍。
helpTransfer()：調用多個工作線程一起幫助進行擴容，這樣的效率就會更高。
⑤、擷取對象時（get()方法）：
計算 hash 值，定位到該 table 索引位置，如果是首結點符合就傳回；
如果遇到擴容時，會調用标記正在擴容結點 ForwardingNode.find()方法，查找該結點，比對就傳回；
以上都不符合的話，就往下周遊結點，比對就傳回，否則最後就傳回 null。
21.ConcurrentHashMap 的并發度是什麼？
程式運作時能夠同時更新 ConccurentHashMap 且不産生鎖競争的最大線程數。預設為 16，且可以在構造函數中設定。
當使用者設定并發度時，ConcurrentHashMap 會使用大于等于該值的最小2幂指數作為實際并發度（假如使用者設定并發度為17，實際并發度則為32）
原作者：菜鳥小于