哈希沖突的產(chǎn)生原因及解決方法

一、哈希沖突的產(chǎn)生原因
哈希是通過對(duì)數(shù)據(jù)進(jìn)行再壓縮，提高效率的一種解決方法。但由于通過哈希函數(shù)產(chǎn)生的哈希值是有限的，而數(shù)據(jù)可能比較多，導(dǎo)致經(jīng)過哈希函數(shù)處理后仍然有不同的數(shù)據(jù)對(duì)應(yīng)相同的值。這時(shí)候就產(chǎn)生了哈希沖突。
二、產(chǎn)生哈希沖突的影響因素
裝填因子（裝填因子=數(shù)據(jù)總數(shù) / 哈希表長(zhǎng)）、哈希函數(shù)、處理沖突的方法
三、解決哈希沖突的四種方法
1.開放地址方法
（1）線性探測(cè)

按順序決定值時(shí)，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來(lái)值的基礎(chǔ)上往后加一個(gè)單位，直至不發(fā)生哈希沖突。

（2）再平方探測(cè)

按順序決定值時(shí)，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來(lái)值的基礎(chǔ)上先加1的平方個(gè)單位，若仍然存在則減1的平方個(gè)單位。隨之是2的平方，3的平方等等。直至不發(fā)生哈希沖突。

（3）偽隨機(jī)探測(cè)

按順序決定值時(shí)，如果某數(shù)據(jù)已經(jīng)存在，通過隨機(jī)函數(shù)隨機(jī)生成一個(gè)數(shù)，在原來(lái)值的基礎(chǔ)上加上隨機(jī)數(shù)，直至不發(fā)生哈希沖突。



2.鏈?zhǔn)降刂贩ǎ℉ashMap的哈希沖突解決方法）

對(duì)于相同的值，使用鏈表進(jìn)行連接。使用數(shù)組存儲(chǔ)每一個(gè)鏈表。

優(yōu)點(diǎn)：
（1）拉鏈法處理沖突簡(jiǎn)單，且無(wú)堆積現(xiàn)象，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長(zhǎng)度較短；
（2）由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，故它更適合于造表前無(wú)法確定表長(zhǎng)的情況；
（3）開放定址法為減少?zèng)_突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間；
（4）在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡(jiǎn)單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。

缺點(diǎn)：

指針占用較大空間時(shí)，會(huì)造成空間浪費(fèi)，若空間用于增大散列表規(guī)模進(jìn)而提高開放地址法的效率。

3.建立公共溢出區(qū)

建立公共溢出區(qū)存儲(chǔ)所有哈希沖突的數(shù)據(jù)。

4.再哈希法

對(duì)于沖突的哈希值再次進(jìn)行哈希處理，直至沒有哈希沖突。




作者： 碼農(nóng)編程進(jìn)階筆記


歡迎關(guān)注微信公眾號(hào) ：碼農(nóng)編程進(jìn)階筆記