這是 JsonChao 的第289期分享
前言HashMap 是我們熟悉的散列表實現，也是 「面試八股文」 的標準題庫之一。今天，我給出一份 HashMap 高頻面試題口述簡答答案，希望對你刷題有幫助。如果能幫上忙請務必點讚加關注，這對我非常重要。
1. 認識散列表1.1 散列表的作用散列算法是散列表的核心，也就做哈希算法或 Hash 算法，是一個意思。散列算法是一種將任意長度輸入轉換為固定長度輸出的算法，輸出的結果就是散列值。基於散列算法實現的散列表，可以實現快速查找元素的特性。
總結一下散列算法的主要性質：
性質描述1、單向性（基本性質）支持從輸入生成散列值，不支持從散列值反推輸入2、高效性（基本性質）單次散列運算計算量低3、一致性相同輸入重複計算，總是得到相同散列值4、隨機性散列值在輸出值域的分布儘量隨機5、輸入敏感性相似的數據，計算後的散列值差別很大1.2 什麼是散列衝突？散列算法一定是一種壓縮映射，因為輸入值域非常大甚至無窮大，而散列值域為一個固定長度的值域。例如，MD5 的輸出散列值為 128 位，SHA256 的輸出散列值為 256 位，這就存在 2 個不同的輸入產生相同輸出的可能性，即散列衝突，或哈希衝突、Hash Collision。
這其實只要用鴿巢原理（又稱：抽屜原理）就很好理解了，假設有 10 個鴿巢，現有 11 只鴿子，無論分配多麼平均，也肯定有一個鴿巢里有兩隻甚至多只鴿子。舉一個直接的例子，Java中的字符串 "Aa" 與 "BB" 的散列值就衝突了：
示例程序
Stringstr1="Aa";Stringstr2="BB";System.out.println(str1.hashCode());2112System.out.println(str2.hashCode());2112散列衝突
1.3 如何降低散列衝突概率雖然散列衝突是無法完全避免的，但可以儘可能降低發生散列衝突的概率。例如：
1、優化散列算法，提高散列值隨機性： 將散列值儘可能均勻分布到輸出值域的範圍內，避免出現 「堆積」 線程。否則，當大部分散列值都堆積在一小塊區域上時，勢必會增大衝突概率。例如，HashMap 保證容量為 2^n 次冪就是提高隨機性的方法。2、擴大輸出值域（即擴容）： 在散列值儘可能均勻分布的前提下，擴大輸出值域可以直接降低衝突概率。例如，HashMap 在達到閾值時執行擴容，本質上是擴大了輸出值域。2. HashMap 設計思路2.1 說一下 HashMap 的底層結構？HashMap 的底層結構是一個 「數組 + 拉鏈」 的二維結構，在 Java 7 中使用的是數組 + 鍊表，而在 Java 8 中當鍊表長度大於 8 時會轉換為紅黑樹。
那麼為什麼 HashMap 要採用這樣的設計呢？我分為 3 點來回答：
第 1 點：HashMap 的定義是一個散列表，這是一種支持快速查找元素的數據結構，那麼其背後就必然會使用到數組隨機訪問的特點。因此，HashMap 的一維結構就是一個數組，數組元素是一個包含 Key、Value 和 hashcode 的 Entry 節點。當我們需要訪問集合元素時，其實就是先通過 key 計算 hashcode，再將 hashCode 對數組長度取余得到數組下標，最後通過下標去數組中找到對應的 Value；第 2 點：從 Key 到數組下標的轉換過程必然是一個壓縮映射的過程，因為不同的 key 計算的 hashCode 可能相同，不同的 hashCode 取余得到的數組下標也可能相同，這就是哈希衝突。常規的哈希衝突解決方法有開放地址法和拉鏈法等，而 HashMap 採用的是拉鏈法來解決哈希衝突。第 3 點：為什麼 Java 8 要引入紅黑樹的設計呢？因為當衝突加劇的時候，在鍊表中尋找對應元素的時間複雜度是 O(n)，n 是鍊表長度。而使用紅黑樹（近似平衡的二叉搜索樹）的話，樹形結構的複雜度一般跟樹的高度有關，查找複雜度是 O(lgn)，時間複雜度更低。2.2 為什麼 HashMap 採用拉鏈法而不是開放地址法？我認為 Java 給予 HashMap 的定位是一個相對通用的散列表容器，它應該在面對各種輸入的時候都表現穩定。而開發地址法相對來說容易出現數據堆積，在數據量較大時可能出現連續衝突的情況，性能不夠穩定。
我們可以舉個反例，在 Java 原生的數據結構中，也存在使用開放地址法的散列表 —— 就是 ThreadlLocal。因為項目中不會大量使用 ThreadLocal 線程局部存儲，所以它是一個小規模數據場景，這裡使用開發地址法是沒問題的。
2.3 為什麼 HashMap 用紅黑樹而不是平衡二叉樹？紅黑樹和平衡二叉樹的區別在於它們的平衡強弱不同：
平衡二叉樹追求的是一種完全平衡的狀態，它的定義是任何結點的左右子樹的高度差不會超過 1，這樣的優勢是樹的結點是很平均分配的；紅黑樹不追求這種完全平衡，而是追求一種弱平衡的狀態，就是讓整個樹最長路徑不會超過最短路徑的 2 倍。這樣的話，紅黑樹雖然犧牲了一部分查找的性能效率，但是能夠換取一部分維持樹平衡狀態的成本。而我們知道 HashMap 的設計定位應該是一個相對通用的散列表，那麼它的設計者會希望這樣一個數據結構應該具備更強大的穩定性，因此它才選擇了紅黑樹。
3. HashMap 源碼細節3.1 HashMap 的初始容量HashMap 的初始容量是 0，這是一種懶加載機制，直到第一次 put 操作才會初始化數組大小，默認大小是 16。
3.2 HashMap 擴容擴容本質上是擴大了散列算法的輸出值域，在散列值儘可能均勻分布的前提下，擴大輸出值域可以直接降低衝突概率。當然，由於 HashMap 使用的是拉鏈法來解決散列衝突，擴容並不是必須的，但是不擴容的話會造成拉鏈的長度越來越長，導致散列表的時間複雜度會傾向於 O(n) 而不是 O(1)。
HashMap 擴容的觸發時機出現在元素個數超過閾值（容量 * loadFactor）的時候時，會將集合的一維數組擴大一倍，然後重新計算每個元素的位置。
3.3 為什麼 HashMap 的長度是 2^n 次冪？這是為了儘量將集合元素均攤到數組的不同位置上。
我們知道 HashMap 在確定元素對應的數組下標時，是採用了 hashCode 對數組長度取余的運算，它其實等價於 hashCode 對數組長度 - 1 的與運算（h % length 等價於 h & (lenght -1)，與運算效率更高，偶數才成立）；而 2^n 次冪對應的 length - 1 恰好全是 1（1000-1 = 111），這樣就把影響下標的因素歸結於 hashCode 本身，因而能夠實現儘可能均攤。3.4 HashMap 中 Key 的匹配判斷if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))3.5 為什麼經常使用 String 作為 HashMap 的 Key？這個問題我認為有 2 個原因：
1、不可變類 String 可以避免修改後無法定位鍵值對： 假設 String 是可變類，當我們在 HashMap 中構建起一個以 String 為 Key 的鍵值對時，此時對 String 進行修改，那麼通過修改後的 String 是無法匹配到剛才構建過的鍵值對的，因為修改後的 hashCode 可能是變化的。而不可變類可以規避這個問題。2、String 能夠滿足 Java 對於 hashCode() 和 equals() 的通用約定：如果兩個對象 equals() 相同，則 hashCode() 相同，如果 hashCode() 相同，則 equals() 不一定相同。這個約定是為了避免兩個 equals() 相同的 Key 在 HashMap 中存儲兩個獨立的鍵值對，引起矛盾。4. HashMap 線程安全性4.1 HashMap 線程不安全的原因數據覆蓋問題：如果兩個線程並發執行 put 操作，並且兩個數據的 hash 值衝突，就可能出現數據覆蓋（線程 A 判斷 hash 值位置為 null，還未寫入數據時掛起，此時線程 B 正常插入數據。接着線程 A 獲得時間片，由於線程 A 不會重新判斷該位置是否為空，就會把剛才線程 B 寫入的數據覆蓋掉）；環形鍊表問題： 在 HashMap 觸發擴容時，並且正好兩個線程同時在操作同一個鍊表時，就可能引起指針混亂，形成環型鏈條（因為 JDK 1.7 版本採用頭插法，在擴容時會翻轉鍊表的順序，而 JDK 1.8 採用尾插法，在擴容時會保持鍊表原本的順序）。4.2 HashMap 和 hashTable 的區別？1、hashTable 對每個方法都增加了 synchronized；2、hashTable 不允許 null 作為 Key；4.3 ConcurrentHashMap 分段鎖的原理HashMap 出現並發問題的核心在於多個線程同時操作同一個鍊表，而 ConcurrentHashMap 在操作鍊表前會用 synchronized 對鍊表的首個元素加鎖，從而避免並發問題。
參考資料都說 HashMap 是線程不安全的，到底體現在哪兒？ —— developer 著Java源碼分析：HashMap 1.8 相對於1.7 到底更新了什麼？[16] —— Carson 著《數據結構與算法之美》（第21、22章） —— 王爭 講，極客時間 出品
Android 增量更新完全解析 是增量不是熱修復
從原理到實戰，全面總結 Android HTTPS 抓包
點擊下方卡片關注JsonChao，為你構建一套
大廠青睞的 T 型人才系統
▲點擊上方卡片關注JsonChao，構建一套
大廠青睞的 T 型人才知識體系
歡迎把文章分享到朋友圈
留言列表