JAVA HashMap 面試奪命二十一問！
JAVA HashMap 面試奪命二十一問！
資料來源:https://mp.weixin.qq.com/s?__biz=MzA5MTkxMDQ4MQ==&mid=2648936321&idx=2&sn=a5100391a5bdadb102fb60f97deaf697&chksm=886217bfbf159ea90a3e91500640ebc0e7a7e437736c68a06c1bca6c9b98d8c6b0126f43c215&scene=126&sessionid=1597817836&key=391633c74d74d5c58f9fd289979062fe0d767279ed7ad191014b98f83ed68bad88121d1b3ba862535caf805c8186bb4cf5210338b6809d18dfe894cfa00294a6bdbe2a79b03ab5fd7ee5562bb6e4ee27852d74c26e134191defc367d5c8121405eb20218b69849ff33ec2f94059b48e2eeb07b57c9ee37a67d9691587c1daec7&ascene=1&uin=MjIwODk2NDgxNw%3D%3D&devicetype=Windows+10+x64&version=62090529&lang=zh_TW&exportkey=AtkIKpNQIDPRJN0AFVYjcCM%3D&pass_ticket=azVX3PgoGyNwvaTt8aCwT2BaG2X%2Fp04P6jW3NVzgpwO7%2FvJgbkifDdjpyQO9dFbI
1：HashMap 的數據結構？
哈希表結構（鍊錶散列：數組+鍊錶）實現，結合數組和鍊錶的優點。當鍊錶長度超過8 時，鍊錶轉換為紅黑樹。
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 會存儲到鍊錶中。為什麼要重寫hashcode 和equals 方法？推薦看下。
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 有什麼區別？
HashMap 參考其他問題；
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）