你好，面试官 | 你拿Java Map考验老干部？
小龍有話說
本期會模擬面試 Map 相關內容。
涉及知識點，Map 常使用實現類使用場景，特性；Hash算法；HashMap原理剖析；分段鎖；ConcurrentHashMap；
本期題改編自 ——2022屆春招 阿里供應鏈 一面
?
面試現場
叮叮叮......
面試官：“你好，我是XX面試官，請問是小龍嗎？”
小龍：“您好，面試官，我是小龍”
面試官：“好的，現在有空嗎，我們開始面試吧”
小龍：“嗯嗯，準備好啦”
.......
other questions
.......
面試官：“我看你簡歷上有提到你已經是 ‘老Map’ 了對吧。”
小龍：“是的”
面試官：“好的，那 Map 接口下，你常用的實現類有哪些？能簡單聊聊嗎？”
獨白：“又得扯HashMap ConCurrentHashMap 了....。”
小龍：“我經常使用HashMap、 LinkedHashMap、TreeMap這些。”
面試官：“那它們分別在什么場景下使用呢？”
小龍：“一般情況涉及到鍵值對的存取，我們都會第一時間考慮使用 HashMap。不過，在某些特定場景，比如：我們需要根據 key 順序去存儲鍵值對，TreeMap可能就更合適啦。“
小龍：”因為 TreeMap 底層是基于紅黑樹實現的，可以提供順序訪問，不過 TreeMap 鍵值都不能為 null，而且時間復雜度是 O(logn)。因此，在實際應用場景中，應當綜合考慮二者的特性去擇優處理。“
小龍：”而對于 LinkedHashMap，它的實現是通過為條目(鍵 值對)維護一個雙向鏈表。平時主要用來處理一些特定的應用場景。”
小龍：”比如：去構建一個對空間占用很看重的一個資源池，可以自動將不常用的資源釋放掉，例如去模擬 LRU 緩存淘汰策略，就可以使用 LinkedHashMap 去模擬。“
面試官：“好的，我們接著往下聊哈。那你有了解過 HashMap 的底層實現原理嗎？平時有沒有仔細研究過它的源碼呢？”
小龍：“這個有仔細研讀過，收獲頗多。”
面試官：“那首先你能給我講講你對 Hash 算法的理解嗎？”
小龍：“簡單來說，其實它就是一種將任意長度的輸入轉為為固定長度的輸出的映射規則。”
面試官：“那這個映射會不會有什么問題呢？”
小龍：“當然，由于任意長度—>固定長度，隨著 hash 次數增加，后面必定出現 哈希沖突。”
面試官：“那這個沖突能避免嗎？”
小龍：“hash沖突不可避免 只能說減少沖突。”
面試官：“那你有了解過哪些方法可以去解決這個 Hash 沖突呢？”
小龍：“嗯，比如：拉鏈法、開放地址、多哈希算法，當然在分布式某些場景中，我們還可以使用一致性Hash算法。”
面試官：“好的，那接下來你說說 HashMap 的底層數據結構吧！”
小龍：“JDK1.7 及以前是數組+鏈表，JDK1.8 是數組+鏈表+紅黑樹。”
面試官：“默認負載因子是多少呢，并且這個負載因子有什么作用？”
小龍：“負載因子默認0.75，它是在計算擴容閾值時用的。”
面試官：“創建 HashMap 時，不指定散列表數組長度，初始長度是多少呢？”
獨白：“wc，問這么簡單嗎？”
小龍：“默認初始長度16啊。”
面試官：“那散列表是new HashMap()時創建的么？”
獨白：“這個到是稍微有點意思~”
小龍：“不是在new HashMap()創建的，它使用懶加載，是當第一次調用 put() 方法時 執行putVal() 時才創建散列表。”
面試官：“那說說 HashMap put() 寫數據的具體流程吧，盡可能的詳細點！”
獨白：“好吧，本來想以普通人身份相處，換來的卻是疏遠，不裝了，攤牌了。是你叫我詳細一點的，我可以直接把源碼一條龍給你背下來.....。”
小龍：“ 1、首先map.put(“公眾號” , “小龍coding”)；”
小龍：“2、調用 key 對象的 hashcode() 方法計算 key-"公眾號" 的hash 。”
小龍：“3、然后經過擾動函數使其 hash 值更散列（調用 key 對象的 hashcode() 方法計算出來 hash 值，將 hash 值的高 16 位右移并與原 hash 值取異或運算（^），混合高 16 位和低 16 位的值，得到一個更加散列的低 16 位的 hash 值）”
小龍：“4、接下來進入putVal() 方法，判斷散列表是否為空 也就是 put() 方法第一次調用才初始化 HashMap 的存儲結構 Node<k,v>[] table 散列表 初始為數組長度16”
小龍：“5、調用 (n - 1) & hash 【細節解釋：（散列表數組長度-1） 與 （hash值得到將要把元素插到哪里的數組下標）】”
小龍：“6、判斷數組該位置是否為空”
小龍：“如果為空 新創建一個結點直接插入 tab[i] = newNode(hash, key, value, null)；如果插入位置已經有值了tab[i]!=null，并且桶位中的該元素，與你當前插入的元素的 key 完全一致，表示后續需要進行替換操作，否則就需要往該結點后添加元素。”
獨白：“估計面試官與正在看的你已經蒙了，這是為了全面細致的拉通分析一遍，面試可以簡單的說。”
小龍：“插入前需要判斷是否為樹結構，若為樹結構按照樹結構的插入結點方法插入，不是樹結構則按照鏈式結構插入結點方法插入。”
小龍：“若為鏈表結構，遍歷改鏈表，判斷是否有與你要插入的 key 一致的 node。”
小龍：“如果沒有則將結點插入到該鏈表末尾（1.8尾插法 1.7頭插法），并判斷插入后是否達到樹化條件（鏈表長度>=8 進入treeifyBin(tab, hash)；進入該方法還需要判斷當前數組長度>=64才能樹化,如果<64則擴容）”
小龍：“到相同元素則需要替換。”
小龍：“7、完成插入操作了 ++modCount(散列表結構結構被修改的次數–替換 Node 元素的 value 不算)”
小龍：“8、最好 size 自增，如果自增后的值大于擴容閾值，則觸發擴容 resize()；”
獨白：“沒有源碼，這里可能基礎差的看起來很吃力，需要看全代碼跟蹤解析，有每一步調試+注釋，一步一步跟著方法進，注釋寫的很清楚，需要可以公眾號【小龍coding】后臺回復【HashMap】”
面試官：“叫你說詳細一點，用不著這么詳細，哈哈。”
面試官：“我們加快腳步了，Node對象內部的 hash 字段，這個 hash 值是 key 對象的 hashcode() 返回值么？”
小龍：“Node 對象里面的 hash 值并不是直接 key.hashcode() 得到， 還要經過 擾動函數。“
面試官：”這個 hash 值是怎么得到呢？“
小龍：”將 hash 值的高 16 位右移并與原 Hash 值取異或運算（^），混合高 16 位和低 16 位的值，得到一個更加散列的低 16 位的 Hash 值。“
面試官：”JDK8 HashMap 為什么引入紅黑樹？解決什么問題？“
小龍：”引入紅黑樹我認為是這樣 當產生 hash 沖突時會形成鏈表 當數據多了沖突多了 鏈表越來越長 造成鏈化 此時查詢將特別耗時 本來時間復雜度為O(1) 結構可能達到 O(n)，引入紅黑樹可以優化查詢。“
面試官：”HashMap 什么情況下會觸發擴容呢？“
小龍：”當它未初始化，第一次 put 時會觸發擴容。后面插入值，當大于擴容閾值時也會觸發擴容。“
面試官：“HashMap 如何確定元素放在哪個位置呢？”
小龍：“首先經過擾動函數計算得到hash值；然后通過 (n - 1) & hash 判斷當前元素存放的位置。”
面試官：”HashMap 有什么問題嗎？在實際應用場景中。“
小龍：”因為 HashMap 非線程安全，可能出現并發線程安全問題。在JDK1.7中，當并發執行擴容操作會造成環形鏈，然后調用 get 方法會死循環。JDK1.8中，并發執行put操作時會發生數據覆蓋的操作。“
面試官：”那有什么解決辦法嗎？“
小龍：”可以使用 Hashtable，因為它的方法加了synchronized，可以做到線程安全。“
小龍：”不過，由于它鎖的是整個表，導致效率低下。因此，我們一般使用的是 ConcurrentHashMap“
面試官：“好的，那你能簡單介紹一下 ConcurrentHashMap 嗎？為何它的性能效率更高呢？”
小龍：”ConcurrentHashMap JDK1.7 引入了分段鎖，數據結構采用Segment數組+HashEntry數組+鏈表。Segment 繼承了 ReentrantLock，一個 Segment[i] 就是一把分段鎖。比起 Hashtable 鎖粒度更細，性能更高。”
一個Segment中包含一個HashEntry數組，每個HashEntry又是一個鏈表結構static?final?class?Segment<K,V>?extens?ReentrantLock?implements?Serializable{transient?volatile?HashEntry<K,V>[]?tables; //..... } static?final?class?HashEntry<K,V> {final?int?hash;final?K?key;volatile?V?value;volatile?HashEntry<K,V>?next; }面試官：“何為分段鎖？”
img小龍：“一個 Segment 就相當于一把鎖，它只鎖住這個槽位，其他的并不受影響。ConcurrentHashMap 將 hash 表分為 16 個桶（默認值），諸如get，put，remove 等常用操作只鎖當前需要用到的桶。”
小龍：“試想，原來 只能一個線程進入，現在卻能同時16個寫線程進入（寫線程才需要鎖定，而讀線程幾乎不受限制，之后會提到），并發性的提升是顯而易見的。”
面試官：“不過我們現在都基本用 JDK1.8 啦，JDK1.8 它也是使用分段鎖嗎？”
小龍：“JDK1.8 后，它做出了很大改變，數據結構采用Node數組+鏈表+紅黑樹，拋棄Segment分段鎖，采用CAS+synchronized，鎖粒度更細，只鎖住鏈表頭節點（紅黑樹根結點），不影響其他哈希桶數組元素的讀寫，提高并發度。”
面試官：“好的，挺不錯的。最后一個問題，你知道 ?ConcurrentHashMap 為什么不支持 null value嗎？”
小龍：“這個很簡單啊，vaule 為 null，有兩種情況，可能是存的值為 null 或則是沒有映射到值 返回null；”
小龍：”HashMap 用于單線程下可以通過 ContainsKey() 區分這兩種情況；“
小龍：“但是 ConcurrentHashMap用于多線程場景，本來是沒有映射 ContainsKey() 返回fasle，但是可能在你調用 ContainsKey() 檢查時新線程插入null值，返回ture，存在二義性”
面試官：“牛逼，基礎很好！繼續加油。”
獨白：“不愧是我，真男人是也！”
?
知識總結
本期我們通過面試模擬簡單介紹了Map相關面試中重點考察的內容，重點剖析了 HashMap 與 ConcurrentHashMap 相關集合。
面試重點
Map 常使用實現類使用場景，特性；Hash算法理解；HashMap原理剖析；分段鎖理解；ConcurrentHashMap原理，底層數據機構，JDK1.8 與JDK1.7 區別。
有道無術，術可成；有術無道，止于術
歡迎大家關注Java之道公眾號
好文章，我在看??
新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！總結
以上是生活随笔為你收集整理的你好，面试官 | 你拿Java Map考验老干部？的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 名校生都去哪些互联网公司？
- 下一篇： Mysql 数据库表中有索引为什么还是查