阿裏面試官最喜歡問的21個HashMap面試題

1.HashMap 的數據結構?

A:哈希表結構(鏈表散列:數組+鏈表)實現,結合數組和鏈表的優點。當鏈表長度超過 8 時,鏈錶轉換為紅黑樹。

transient Node<K,V>\[\] table;

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 會存儲到鏈表中。

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)

更多精彩面試題

如果有想看的小夥伴就給我留言吧。這就是本文的全部內容了。如果覺得寫的不錯,請記得收藏加轉發。還想跟我看更多數據結構和算法題的小夥伴們,記得關注我公眾號:程序零世界,Java 就這麼回事。

線程,多線程,線程池,線程上下文,鎖一鍵啟動線程

紅黑樹其實並不難,只是你還沒看過ta

JVM其實並沒有那麼難,你也該啃下TA了

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※為什麼 USB CONNECTOR 是電子產業重要的元件?

網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※台北網頁設計公司全省服務真心推薦

※想知道最厲害的網頁設計公司"嚨底家"!

新北清潔公司,居家、辦公、裝潢細清專業服務

※推薦評價好的iphone維修中心

您可能也會喜歡…