簡答一波 HashMap 常見八股面試題 —— 演算法系列(2)

請點贊,你的點贊對我意義重大,滿足下我的虛榮心。

🔥 Hi,我是小彭。本文已收錄到 GitHub · Android-NoteBook 中。這裡有 Android 進階成長知識體系,有志同道合的朋友,關注公眾號 [彭旭銳] 跟我一起成長。

前言

HashMap 是我們熟悉的散列表實現,也是 「面試八股文」 的標準題庫之一。今天,我給出一份 HashMap 高頻面試題口述簡答答案,希望對你刷題有幫助。如果能幫上忙請務必點贊加關注,這對我非常重要。


這篇文章是數據結構與演算法系列文章第 2 篇,專欄文章列表:

一、數據結構基礎:

二、演算法思想:

三、高級數據結構:

四、刷題題解:


1. 認識散列表

1.1 散列表的作用

散列演算法是散列表的核心,也就做哈希演算法或 Hash 演算法,是一個意思。散列演算法是一種將任意長度輸入轉換為固定長度輸出的演算法,輸出的結果就是散列值。基於散列演算法實現的散列表,可以實現快速查找元素的特性。

總結一下散列演算法的主要性質:

性質 描述
1、單向性(基本性質) 支援從輸入生成散列值,不支援從散列值反推輸入
2、高效性(基本性質) 單次散列運算計算量低
3、一致性 相同輸入重複計算,總是得到相同散列值
4、隨機性 散列值在輸出值域的分布盡量隨機
5、輸入敏感性 相似的數據,計算後的散列值差別很大

1.2 什麼是散列衝突?

散列演算法一定是一種壓縮映射,因為輸入值域非常大甚至無窮大,而散列值域為一個固定長度的值域。例如,MD5 的輸出散列值為 128 位,SHA256 的輸出散列值為 256 位,這就存在 2 個不同的輸入產生相同輸出的可能性,即散列衝突,或哈希衝突、Hash Collision。

這其實只要用鴿巢原理(又稱:抽屜原理)就很好理解了,假設有 10 個鴿巢,現有 11 只鴿子,無論分配多麼平均,也肯定有一個鴿巢里有兩隻甚至多只鴿子。舉一個直接的例子,Java中的字元串 "Aa""BB" 的散列值就衝突了:

示常式序

String str1 = "Aa";
String str2 = "BB";
System.out.println(str1.hashCode());  2112
System.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 對鏈表的首個元素加鎖,從而避免並發問題。


參考資料

Tags: