HashMap 的 31 連環炮

寫在前面

在面試中，HashMap 基本必問，只是問法各有不同而已。曾經我也和很多面試官聊過關於 HashMap 的話題，使用 HashMap 就能考察面試者的很多知識點。不幸的是，很大部分人都拜倒在 HashMap 的石榴裙底下。

HashMap 爲什麼如此受面試官青睞？

我覺得其中有 4 個原因：

• HashMap 在我們工作中使用頻率相當高。

• Java 基礎（可以通過此 Java 集合）

• 線程安全問題（可以通過這個問題引入多線程併發編程的相關問題）

• 大廠都在問，豈能不問？（不問的話，顯得面試官沒有水平）

下面就是我給大家準備的 HashMap 連環炮，這個連環炮就相當於高考真題演練一樣，可能沒有完全一樣的，只是問法不同罷了，這個主要得益於咱們漢語博大精深。

下面是 HashMap 的 31 連環炮：

1：說說 HashMap 底層數據結構是怎樣的？

2：談一下 HashMap 的特性？

3：使用 HashMap 時，當兩個對象的 hashCode 相同怎麼辦？

4：HashMap 的哈希函數怎麼設計的嗎？

5：HashMap 遍歷方法有幾種？

6：爲什麼採用 hashcode 的高 16 位和低 16 位異或能降低 hash 碰撞？hash 函數能不能直接用 key 的 hashcode？

7：解決 hash 衝突的有幾種方法？

8：爲什麼要用異或運算符？

9.：HashMap 的 table 的容量如何確定？

10：請解釋一下 HashMap 的參數 loadFactor，它的作用是什麼

11：說說 HashMap 中 put 方法的過程

12：當鏈表長度 >= 8 時，爲什麼要將鏈表轉換成紅黑樹？

13：new HashMap(18); 此時 HashMap 初始容量爲多少？

14：說說 resize 擴容的過程

15：說說 hashMap 中 get 是如何實現的？

16：拉鍊法導致的鏈表過深問題爲什麼不用二叉查找樹代替，而選擇紅黑樹？爲什麼不一直使用紅黑樹？

17：說說你對紅黑樹的瞭解

18：JDK8 中對 HashMap 做了哪些改變？

19：HashMap 中的 key 我們可以使用任何類作爲 key 嗎？

20：HashMap 的長度爲什麼是 2 的 N 次方呢？

21：HashMap，LinkedHashMap，TreeMap 有什麼區別？

22：說說什麼是 fail-fast？

23：HashMap 和 HashTable 有什麼區別？

24：HashMap 是線程安全的嗎？

25：如何規避 HashMap 的線程不安全？

26：HashMap 和 ConcurrentHashMap 的區別？

27：爲什麼 ConcurrentHashMap 比 HashTable 效率要高？

28：說說 ConcurrentHashMap 中 鎖機制

29：在 JDK 1.8 中，ConcurrentHashMap 爲什麼要使用內置鎖 synchronized 來代替重入鎖 ReentrantLock？

30：能對 ConcurrentHashMap 做個簡單介紹嗎？

31：熟悉 ConcurrentHashMap 的併發度嗎？

....

java 集合知識總結

下面我們正式開始連環炮

1、說說 HashMap 底層數據結構是怎樣的？

HashMap 底層是 hash 數組和單向鏈表實現，jdk8 後採用數組 + 鏈表 + 紅黑樹的數據結構。

2、說說 HashMap 的工作原理

如果第一題沒問，直接問原理，那就必須把 HashMap 的數據結構說清楚。

HashMap 底層是 hash 數組和單向鏈表實現，JDK8 後採用數組 + 鏈表 + 紅黑樹的數據結構。

我們通過 put 和 get 存儲和獲取對象。當我們給 put() 方法傳遞鍵和值時，先對鍵做一個 hashCode() 的計算來得到它在 bucket 數組中的位置來存儲 Entry 對象。當獲取對象時，通過 get 獲取到 bucket 的位置，再通過鍵對象的 equals() 方法找到正確的鍵值對，然後在返回值對象。

3、使用 HashMap 時，當兩個對象的 hashCode 相同怎麼辦？

因爲 HashCode 相同，不一定就是相等的（equals 方法比較），所以兩個對象所在數組的下標相同，"碰撞" 就此發生。又因爲 HashMap 使用鏈表存儲對象，這個 Node 會存儲到鏈表中。

4、HashMap 的哈希函數怎麼設計的嗎？

hash 函數是先拿到通過 key 的 hashCode ，是 32 位的 int 值，然後讓 hashCode 的高 16 位和低 16 位進行異或操作。兩個好處：

