Java 容器面試題】談談你對HashMap 的了解

為了能夠在面試回答中優雅而不失體面回答面試考點，該文章借鑒了不同平台對知識點的描述。

如有侵權請聯系我

文章的不足和錯誤請指正，好的建議也不要吝啬，我都會采納并更正

您的點贊是我持續更新的動力

我的回答

HashMap 是一種存取高效但不保證有序的常用容器。它的資料結構為“數組+連結清單”，是解決哈希沖突的産物，也就是我們常說的鍊位址法。它實作了Map 接口采用K-V 鍵值對存儲資料，并實作了淺拷貝和序列化。

HashMap 的預設初始大小為16，初始化大小必須為2的幂，最大大小為2的30次方。數組中存儲的連結清單節點Entry 類實作于Map.Entry 接口，它實作了對節點的通用操作。HashMap 的門檻值預設為“容量*0.75f”，當存儲節點數量超過該值，則對map 進行擴容處理。

HashMap 提供了4種構造方法，分别是預設構造方法；可以指定初始容量的構造方法；可以指定初始容量和門檻值的構造方法以及基于一個Map 的構造方法。雖然是構造函數，但是真正的初始化都是在第一次添加操作裡面實作的。

在第一次添加操作中，HashMap 會先判斷存儲數組有沒有初始化，如果沒有先進行初始化操作，初始化過程中會取比使用者指定的容量大的最近的2 的幂次方數作為數組的初始容量，并更新擴容的門檻值。

接着添加操作講吧。添加操作的執行流程為:

先判斷有沒有初始化

再判斷傳入的key 是否為空，為空儲存在table[o] 位置

key 不為空就對key 進hash，hash 的結果再& 數組的長度就得到存儲的位置

如果存儲位置為空則建立節點，不為空就說明存在沖突

解決沖突HashMap 會先周遊連結清單，如果有相同的value 就更新舊值，否則建構節點添加到連結清單頭

添加還要先判斷存儲的節點數量是否達到門檻值，到達門檻值要進行擴容

擴容擴2倍，是建立數組是以要先轉移節點，轉移時都重新計算存儲位置，可能保持不變可能為舊容量+位置。

擴容結束後新插入的元素也得再hash 一遍才能插入。

擷取節點的操作和添加差不多，也是

先判斷是否為空，為空就在table[0] 去找值

不為空也是先hash,&數組長度計算下标位置

再周遊找相同的key 傳回值

HashMap 的其他操作大同小異，再講講HashMap1.7 的問題還有1.7 和1.8 的差别。

HashMap 是一個并發不安全的容器，在疊代操作是采用的是fast-fail 機制；在并發添加操作中會出現丢失更新的問題；因為采用頭插法在并發擴容時會産生環形連結清單的問題，導緻CPU 到達100%，甚至當機。

解決并發問題可以采用

Java 類庫提供的Collections 工具包下的Collections.synchronizedMap()方法，傳回一個線程安全的Map

或者使用并發包下的 ConcurrentHashMap，ConcurrentHashMap采用分段鎖機制實作線程安全

使用HashTable （不推薦）

Hash1.7 和1.8 最大的不同在于1.8 采用了“數組+連結清單+紅黑樹”的資料結構，在連結清單長度超過8 時，把連結清單轉化成紅黑樹來解決HashMap 因連結清單變長而查詢變慢的問題；其次

在hash 取下标時将1.7 的9次擾動（5次按位與和4次位運算）改為2次（一次按位與和一次位運算）

1.7 的底層節點為Entry，1.8 為node ，但是本質一樣，都是Map.Entry 的實作

還有就是在存取資料時添加了關于樹結構的周遊更新與添加操作，并采用了尾插法來避免環形連結清單的産生

但是并發丢失更新的問題依然存在。

回答順序：資料結構+繼承結構+基本字段+構造方法+添加操作+擴容操作+擷取操作+并發問題+與1.8的差別

考點分析

HashMap 作為最基本的容器，它本身的設計與1.7 1.8的差異性導緻HashMap 成為面試中最最高頻的考點。是以掌握HashMap 勢在必行，但是想要在各種寬泛的回答中脫穎而出，就必須對hashMap 前因後果了然于胸。

考點一：為什麼初始容量必須為2 的幂？為什麼負載因子為0.75f？為什麼要做那麼多擾動處理？

這些問題都要圍繞一個點來回答：減少哈希沖突。

（1）容量必須為2 的幂是為了增加取值的可能性。

2 的n次幂轉化為二進制為1後面n個0，在計算下标的時候是hash&(length - 1)，也就是&(n-1)個1:初始容量為4->100，length-1 -> 11。所有的二進制為都為1有什麼好處？

0/1 & 1 都為它本身

0/1 & 0 都為 0

可以看出&1保證了取值的平均。如果某一位為0 ，比如最後一位，那麼它&出來下标就一定是個偶數，減少了HashMap 數組一半的取值，大大增加了沖突的可能。

（2）負載因子為0.75f 是空間與時間的均衡

如果負載因子小，意味着門檻值變小。比如容量為10 的HashMap，負載因子為0.5f，那麼存儲5個就會擴容到20，出現哈希沖突的可能性變小，但是空間使用率不高。适用于有足夠記憶體并要求查詢效率的場景。

相反如果門檻值為1 ，那麼容量為10，就必須存儲10個元素才進行擴容，出現沖突的機率變大，極端情況下可能會從O(1)退化到O(n)。适用于記憶體敏感但不要求要求查詢效率的場景

（3）hash() 的意義在于使hash 結果不同

hash 算法的好壞直接影響hash 結構的效率，壞的hash 算法極端情況下可能會使hash 結構的存取效率從O(1)退化到O(n)。1.8 之是以把9 次擾動降到2 次，是出于計算效率的考慮。

考點二：& 字元雖然和 % 效果一樣，但是操作效率更高

考點三：為什麼int，String 适合最為key？

int 和 String 的好處在于hash 出來的值不會改變。如果是一個對象，那麼他們可能會因為内部引用的改變而hashCode 值的改變，會導緻存儲重複的資料或找不到資料的情況。

考點四：并發操作導緻的添加丢失和環形連結清單的産生過程

知識點拓展

不僅僅是HashMap 的東西，根據你的回答，面試官會引出很多其他的問題，是以你在自己設計回答的過程中可以有意識引導面試官問出你熟悉的内容，安排的明明白白。

拓展一：解決Hash 沖突的不同方案

鍊位址法

開發位址：線性探測法、平方探測法

完全散列：布谷鳥散列

拓展二：HashMap 是淺拷貝，說一說淺拷貝和深拷貝的差別

拓展三：說一說Collections.synchronizedMap()和HashTable 的差別

拓展四：說一說HashMap 如何實作有序(LinkHashMap 和TreeMap)以及他們的差别

拓展五：說一說ConcurrentHashMap 如何實作線程安全

結尾

這篇文章更多的是HashMap 面試怎麼答，以及需要注意的知識點，希望對你有所幫助。

HashMap 的東西太多，因個人能力有限不能一一道全，後面如果變強了我會重新補全

最後，如果你跟我一樣都喜歡java，也在學習java的道路上奔跑，歡迎你添加 V X sweetbest130 每天都會分享java最新業内資料，共同交流學習，讓學習變（編）成（程）一種習慣！