引言

大家好呀，我是你們的小米，一個積極活潑的程序員小伙伴！今天我們聊聊Java面試中的常見問題——“HashMap是怎么解決哈希沖突的？”。相信不少人都對這個問題既熟悉又陌生，知道它很重要，但要講清楚，可能還得捋一捋思路。別急，今天我們就通過一個小故事，輕松搞懂這個知識點！

HashMap的世界：存儲的藝術

想象一個圖書管理員阿牛，他需要管理一間藏書豐富的圖書館。為了快速找到書，阿牛決定設計一個存書系統：

• 書本編號（Key）： 每本書都有獨特的編號，類似HashMap的key。
• 書柜號（哈希函數）： 阿牛通過某種算法，把書的編號轉化為一個書柜號，這相當于HashMap的hashCode()。
• 書的位置（存儲）： 阿牛把書放進對應的書柜。

問題來了：哈希沖突

一天，阿牛發現編號 123 和 789 的兩本書，居然被分配到同一個書柜里！這就是哈希沖突——不同的Key，經過哈希函數計算，得到了相同的Hash值。

這種情況在HashMap里并不罕見，因為HashMap的底層結構決定了哈希值會映射到一個固定大小的數組中，必然存在沖突的可能。那么阿牛該怎么辦呢？

HashMap的解決方案

為了應對哈希沖突，阿牛想出了兩種辦法，分別對應HashMap在不同版本中的處理方式：

1. 鏈地址法（JDK 1.8之前的實現）

阿牛決定用鏈表解決問題。如果書柜里已經有書，他就直接在書柜旁邊放一個籃子，把新書放進籃子里。

• 每次存書時，阿牛會先檢查書柜里是否已經有書。如果有，就把新書添加到鏈表的尾部。
• 每次取書時，阿牛會按照鏈表依次查找，直到找到目標書。

在代碼中，鏈地址法就是用鏈表存儲同一個桶（bucket）中的所有Key-Value對：

圖片

雖然這種方法簡單易行，但當鏈表長度過長時，性能會急劇下降。因為查找需要遍歷整個鏈表，時間復雜度從理想情況下的O(1)退化為O(n)。

2. 紅黑樹（JDK 1.8之后的新方案）

阿牛覺得鏈表太慢了，于是升級了他的存書策略——如果書柜旁邊的籃子（鏈表）里的書超過一定數量（8本），他就用紅黑樹來替代鏈表。

紅黑樹是一種自平衡二叉搜索樹，能夠顯著提升查找效率：

• 存儲時： 如果籃子里的書數量超過了閾值，就將鏈表轉換為紅黑樹。
• 查找時： 紅黑樹的時間復雜度是O(log n)，比鏈表的O(n)高效得多。

在代碼中，紅黑樹的實現邏輯看起來大致如下：

圖片

這里有一個小細節：如果HashMap的容量較小，鏈表不會直接轉換為紅黑樹，而是優先擴容。這是因為紅黑樹相對復雜，適用于大規模數據。

總結：HashMap的兩種處理方式

為了方便大家記憶，我們用一個表格總結一下：

圖片

面試中的延伸問題

如果你在面試中被問到這個問題，面試官可能還會進一步追問：

1、哈希沖突的概率高嗎？

答：HashMap的哈希函數經過優化，盡量均勻分布Key，但沖突無法完全避免。

2、為什么選用紅黑樹？

答：紅黑樹具有自平衡特性，插入、刪除和查找的效率較高，且最壞情況的時間復雜度是O(log n)。

3、什么時候會退化為鏈表？

答：如果HashMap的容量不足，沖突嚴重，鏈表長度可能增加。

彩蛋：如何手寫一個簡易HashMap？

如果你有時間，不妨自己嘗試實現一個簡易版的HashMap，幫助加深理解：

圖片