哈希沖突的產(chǎn)生原因
哈希是通過對數(shù)據(jù)進行再壓縮，提高效率的一種解決方法。但由于通過哈希函數(shù)產(chǎn)生的哈希值是有限的，而數(shù)據(jù)可能比較多，導致經(jīng)過哈希函數(shù)處理后仍然有不同的數(shù)據(jù)對應(yīng)相同的索引值。這時候就產(chǎn)生了哈希沖突（兩個值都需要同一個地址索引位置）。
產(chǎn)生哈希沖突的影響因素
裝填因子（裝填因子=數(shù)據(jù)總數(shù) / 哈希表長）、哈希函數(shù)、處理沖突的方法
解決哈希沖突的四種方法
1.開放地址方法(再散列法)
可以通俗理解為所有的地址都對所有的數(shù)值開放，而不是鏈式地址法的封閉方式，一個數(shù)值固定在一個索引地址位置。
p1=hash(key)如果沖突就在p1地址的基礎(chǔ)上+1或者散列處理，p2=hash(p1)....
?。?）線性探測
按順序決定值時，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來值的基礎(chǔ)上往后加一個單位，直至不發(fā)生哈希沖突。
?。?）再平方探測
按順序決定值時，如果某數(shù)據(jù)的值已經(jīng)存在，則在原來值的基礎(chǔ)上先加1的平方個單位，若仍然存在則減1的平方個單位。隨之是2的平方，3的平方等等。直至不發(fā)生哈希沖突。
和線性探測相比就是改變探測了步長。因為如果都是+1來探測在數(shù)據(jù)量比較大的情況下，效率會很差。
?。?）偽隨機探測
按順序決定值時，如果某數(shù)據(jù)已經(jīng)存在，通過隨機函數(shù)隨機生成一個數(shù)，在原來值的基礎(chǔ)上加上隨機數(shù)，直至不發(fā)生哈希沖突。
2.鏈式地址法（HashMap的哈希沖突解決方法）
對于相同的值，使用鏈表進行連接。使用數(shù)組存儲每一個鏈表。
優(yōu)點：
?。?）拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短；
?。?）由于拉鏈法中各鏈表上的結(jié)點空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況；
?。?）開放定址法為減少沖突，要求裝填因子α較小，故當結(jié)點規(guī)模較大時會浪費很多空間。而拉鏈法中可取α≥1，且結(jié)點較大時，拉鏈法中增加的指針域可忽略不計，因此節(jié)省空間；
? ? ? ?（4）在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點的操作易于實現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的結(jié)點即可。
????????缺點：
指針占用較大空間時，會造成空間浪費，若空間用于增大散列表規(guī)模進而提高開放地址法的效率。
3.建立公共溢出區(qū)
建立公共溢出區(qū)存儲所有哈希沖突的數(shù)據(jù)。
4.再哈希法
對于沖突的哈希值再次進行哈希處理，直至沒有哈希沖突。
可以理解為p=hash(key)如果沖突就p=hash2(key)....
參考文獻：