1. 一定要儘可能降低 hash 碰撞，越分散越好；

2. 算法一定要儘可能高效，因爲這是高頻操作, 因此採用位運算；

5、HashMap 遍歷方法有幾種？

• Iterator 迭代器

• 最常見的使用方式，可同時得到 key、value 值

• 使用 foreach 方式（JDK1.8 纔有）

• 通過 key 的 set 集合遍歷

6、爲什麼採用 hashcode 的高 16 位和低 16 位異或能降低 hash 碰撞？

因爲 key.hashCode() 函數調用的是 key 鍵值類型自帶的哈希函數，返回 int 型散列值。int 值範圍爲 -2147483648~2147483647，前後加起來大概 40 億的映射空間。只要哈希函數映射得比較均勻鬆散，一般應用是很難出現碰撞的。但問題是一個 40 億長度的數組，內存是放不下的。

設想，如果 HashMap 數組的初始大小才 16，用之前需要對數組的長度取模運算，得到的餘數才能用來訪問數組下標。

7、解決 hash 衝突的有幾種方法？

1、再哈希法：如果 hash 出的 index 已經有值，就再 hash，不行繼續 hash，直至找到空的 index 位置，要相信瞎貓總能碰上死耗子。這個辦法最容易想到。但有 2 個缺點：

• 比較浪費空間，消耗效率。根本原因還是數組的長度是固定不變的，不斷 hash 找出空的 index，可能越界，這時就要創建新數組，而老數組的數據也需要遷移。隨着數組越來越大，消耗不可小覷。

• get 不到，或者說 get 算法複雜。進是進去了，想出來就沒那麼容易了。

2、開放地址方法：如果 hash 出的 index 已經有值，通過算法在它前面或後面的若干位置尋找空位，這個和再 hash 算法差別不大。

3、建立公共溢出區： 把衝突的 hash 值放到另外一塊溢出區。

4、鏈式地址法： 把產生 hash 衝突的 hash 值以鏈表形式存儲在 index 位置上。HashMap 用的就是該方法。優點是不需要另外開闢新空間，也不會丟失數據，尋址也比較簡單。但是隨着 hash 鏈越來越長，尋址也是更加耗時。好的 hash 算法就是要讓鏈儘量短，最好一個 index 上只有一個值。也就是儘可能地保證散列地址分佈均勻，同時要計算簡單。

8、爲什麼要用異或運算符？

保證了對象的 hashCode 的 32 位值只要有一位發生改變，整個 hash() 返回值就會改變。儘可能的減少碰撞。

9、HashMap 的 table 的容量如何確定？

①、table 數組大小是由 capacity 這個參數確定的，默認是 16，也可以構造時傳入，最大限制是 1<<30；

②、loadFactor 是裝載因子，主要目的是用來確認 table 數組是否需要動態擴展，默認值是 0.75，比如 table 數組大小爲 16，裝載因子爲 0.75 時，threshold 就是 12，當 table 的實際大小超過 12 時，table 就需要動態擴容；

③、擴容時，調用 resize() 方法，將 table 長度變爲原來的兩倍（注意是 table 長度，而不是 threshold）；

④、如果數據很大的情況下，擴展時將會帶來性能的損失，在性能要求很高的地方，這種損失很可能很致命。

10、請解釋一下 HashMap 的參數 loadFactor，它的作用是什麼

loadFactor 表示 HashMap 的擁擠程度，影響 hash 操作到同一個數組位置的概率。

默認 loadFactor 等於 0.75，當 HashMap 裏面容納的元素已經達到 HashMap 數組長度的 75% 時，表示 HashMap 太擠了，需要擴容，在 HashMap 的構造器中可以定製 loadFactor。

11、說說 HashMap 中 put 方法的過程

由於 JDK 版本中 HashMap 設計上存在差異，這裏說說 JDK7 和 JDK8 中的區別：

具體 put 流程，請參照下圖進行回答：

12、當鏈表長度 >= 8 時，爲什麼要將鏈表轉換成紅黑樹？

因爲紅黑樹的平均查找長度是 log(n)，長度爲 8 的時候，平均查找長度爲 3，如果繼續使用鏈表，平均查找長度爲 8/2=4，所以，當鏈表長度 >= 8 時 ，有必要將鏈表轉換成紅黑樹。

13、new HashMap(18); 此時 HashMap 初始容量爲多少？

容量爲 32。

