你參加的面試有人不問 hashmap 的嗎？ 單選
0
人0%
A.沒有
0
人0%
B.有
在 Java 基礎面試中，HashMap 似乎是每個面試官必問的一道題。
一、阿里開發手冊中對 HashMap 的描述
集合初始化時，指定集合初始值大小。
正例：initialCapacity = (需要存儲的元素個數 / 負載因子) + 1。注意負載因子（即loader factor）默認為 0.75，如果暫時無法確定初始值大小，請設置為 16（即默認值）。
反例：HashMap 需要放置 1024 個元素，由於沒有設置容量初始大小，隨著元素不斷增加，容 量 7 次被迫擴大，resize 需要重建 hash 表，嚴重影響性能
如果你看到這，思考下：
為什麼需要放置 1024 個元素，需要 7 次 擴容？？？
二、HashMap 的數據結構
hashmap 1.7 是 數組 + 單向鏈表
hashmap 1.8 是 數組 + 單向鏈表 + 紅黑樹
以下以 hashmap 1.8 說明
1、 基本屬性
特別注意：
除了常說的默認容量 16，負載因子 0.75，由於加入了紅黑樹，當鏈表轉為紅黑樹需要滿足 2 個必要條件：
① 鏈表長度到8
② 一個是數組長度到 64
簡單說，當你的鏈表長度即使到 8 ，但是數組長度小於 64 時，趕緊去擴容吧
2、鏈表結構
鏈表在Java7 叫 Entry 在 Java8 中叫 Node。
我們從下圖中可以看到鏈表結構是單鏈表。
紅黑樹的結構比較複雜，暫時忽略，有興趣的老鐵可自行研究，太傷腦細胞了
特別注意：
Java 8 之前是使用頭插法（認為後添加的元素會先被查詢），在 Java 8 改為尾插法。
由於多線程併發導致的擴容下，頭插法由於在併發的時候原來的順序被另外一個線程 a 顛倒了，而被掛起線程 b 恢復後拿擴容前的節點和順序繼續完成第一次循環後，又遵循 a 線程擴容後的鏈表順序重新排列鏈表中的順序，最終形成了環。
三、HashMap 如何解決衝突？？？
在說道 hashmap 如何解決衝突之前，我們先區分下 capacity 和 size 的區別？
1、容量 （ capacity）
比如我們的默認容量是 16，指的是數組的長度，而 size 指的是我們 put 的 key-value 個數
輸出結果：
capacity : 16
size : 1
問題：當我設置默認程度為 10，HashMap 的實際容量是 10 還是 16？
答案：16。在 tableSizeFor 的功能（不考慮大於最大容量的情況）是返回大於輸入參數且最近的 2 的整數次冪的數
2、hash 函數
Java 8 之前 hash 算法 return h & (length-1);
默認容量選擇 16 是為了 hash 算法平均分配到數組上
3、擴容
當 size 的個數 達到 （容量*負載因子）的值時，進行擴容。
四、HashMap 的時間複雜度？？？
Java 8 HashMap由數組+鏈表+紅黑樹組成的，數組是主體，鏈表是解決衝突，理想情況，不出現 hash 衝突，查找和增加的時間複雜度是 O(1)；如果出現 hash 衝突，查找和增加的時間複雜度是 O(n)。
五、HashMap 線程不安全體現在哪些地方？
1、Java 7 中的 HashMap
Java 7 HashMap 鏈表上的數據是按“頭插法”，“頭插法”可能導致死循環和數據丟失現象；
transfer 函數
① “頭插法” 死循環
請花幾分鐘瀏覽圖中的代碼
假設未擴容前是這個樣子
假設單線程下，擴容後：
單線程下沒啥問題
假設有兩個線程 A 和 B
線程 A 出現下列情況
線程 A 掛起，線程 B 開始，完成 resize 操作
到這步，應該不少老鐵看出問題了。線程 B k2 的下個節點是 k1，剛才掛起的線程 A 準備 hash k2，由於線程 B 的影響，會導致又回到 重新 hash k1，從而導致死循環。
2、Java 8 中的 HashMap
Java 8 中的 HashMap 使用了“尾插法”，避免了死循環問題。
當 線程 A 和線程 B 都執行到紅框處代碼時，
如果兩條不同數據的 hash 值相同，
並且該位置為 null，
會出現數據覆蓋的情況。
@Python大星 | 文
