經(jīng)典面試題：怎么解決哈希碰撞？

回答重點(diǎn)

Hash 碰撞是指在使用哈希算法時(shí)，不同的輸入數(shù)據(jù)通過哈希函數(shù)計(jì)算后，得到了相同的哈希值（即散列值）。因?yàn)楣Ｖ迪嗤赃@些鍵會(huì)被映射到哈希表的同一個(gè)位置，從而引發(fā)“碰撞”。

常見有以下幾種方式解決哈希碰撞問題：

1）拉鏈法（鏈地址法）：

將哈希表中每個(gè)槽的位置變成一個(gè)鏈表，當(dāng)多個(gè)鍵的哈希值相同時(shí)，將它們存儲(chǔ)在同一個(gè)鏈表中。

2）開放尋址法：

如果出現(xiàn)碰撞，尋找哈希表中的下一個(gè)可用位置。

3）再哈希法（雙重哈希）：

在出現(xiàn)碰撞時(shí)，使用第二個(gè)哈希函數(shù)計(jì)算新的索引位置，減少碰撞的概率。

擴(kuò)展知識(shí)

拉鏈法（鏈地址法）

使用鏈表來處理沖突，每個(gè)哈希表的槽（bucket）不僅存儲(chǔ)單個(gè)元素，而是存儲(chǔ)指向鏈表頭部的指針。所有具有相同哈希值的元素都會(huì)被放入到同一個(gè)鏈表中。

優(yōu)點(diǎn)：

• 簡(jiǎn)單易實(shí)現(xiàn)，擴(kuò)展性好。
• 在處理大量數(shù)據(jù)時(shí)，性能更為穩(wěn)定。

缺點(diǎn)：

• 如果碰撞頻繁，鏈表會(huì)變長(zhǎng)，導(dǎo)致查詢性能下降。
• 需要額外的內(nèi)存來存儲(chǔ)鏈表的指針。

紅黑樹優(yōu)化

當(dāng)沖突產(chǎn)生的鏈表長(zhǎng)度超過一定閾值時(shí)，可以將鏈表轉(zhuǎn)換為紅黑樹。紅黑樹的查找時(shí)間復(fù)雜度為 O(log n)，相較于鏈表 O(n) 的查找復(fù)雜度，性能更高。

這個(gè)優(yōu)化可以大幅提升在極端情況下的查找性能。

缺點(diǎn)就是實(shí)現(xiàn)復(fù)雜，且需要更多的內(nèi)存空間。

在 Java 8 中的 HashMap 使用了鏈表轉(zhuǎn)紅黑樹的解決方案。詳細(xì)可看為什么 JDK 1.8 對(duì) HashMap 進(jìn)行了紅黑樹的改動(dòng)？

開放尋址法

在哈希表中尋找下一個(gè)空閑的槽位以存儲(chǔ)發(fā)生碰撞的元素，常見尋找方式有線性探查、平方探查和雙重散列。

優(yōu)點(diǎn)：

• 不需要額外的內(nèi)存來存儲(chǔ)指針或鏈表結(jié)構(gòu)。
• 如果負(fù)載因子低，查找和插入的效率較高。

缺點(diǎn)：

• 隨著哈希表的填充度增加，探查的次數(shù)會(huì)增加，導(dǎo)致性能下降。
• 刪除元素時(shí)候，不能真的刪除，只能打標(biāo)，否則會(huì)導(dǎo)致查找錯(cuò)誤。只能在下一個(gè)元素插入時(shí)，發(fā)現(xiàn)標(biāo)記后才能替換原來的元素。

尋找方式

1）線性探查法：

在哈希表中查找下一個(gè)連續(xù)的空槽，將碰撞的鍵存入該槽中。

2）平方探查法：

類似于線性探查，但探查的步長(zhǎng)是二次方，減少了聚集問題。

3）雙散列法：

使用兩個(gè)不同的哈希函數(shù)，第一次哈希決定初始位置，第二次哈希決定探查步長(zhǎng)。

幾種尋址方式本質(zhì)原理都差不多，僅演示下線性探測(cè)過程：

再哈希法（雙重哈希）

在出現(xiàn)碰撞時(shí)，使用第二個(gè)哈希函數(shù)計(jì)算新的索引位置，減少碰撞的概率