《面試1v1》HashMap
沒有人比中國人更懂 HashMap
我是 javapub，一名 Markdown 程序員從?????，八股文種子選手。
面試官：HashMap 是Java程序員用得最頻繁的集合之一,可以給我簡單介紹一下它的內部實現機制嗎?
候選人： HashMap 是一個散列映射表,它存儲的內容是鍵值對(key-value)映射。
面試官：那它內部具體是如何實現的呢?
候選人： HashMap 在內部實現上主要包含以下幾個結構:
數組:HashMap 的核心數據結構就是一個 Entry[] 數組。
鏈表:每個數組元素是一個單鏈表結構的頭節(jié)點,當沖突產生時,會在鏈表中追加元素。
節(jié)點:每個鏈表節(jié)點包含四個字段,key, value, hash 和 next。其中 key 和 value 是映射中的鍵值,hash 是 key 的 hashCode,next 是指向下一個節(jié)點的指針。
面試官：為什么要選擇數組和鏈表這兩種數據結構呢?
候選人： 這是因為 HashMap 要保證高效的增刪改查操作,數組和鏈表各自的優(yōu)點可以滿足這個要求:
數組實現通過散列算法,可以快速定位到相應的位置,保證查詢的時間復雜度為O(1)。
鏈表在沖突發(fā)生時,通過在尾部添加節(jié)點,可以高效地進行插入操作。同時也方便進行刪除操作。 所以,HashMap通過數組實現快速查找,通過鏈表解決沖突,既可以保證查詢效率,也可以應對散列算法產生碰撞的情況。這是它的核心優(yōu)雅與高效之處。
面試官：HashMap 是非線程安全的,它有哪些線程安全的替代方案呢?
候選人： 對于線程安全的需求,可以選擇以下替代方案:
HashTable:HashMap 的線程安全版,內部的方法基本相同,只是進行了線程安全的同步處理。
ConcurrentHashMap:Java 7 的實現使用分段鎖,既保證線程安全,也不會影響性能。Java 8 使用 CAS 操作來保證并發(fā)度高的操作。
Hashtable:Java 老版本中提供的 hash 表實現,線程安全,但相比于前兩者性能較低。現在不建議使用。 所以,如果不需要高并發(fā),HashTable 是一個簡單直接的替代方案;如果對性能有較高要求,推薦使用 ConcurrentHashMap。兩者相比,ConcurrentHashMap 的并發(fā)度更高,性能也更佳,是當前推薦的線程安全 hash 表方案。
面試官：簡單說一下 HashMap 的 put 操作過程。
候選人： HashMap 的 put(key, value) 方法大致分為以下幾步:
計算key的hash值,這一步通過key的hashCode()方法計算,然后進一步處理高16位和低16位產生最終的hash值。
//?計算key的hash值?
final?int?hash?=?hash(key);
根據hash值定位數組索引,如果沒有沖突就直接插入。如果產生沖突,就插入沖突鏈表中。
int?i?=?indexFor(hash,?table.length);
//?若i位置為空,直接新建節(jié)點添加,size增加????
if?(table[i]?==?null)?{??
????table[i]?=?newNode(hash,?key,?value,?null);
}?
//?若產生沖突,將節(jié)點添加到鏈表尾部??
else?{??
????...
}?
如果鏈表長度超過TREEIFY_THRESHOLD(默認8),就把鏈表轉換為紅黑樹。這一步可以提高查詢效率。
//?若鏈表長度大于8,鏈表轉換為紅黑樹????
if?(binCount?>?TREEIFY_THRESHOLD)?
????treeifyBin(tab,?hash);??
如果節(jié)點已經存在,就替換oldValue為新值。
//?若節(jié)點已存在,用新值替換舊值
for?(Node<K,V>?e?=?p;;?e?=?e.next)?{
????if?(e.hash?==?hash?&&?((k?=?e.key)?==?key?||?key.equals(k)))?{
????????e.value?=?value;
????????break;
????}
如果容量達到閾值,就進行resize兩倍擴容,這一步可以減少hash沖突,提高查詢性能。
if?(++size?>?threshold)?
????resize(newCapacity);?
面試官：說說HashMap的擴容機制。
候選人： HashMap的擴容機制就是在put時,如果size已經超過閾值threshold,就會進行擴容resize操作。在擴容時,capacity的容量會擴大兩倍,并會重新計算每個節(jié)點的hash值和索引位置。
面試官：為什么要進行兩倍擴容?
候選人： 這是因為HashMap采用開放定址法來解決沖突,每次擴容時,原有的hash值都需要重新計算,如果擴容過小,重新計算后的索引位置有很大概率仍然會發(fā)生沖突,效果不明顯。如果采用兩倍擴容,然后重新計算hash值,那么沖突的概率會大大減少,查詢性能就能得到較大提高。
面試官：說說resize的實現過程。
候選人： resize的實現過程主要分為以下幾步:
將oldTable的值賦給newTable,newTable的長度是oldTable的兩倍。
Node<K,V>[]?newTable?=?(Node<K,V>[])new?Node[newCapacity];
table?=?newTable;
遍歷oldTable的每個桶,如果桶位非空,就重新計算每個節(jié)點的hash值和索引,并放入newTable對應的桶中。
for?(int?j?=?0;?j?<?oldCap;?++j)?{
????Node<K,V>?e;
????if?((e?=?oldTab[j])?!=?null)?{
????????oldTab[j]?=?null;
????????if?(e.next?==?null)
????????????newTab[e.hash?&?(newCap?-?1)]?=?e;
????????else?...?
????}
}?
resize的過程中,如果節(jié)點的新的索引位置相同,就會在鏈表中追加新節(jié)點。如果不同,就在新位置形成新的鏈表。
else?if?(e?instanceof?TreeNode)?
????((TreeNode<K,V>)e).split(this,?newTab,?j,?oldCap);
else?{?//?鏈表情況?
????Node<K,V>?loHead?=?null,?loTail?=?null;
????Node<K,V>?hiHead?=?null,?hiTail?=?null;
????Node<K,V>?next;
????do?{
????????next?=?e.next;
????????...
????}?while?((e?=?next)?!=?null);
}
如果鏈表長度過長,就會先將鏈表轉成紅黑樹,再進行resize。這一步可以有效提高性能。
面試官：最后,總結一下HashMap的優(yōu)勢。
候選人： HashMap的主要優(yōu)勢有:
查詢和修改的時間復雜度都是O(1),這是通過哈希算法實現的。
HashMap是非線程安全的,可以選擇并發(fā)版的ConcurrentHashMap。
HashMap通過擴容和鏈表轉紅黑樹,可以動態(tài)調整容量和提高查詢性能。
HashMap支持null鍵和null值。
HashMap的實現是非常巧妙的,通過數組和鏈表組合,既可以支持快速查找,也可以解決沖突。
HashMap有很高的空間利用率,可以存儲大量元素。 所以,總之,HashMap的優(yōu)勢在于:性能高效,支持null,動態(tài)擴容,空間利用率高,這也是它成為Java最常用的Map實現的原因。
面試官：說說HashMap的缺點。
候選人： HashMap也存在一定的缺點:
HashMap是非線程安全的。多線程環(huán)境下,需要對HashMap進行同步處理,可以選擇HashTable或者ConcurrentHashMap。
HashMap的迭代順序是未定義的。每次迭代的順序可能不同,如果需要順序,可以采用LinkedHashMap。
HashMap的遍歷也是O(n)的時間復雜度,如果集合很大,遍歷會很慢?？梢酝ㄟ^提高初始容量和負載因子來減少沖突及拉鏈長度,提高性能。
如果Hash算法設計不當,HashMap的性能會很差。比如大量Hash沖突會導致拉鏈過長,嚴重影響查詢性能。對于自定義類型作為鍵,需要重寫hashCode()方法來保證分布均勻。
HashMap采用拉鏈法解決沖突,極端情況下(數據全部使用相同hashCode)會退化為鏈表,變成O(n)的時間復雜度,查詢性能變差。這種情況可以通過使用TreeMap來改進。
HashMap的初始容量和擴容機制的設計不當,會造成非必要的數學開銷,影響性能。
HashMap不支持排序,如果需要排序可以使用TreeMap或者對HashMap進行排序。 所以,總結來說,HashMap的主要缺點在于:非線程安全,遍歷慢,迭代順序不定,自定義鍵的hashCode()設計不好會導致性能下降,不支持排序等。但這些缺點都可以通過選擇其他Map實現或輔助結構來補充。如果能清楚 HashMap 的這些缺點,就可以更好地選擇和使用它。
面試官：你說的很全面和深入。HashMap作為一個高頻使用的數據結構,你對它的理解已經相當深刻了。
候選人： 謝謝面試官的夸獎!HashMap確實是我常用的數據結構之一,我通過閱讀源碼、實踐使用與論壇上的討論,對它的設計和實現有了比較深入的理解。但HashMap的內容還是非常之廣博,我還需要繼續(xù)學習和總結,以進一步加深理解,利用好它提供的功能,并在實際工作中發(fā)揮其優(yōu)勢。我會持續(xù)努力,不斷提高自己對這方面的認知。
面試官：很好,你對自己的提高有清醒的認識。最后,我想問你作為HashMap的替代,現在有什么其他的Map實現可以選擇?
候選人： 除了HashMap,Java中常用的Map還有:
Hashtable:HashMap的線程安全版本,性能差一些,現在不太建議使用。
ConcurrentHashMap:支持高并發(fā)的線程安全Map,在Java8之前使用分段鎖,之后使用CAS保證并發(fā)度高的操作。是HashMap的線程安全替代方案。
TreeMap:基于紅黑樹實現,支持排序,復雜度O(logN), Keys自動排序。
LinkedHashMap:內部維護著一個雙向鏈表,結合HashMap提供按插入順序或訪問順序遍歷Map中的條目。
EnumMap:鍵是枚舉類型,內部實現更加緊湊高效。
WeakHashMap:鍵是弱引用,容易被垃圾回收,防止內存泄露。 所以,根據需要的功能,有多個可替代的Map實現供選擇。但作為最基本和高效的實現,HashMap還是最為常用和推薦的。
面試官：很好,你的理解和應用已經相當不錯了。熟練運用設計模式,在項目開發(fā)中可以 large-scale 重構,提高系統(tǒng)擴展性和復用性。你繼續(xù)加深對各種設計模式的理解和運用,技術還會更上一層樓。
最后,你有什么問題想要提問嗎?今天的面試到此結束。
候選人： ?非常感謝面試官今天的時間!通過我們的交流,我對很多技術內容有了進一步的認識和提高,也清楚自己的不足和需要努力的方向。這對我來說很寶貴。 我現階段沒有其他問題了。我會繼續(xù)努力學習,不斷總結和實踐,特別是對數據結構、算法與設計模式等基礎內容的運用,提高自己的工程化水平與解決問題的能力。
再次感謝面試官!這是一次非常有價值的交流,很高興有機會進行這樣的技術探討。謝謝!
面試官： ?你的態(tài)度很好,技術也不錯,繼續(xù)努力深造,我相信你一定會越來越精進。這也是我作為面試官最喜歡看到的,不論最終結果如何,重要的是候選人的心態(tài)和潛力。 你也提出了很好的問題,我們進行了廣泛而深入的探討,這說明你在學習和工作中確實遇到過一定的困惑,而又積極主動尋求解決之道。這種積極主動的學習態(tài)度很難得,技術人員走的最遠的,永遠都是在學習和總結中不斷超越自己。
很高興今天的交流,這也使我有機會重溫。
最近我在更新《面試1v1》系列文章，主要以場景化的方式，講解我們在面試中遇到的問題，致力于讓每一位工程師拿到自己心儀的offer，感興趣可以關注公眾號JavaPub追更！
??目錄合集：
Gitee：https://gitee.com/rodert/JavaPub
GitHub：https://github.com/Rodert/JavaPub
http://javapub.net.cn