在 HashMap 中有個靜態方法 tableSizeFor ，tableSizeFor 方法保證函數返回值是大於等於給定參數 initialCapacity 最小的 2 的冪次方的數值 。

static final int tableSizeFor(int cap) {
  int n = cap - 1;
  n |= n >>> 1;
  n |= n >>> 2;
  n |= n >>> 4;
  n |= n >>> 8;
  n |= n >>> 16;
  return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
  }

14、說說 resize 擴容的過程

創建一個新的數組，其容量爲舊數組的兩倍，並重新計算舊數組中結點的存儲位置。結點在新數組中的位置只有兩種，原下標位置或原下標 + 舊數組的大小。

15、說說 hashMap 中 get 是如何實現的？

對 key 的 hashCode 進行 hash 值計算，與運算計算下標獲取 bucket 位置，如果在桶的首位上就可以找到就直接返回，否則在樹中找或者鏈表中遍歷找，如果有 hash 衝突，則利用 equals 方法去遍歷鏈表查找節點。

16、拉鍊法導致的鏈表過深問題爲什麼不用二叉查找樹代替，而選擇紅黑樹？爲什麼不一直使用紅黑樹？

之所以選擇紅黑樹是爲了解決二叉查找樹的缺陷，二叉查找樹在特殊情況下會變成一條線性結構（這就跟原來使用鏈表結構一樣了，造成很深的問題），遍歷查找會非常慢。而紅黑樹在插入新數據後可能需要通過左旋，右旋、變色這些操作來保持平衡，引入紅黑樹就是爲了查找數據快，解決鏈表查詢深度的問題，我們知道紅黑樹屬於平衡二叉樹，但是爲了保持 “平衡” 是需要付出代價的，但是該代價所損耗的資源要比遍歷線性鏈表要少，所以當長度大於 8 的時候，會使用紅黑樹，如果鏈表長度很短的話，根本不需要引入紅黑樹，引入反而會慢。

17、說說你對紅黑樹的瞭解

紅黑樹是一種自平衡的二叉查找樹，是一種高效的查找樹。

紅黑樹通過如下的性質定義實現自平衡：

• 節點是紅色或黑色。

• 根是黑色。

• 所有葉子都是黑色（葉子是 NIL 節點）。

• 每個紅色節點必須有兩個黑色的子節點。（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。）

• 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點（簡稱黑高）。

18、JDK8 中對 HashMap 做了哪些改變？

1. 在 java 1.8 中，如果鏈表的長度超過了 8，那麼鏈表將轉換爲紅黑樹。（桶的數量必須大於 64，小於 64 的時候只會擴容）

2. 發生 hash 碰撞時，java 1.7 會在鏈表的頭部插入，而 java 1.8 會在鏈表的尾部插入

3. 在 java 1.8 中，Entry 被 Node 替代 (換了一個馬甲)。

19、HashMap 中的 key 我們可以使用任何類作爲 key 嗎？

平時可能大家使用的最多的就是使用 String 作爲 HashMap 的 key，但是現在我們想使用某個自定 義類作爲 HashMap 的 key，那就需要注意以下幾點：

• 如果類重寫了 equals 方法，它也應該重寫 hashCode 方法。

• 類的所有實例需要遵循與 equals 和 hashCode 相關的規則。

• 如果一個類沒有使用 equals，你不應該在 hashCode 中使用它。

• 咱們自定義 key 類的最佳實踐是使之爲不可變的，這樣，hashCode 值可以被緩存起來，擁有

  更好的性能。不可變的類也可以確保 hashCode 和 equals 在未來不會改變，這樣就會解決與可變相關的問題了。

20、HashMap 的長度爲什麼是 2 的 N 次方呢？

爲了能讓 HashMap 存數據和取數據的效率高，儘可能地減少 hash 值的碰撞，也就是說盡量把數 據能均勻的分配，每個鏈表或者紅黑樹長度儘量相等。我們首先可能會想到 % 取模的操作來實現。下面是回答的重點喲：

取餘（%）操作中如果除數是 2 的冪次，則等價於與其除數減一的與（&）操作（也就是說 hash % length == hash &(length - 1) 的前提是 length 是 2 的 n 次方）。並且，採用二進 制位操作 & ，相對於 % 能夠提高運算效率。

這就是爲什麼 HashMap 的長度需要 2 的 N 次方了。

21、HashMap，LinkedHashMap，TreeMap 有什麼區別？

• LinkedHashMap 是繼承於 HashMap，是基於 HashMap 和雙向鏈表來實現的。

