出現(xiàn)Hash沖突以及哪些解決散列沖突的方法是什么，針對這個問題，這篇文章詳細介紹了相對應的分析和解答，希望可以幫助更多想解決這個問題的小伙伴找到更簡單易行的方法。

平陽ssl適用于網(wǎng)站、小程序/APP、API接口等需要進行數(shù)據(jù)傳輸應用場景，ssl證書未來市場廣闊！成為創(chuàng)新互聯(lián)的ssl證書銷售渠道，可以享受市場價格4-6折優(yōu)惠！如果有意向歡迎電話聯(lián)系或者加微信：18982081108（備注：SSL證書合作）期待與您的合作！

通過構(gòu)造性能良好的哈希函數(shù)，可以減少沖突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個關(guān)鍵問題。

創(chuàng)建哈希表和查找哈希表都會遇到?jīng)_突，兩種情況下解決沖突的方法應該一致。

下面以創(chuàng)建哈希表為例，說明解決沖突的方法。常用的解決沖突方法有以下四種：

開放定址法

這種方法也稱再散列法，其基本思想是：當關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時，以p為基礎，產(chǎn)生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產(chǎn)生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。

這種方法有一個通用的再散列函數(shù)形式：

Hi=（H（key）+di）% m   i=1，2，…，n

其中H（key）為哈希函數(shù)，m 為表長，di稱為增量序列。增量序列的取值方式不同，相應的再散列方式也不同。主要有以下三種：

線性探測再散列

dii=1，2，3，…，m-1

這種方法的特點是：沖突發(fā)生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。

二次探測再散列

di=12，-12，22，-22，…，k2，-k2    ( k<=m/2 )

這種方法的特點是：沖突發(fā)生時，在表的左右進行跳躍式探測，比較靈活。

偽隨機探測再散列，di=偽隨機數(shù)序列。

具體實現(xiàn)時，應建立一個偽隨機數(shù)發(fā)生器，（如i=(i+p) % m），并給定一個隨機數(shù)做起點。

例如，已知哈希表長度m=11，哈希函數(shù)為：H（key）= key  %  11，則H（47）=3，H（26）=4，H（60）=5，假設下一個關(guān)鍵字為69，則H（69）=3，與47沖突。

如果用線性探測再散列處理沖突，下一個哈希地址為H1=（3 + 1）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 + 2）% 11 = 5，還是沖突，繼續(xù)找下一個哈希地址為H3=（3 + 3）% 11 = 6，此時不再沖突，將69填入5號單元。

如果用二次探測再散列處理沖突，下一個哈希地址為H1=（3 + 12）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 - 12）% 11 = 2，此時不再沖突，將69填入2號單元。

如果用偽隨機探測再散列處理沖突，且偽隨機數(shù)序列為：2，5，9，……..，則下一個哈希地址為H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個哈希地址為H2=（3 + 5）% 11 = 8，此時不再沖突，將69填入8號單元。

再哈希法

這種方法是同時構(gòu)造多個不同的哈希函數(shù)：

Hi=RH1（key）  i=1，2，…，k

當哈希地址Hi=RH1（key）發(fā)生沖突時，再計算Hi=RH2（key）……，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計算時間。

鏈地址法

這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經(jīng)常進行插入和刪除的情況。

建立公共溢出區(qū)

這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。

優(yōu)缺點

開放散列（open hashing）/ 拉鏈法（針對桶鏈結(jié)構(gòu)）

1）優(yōu)點： 

①對于記錄總數(shù)頻繁可變的情況，處理的比較好（也就是避免了動態(tài)調(diào)整的開銷） 

②由于記錄存儲在結(jié)點中，而結(jié)點是動態(tài)分配，不會造成內(nèi)存的浪費，所以尤其適合那種記錄本身尺寸（size）很大的情況，因為此時指針的開銷可以忽略不計了 

③刪除記錄時，比較方便，直接通過指針操作即可

2）缺點： 

①存儲的記錄是隨機分布在內(nèi)存中的，這樣在查詢記錄時，相比結(jié)構(gòu)緊湊的數(shù)據(jù)類型（比如數(shù)組），哈希表的跳轉(zhuǎn)訪問會帶來額外的時間開銷 

②如果所有的 key-value 對是可以提前預知，并之后不會發(fā)生變化時（即不允許插入和刪除），可以人為創(chuàng)建一個不會產(chǎn)生沖突的完美哈希函數(shù)（perfect hash function），此時封閉散列的性能將遠高于開放散列 

③由于使用指針，記錄不容易進行序列化（serialize）操作

封閉散列（closed hashing）/ 開放定址法

1）優(yōu)點： 

①記錄更容易進行序列化（serialize）操作 

②如果記錄總數(shù)可以預知，可以創(chuàng)建完美哈希函數(shù)，此時處理數(shù)據(jù)的效率是非常高的

2）缺點： 

①存儲記錄的數(shù)目不能超過桶數(shù)組的長度，如果超過就需要擴容，而擴容會導致某次操作的時間成本飆升，這在實時或者交互式應用中可能會是一個嚴重的缺陷 

②使用探測序列，有可能其計算的時間成本過高，導致哈希表的處理性能降低 

③由于記錄是存放在桶數(shù)組中的，而桶數(shù)組必然存在空槽，所以當記錄本身尺寸（size）很大并且記錄總數(shù)規(guī)模很大時，空槽占用的空間會導致明顯的內(nèi)存浪費 

④刪除記錄時，比較麻煩。比如需要刪除記錄a，記錄b是在a之后插入桶數(shù)組的，但是和記錄a有沖突，是通過探測序列再次跳轉(zhuǎn)找到的地址，所以如果直接刪除a，a的位置變?yōu)榭詹郏詹凼遣樵冇涗浭〉慕K止條件，這樣會導致記錄b在a的位置重新插入數(shù)據(jù)前不可見，所以不能直接刪除a，而是設置刪除標記。這就需要額外的空間和操作。

關(guān)于出現(xiàn)Hash沖突以及哪些解決散列沖突的方法是什么問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道了解更多相關(guān)知識。

當前題目：出現(xiàn)Hash沖突以及哪些解決散列沖突的方法是什么
文章位置：http://www.chinadenli.net/article36/ieocsg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供企業(yè)網(wǎng)站制作、網(wǎng)站改版、外貿(mào)網(wǎng)站建設、營銷型網(wǎng)站建設、外貿(mào)建站、網(wǎng)站設計公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)