最近看了布隆去重原理，發(fā)現(xiàn)一個(gè)詞哈希沖突特意去查了下

參考

哈希沖突的產(chǎn)生原因

哈希是通過對數(shù)據(jù)進(jìn)行再壓縮，提高效率的一種解決方法。但由于通過哈希函數(shù)產(chǎn)生的哈希值
是有限的，而數(shù)據(jù)可能比較多，導(dǎo)致經(jīng)過哈希函數(shù)處理后仍然有不同的數(shù)據(jù)對應(yīng)相同的哈希值。
這時(shí)候就產(chǎn)生了哈希沖突。

產(chǎn)生哈希沖突的影響因素

裝填因子（裝填因子=數(shù)據(jù)總數(shù) / 哈希表長）、哈希函數(shù)、處理沖突的方法

解決哈希沖突的四種方法

1.開放地址方法

　?。?）線性探測

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

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

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

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

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

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

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

　　（1）拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長度較短；

　?。?）由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請的，故它更適合于造表前無法確定表長的情況；

　?。?）開放定址法為減少?zèng)_突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間；

　?。?）在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。
　　缺點(diǎn)：

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

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

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

4.再哈希法

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