• HashMap 無序；LinkedHashMap 有序，可分爲插入順序和訪問順序兩種。如果是訪問順序，那 put 和 get 操作已存在的 Entry 時，都會把 Entry 移動到雙向鏈表的表尾 (其實是先刪除再插入)。

• LinkedHashMap 存取數據，還是跟 HashMap 一樣使用的 Entry[] 的方式，雙向鏈表只是爲了保證順序。

• LinkedHashMap 是線程不安全的。

22、說說什麼是 fail-fast？

fail-fast 機制是 Java 集合（Collection）中的一種錯誤機制。當多個線程對同一個集合的內容進行 操作時，就可能會產生 fail-fast 事件。

例如：當某一個線程 A 通過 iterator 去遍歷某集合的過程中，若該集合的內容被其他線程所改變 了，那麼線程 A 訪問集合時，就會拋出 ConcurrentModificationException 異常，產生 fail-fast 事 件。這裏的操作主要是指 add、remove 和 clear，對集合元素個數進行修改。

解決辦法

建議使用 “java.util.concurrent 包下的類” 去取代“java.util 包下的類”。可以這麼理解：在遍歷之前，把 modCount 記下來 expectModCount，後面 expectModCount 去 和 modCount 進行比較，如果不相等了，證明已併發了，被修改了，於是拋出 ConcurrentModificationException 異常。

23、HashMap 和 HashTable 有什麼區別？

①、HashMap 是線程不安全的，HashTable 是線程安全的；

②、由於線程安全，所以 HashTable 的效率比不上 HashMap；

③、HashMap 最多隻允許一條記錄的鍵爲 null，允許多條記錄的值爲 null，而 HashTable 不允許；

④、HashMap 默認初始化數組的大小爲 16，HashTable 爲 11，前者擴容時，擴大兩倍，後者擴大兩倍 + 1；

⑤、HashMap 需要重新計算 hash 值，而 HashTable 直接使用對象的 hashCode；

24、HashMap 是線程安全的嗎？

不是，在多線程環境下，1.7 會產生死循環、數據丟失、數據覆蓋的問題，1.8 中會有數據覆蓋的問題，以 1.8 爲例，當 A 線程判斷 index 位置爲空後正好掛起，B 線程開始往 index 位置的寫入節點數據，這時 A 線程恢復現場，執行賦值操作，就把 A 線程的數據給覆蓋了；還有 ++size 這個地方也會造成多線程同時擴容等問題。

25、如何規避 HashMap 的線程不安全？

單線程條件下，爲避免出現 ConcurrentModificationException，需要保證只通過 HashMap 本身或者只通過 Iterator 去修改數據，不能在 Iterator 使用結束之前使用 HashMap 本身的方法修改數據。因爲通過 Iterator 刪除數據時，HashMap 的 modCount 和 Iterator 的 expectedModCount 都會自增，不影響二者的相等性。如果是增加數據，只能通過 HashMap 本身的方法完成，此時如果要繼續遍歷數據，需要重新調用 iterator() 方法從而重新構造出一個新的 Iterator，使得新 Iterator 的 expectedModCount 與更新後的 HashMap 的 modCount 相等。

多線程條件下，可使用兩種方式：

• Collections.synchronizedMap 方法構造出一個同步 Map

• 直接使用線程安全的 ConcurrentHashMap。

26、HashMap 和 ConcurrentHashMap 的區別？

1. 都是 key-value 形式的存儲數據；

2. HashMap 是線程不安全的，ConcurrentHashMap 是 JUC 下的線程安全的；

3. HashMap 底層數據結構是數組 + 鏈表（JDK 1.8 之前）。JDK 1.8 之後是數組 + 鏈表 + 紅黑 樹。當鏈表中元素個數達到 8 的時候，鏈表的查詢速度不如紅黑樹快，鏈表會轉爲紅黑樹，紅 黑樹查詢速度快；

4. HashMap 初始數組大小爲 16（默認），當出現擴容的時候，以 0.75 * 數組大小的方式進行擴 容；

5. ConcurrentHashMap 在 JDK 1.8 之前是採用分段鎖來現實的 Segment + HashEntry， Segment 數組大小默認是 16，2 的 n 次方；JDK 1.8 之後，採用 Node + CAS + Synchronized 來保證併發安全進行實現。

27、爲什麼 ConcurrentHashMap 比 HashTable 效率要高？

HashTable：使用一把鎖（鎖住整個鏈表結構）處理併發問題，多個線程競爭一把鎖，容易阻塞；

ConcurrentHashMap：

