引言

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

HashMap的世界：存儲(chǔ)的藝術(shù)

想象一個(gè)圖書(shū)管理員阿牛，他需要管理一間藏書(shū)豐富的圖書(shū)館。為了快速找到書(shū)，阿牛決定設(shè)計(jì)一個(gè)存書(shū)系統(tǒng)：

• 書(shū)本編號(hào)（Key）： 每本書(shū)都有獨(dú)特的編號(hào)，類(lèi)似HashMap的key。
• 書(shū)柜號(hào)（哈希函數(shù)）： 阿牛通過(guò)某種算法，把書(shū)的編號(hào)轉(zhuǎn)化為一個(gè)書(shū)柜號(hào)，這相當(dāng)于HashMap的hashCode()。
• 書(shū)的位置（存儲(chǔ)）： 阿牛把書(shū)放進(jìn)對(duì)應(yīng)的書(shū)柜。

問(wèn)題來(lái)了：哈希沖突

一天，阿牛發(fā)現(xiàn)編號(hào) 123 和 789 的兩本書(shū)，居然被分配到同一個(gè)書(shū)柜里！這就是哈希沖突——不同的Key，經(jīng)過(guò)哈希函數(shù)計(jì)算，得到了相同的Hash值。

這種情況在HashMap里并不罕見(jiàn)，因?yàn)镠ashMap的底層結(jié)構(gòu)決定了哈希值會(huì)映射到一個(gè)固定大小的數(shù)組中，必然存在沖突的可能。那么阿牛該怎么辦呢？

HashMap的解決方案

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

1. 鏈地址法（JDK 1.8之前的實(shí)現(xiàn)）

阿牛決定用鏈表解決問(wèn)題。如果書(shū)柜里已經(jīng)有書(shū)，他就直接在書(shū)柜旁邊放一個(gè)籃子，把新書(shū)放進(jìn)籃子里。

• 每次存書(shū)時(shí)，阿牛會(huì)先檢查書(shū)柜里是否已經(jīng)有書(shū)。如果有，就把新書(shū)添加到鏈表的尾部。
• 每次取書(shū)時(shí)，阿牛會(huì)按照鏈表依次查找，直到找到目標(biāo)書(shū)。

在代碼中，鏈地址法就是用鏈表存儲(chǔ)同一個(gè)桶（bucket）中的所有Key-Value對(duì)：

圖片

雖然這種方法簡(jiǎn)單易行，但當(dāng)鏈表長(zhǎng)度過(guò)長(zhǎng)時(shí)，性能會(huì)急劇下降。因?yàn)椴檎倚枰闅v整個(gè)鏈表，時(shí)間復(fù)雜度從理想情況下的O(1)退化為O(n)。

2. 紅黑樹(shù)（JDK 1.8之后的新方案）

阿牛覺(jué)得鏈表太慢了，于是升級(jí)了他的存書(shū)策略——如果書(shū)柜旁邊的籃子（鏈表）里的書(shū)超過(guò)一定數(shù)量（8本），他就用紅黑樹(shù)來(lái)替代鏈表。

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

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

在代碼中，紅黑樹(shù)的實(shí)現(xiàn)邏輯看起來(lái)大致如下：

圖片

這里有一個(gè)小細(xì)節(jié)：如果HashMap的容量較小，鏈表不會(huì)直接轉(zhuǎn)換為紅黑樹(shù)，而是優(yōu)先擴(kuò)容。這是因?yàn)榧t黑樹(shù)相對(duì)復(fù)雜，適用于大規(guī)模數(shù)據(jù)。

總結(jié)：HashMap的兩種處理方式

為了方便大家記憶，我們用一個(gè)表格總結(jié)一下：

圖片

面試中的延伸問(wèn)題

如果你在面試中被問(wèn)到這個(gè)問(wèn)題，面試官可能還會(huì)進(jìn)一步追問(wèn)：

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

答：HashMap的哈希函數(shù)經(jīng)過(guò)優(yōu)化，盡量均勻分布Key，但沖突無(wú)法完全避免。

2、為什么選用紅黑樹(shù)？

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

3、什么時(shí)候會(huì)退化為鏈表？

答：如果HashMap的容量不足，沖突嚴(yán)重，鏈表長(zhǎng)度可能增加。

彩蛋：如何手寫(xiě)一個(gè)簡(jiǎn)易HashMap？

如果你有時(shí)間，不妨自己嘗試實(shí)現(xiàn)一個(gè)簡(jiǎn)易版的HashMap，幫助加深理解：

圖片