• JDK 1.7 中使用分段鎖（ReentrantLock + Segment + HashEntry），相當於把一個 HashMap 分成多個段，每段分配一把鎖，這樣支持多線程訪問。鎖粒度：基於 Segment，包含多個 HashEntry。

• JDK 1.8 中使用CAS + synchronized + Node + 紅黑樹。鎖粒度：Node（首結點）（實現 Map.Entry<K,V>）。鎖粒度降低了。

28、說說 ConcurrentHashMap 中 鎖機制

JDK 1.7 中，採用分段鎖的機制，實現併發的更新操作，底層採用數組 + 鏈表的存儲結構，包括兩個核心靜態內部類 Segment 和 HashEntry。

①、Segment 繼承 ReentrantLock（重入鎖） 用來充當鎖的角色，每個 Segment 對象守護每個散列映射表的若干個桶；

②、HashEntry 用來封裝映射表的鍵 - 值對；

③、每個桶是由若干個 HashEntry 對象鏈接起來的鏈表

JDK 1.8 中，採用 Node + CAS + Synchronized 來保證併發安全。取消類 Segment，直接用 table 數組存儲鍵值對；當 HashEntry 對象組成的鏈表長度超過 TREEIFY_THRESHOLD 時，鏈表轉換爲紅黑樹，提升性能。底層變更爲數組 + 鏈表 + 紅黑樹。

29、在 JDK 1.8 中，ConcurrentHashMap 爲什麼要使用內置鎖 synchronized 來代替重入鎖 ReentrantLock？

①、粒度降低了；

②、JVM 開發團隊沒有放棄 synchronized，而且基於 JVM 的 synchronized 優化空間更大，更加自然。

③、在大量的數據操作下，對於 JVM 的內存壓力，基於 API 的 ReentrantLock 會開銷更多的內存。

30、能對 ConcurrentHashMap 做個簡單介紹嗎？

①、重要的常量：　　

private transient volatile int sizeCtl; 　　

當爲負數時，-1 表示正在初始化，-N 表示 N - 1 個線程正在進行擴容；　　

當爲 0 時，表示 table 還沒有初始化；　　

當爲其他正數時，表示初始化或者下一次進行擴容的大小。

②、數據結構：　　

Node 是存儲結構的基本單元，繼承 HashMap 中的 Entry，用於存儲數據； 

TreeNode 繼承 Node，但是數據結構換成了二叉樹結構，是紅黑樹的存儲結構，用於紅黑樹中存儲數據；　　

TreeBin 是封裝 TreeNode 的容器，提供轉換紅黑樹的一些條件和鎖的控制。

③、存儲對象時（put() 方法）：　　

1. 如果沒有初始化，就調用 initTable() 方法來進行初始化；　　

2. 如果沒有 hash 衝突就直接 CAS 無鎖插入；　　

3. 如果需要擴容，就先進行擴容；　　

4. 如果存在 hash 衝突，就加鎖來保證線程安全，兩種情況：一種是鏈表形式就直接遍歷到尾端插入，一種是紅黑樹就按照紅黑樹結構插入；　　

5. 如果該鏈表的數量大於閥值 8，就要先轉換成紅黑樹的結構，break 再一次進入循環 　　

6. 如果添加成功就調用 addCount() 方法統計 size，並且檢查是否需要擴容。

④、擴容方法 transfer()：默認容量爲 16，擴容時，容量變爲原來的兩倍。　　helpTransfer()：調用多個工作線程一起幫助進行擴容，這樣的效率就會更高。

⑤、獲取對象時（get() 方法）：　　

1. 計算 hash 值，定位到該 table 索引位置，如果是首結點符合就返回；　　

2. 如果遇到擴容時，會調用標記正在擴容結點 ForwardingNode.find() 方法，查找該結點，匹配就返回；　　

3. 以上都不符合的話，就往下遍歷結點，匹配就返回，否則最後就返回 null。

31、熟悉 ConcurrentHashMap 的併發度嗎？

程序運行時能夠同時更新 ConccurentHashMap 且不產生鎖競爭的最大線程數。默認爲 16，且可以在構造函數中設置。當用戶設置併發度時，ConcurrentHashMap 會使用大於等於該值的最小 2 冪指數作爲實際併發度（假如用戶設置併發度爲 17，實際併發度則爲 32）。

參考：http://ii081.cn/gFInl

總結

好了，就寫這麼多了，文章中很多已經不是 HashMap 知識點了，但，面試很有可能會問這些知識點，多準備點也算是有備無患。

所謂天才，只不過是把別人喝咖啡的功夫都用在工作上了。

——魯迅

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/7I-5RL0Py-g8mP7lJol3Yg