數(shù)據(jù)結(jié)構(gòu)中散列表沖突的處理方式

這篇文章給大家分享的是有關(guān)數(shù)據(jù)結(jié)構(gòu)中散列表沖突的處理方式的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧。

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

   散列是在記錄的存儲(chǔ)位置和它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使得每個(gè)關(guān)鍵字key對(duì)應(yīng)一個(gè)存儲(chǔ)位置f(key)，建立了關(guān)鍵字與存儲(chǔ)位置的相互對(duì)應(yīng)關(guān)系，這種關(guān)系 f 稱為散列函數(shù)（哈希函數(shù)）。

查找過(guò)程中，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個(gè)因素：

1. 散列函數(shù)是否均勻；

2. 處理沖突的方法；

3. 散列表的裝填因子。

散列表的裝填因子定義為：α= 填入表中的元素個(gè)數(shù) / 散列表的長(zhǎng)度

α是散列表裝滿程度的標(biāo)志因子。由于表長(zhǎng)是定值，α與“填入表中的元素個(gè)數(shù)”成正比，所以，α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。

實(shí)際上，散列表的平均查找長(zhǎng)度是裝填因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。

解決哈希沖突的方法一般有：

NO.1開放定址法

所謂的開放定址法就是一旦發(fā)生了沖突，就去尋找下一個(gè)空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。

公式：f(key)=(f(key)+di)%m(di=1,2,3….m-1)

比如說(shuō)，關(guān)鍵字集合為{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，表長(zhǎng)為12。散列函數(shù)f(key) = key mod 12。

當(dāng)計(jì)算前5個(gè)數(shù){12, 67, 56, 16, 25}時(shí)，都是沒(méi)有沖突的散列地址，直接存入；計(jì)算key = 37時(shí)，發(fā)現(xiàn)f(37) = 1，此時(shí)就與25所在的位置沖突。于是應(yīng)用上面的公式f(37) = (f(37) + 1) mod 12 =2,。于是將37存入下標(biāo)為2的位置。接下來(lái)22,29,15,47都沒(méi)有沖突，正常的存入。到了48，計(jì)算得到f(48) = 0，與12所在的0位置沖突了，不要緊，我們f(48) = (f(48) + 1） mod 12 = 1，此時(shí)又與25所在的位置沖突。于是f(48) = (f(48) + 2） mod 12 = 2，還是沖突......一直到f(48) = (f(48) + 6） mod 12 = 6時(shí)，才有空位，如下表所示。

序號(hào)	0	1	2	3	4	5	6	7	8	9	10	11
關(guān)鍵字	12	25			16			67	56

NO.2再哈希法

對(duì)于散列表來(lái)說(shuō)，可以事先準(zhǔn)備多個(gè)散列函數(shù)。

公式：fi(key)=RHi(key)(i=1,2,3…,k)

這里RHi 就是不同的散列函數(shù)，可以把除留余數(shù)、折疊、平方取中全部用上。每當(dāng)發(fā)生散列地址沖突時(shí)，就換一個(gè)散列函數(shù)計(jì)算。

這種方法能夠使得關(guān)鍵字不產(chǎn)生聚集，但相應(yīng)地也增加了計(jì)算的時(shí)間。

NO.3鏈地址法（拉鏈法）

將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在一個(gè)單鏈表中，稱這種表為同義詞子表，在散列表中只存儲(chǔ)所有同義詞子表前面的指針。對(duì)于關(guān)鍵字集合{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，用前面同樣的12為余數(shù)，進(jìn)行除留余數(shù)法，可以得到下圖結(jié)構(gòu)。

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

這個(gè)方法是當(dāng)你時(shí)重新給你找個(gè)地址，為所有沖突的關(guān)鍵字建立一個(gè)公共的溢出區(qū)來(lái)存放。

就前面的例子而言，共有三個(gè)關(guān)鍵字37、48、34與之前的關(guān)鍵字位置有沖突，那就將它們存儲(chǔ)到溢出表中。如下圖所示。

在查找時(shí)，對(duì)給定值通過(guò)散列函數(shù)計(jì)算出散列地址后，先與基本表的相應(yīng)位置進(jìn)行比對(duì)，如果相等，則查找成功；如果不相等，則到溢出表中進(jìn)行順序查找。如果相對(duì)于基本表而言，有沖突的數(shù)據(jù)很少的情況下，公共溢出區(qū)的結(jié)構(gòu)對(duì)查找性能來(lái)說(shuō)還是非常高的。

感謝各位的閱讀！關(guān)于數(shù)據(jù)結(jié)構(gòu)中散列表沖突的處理方式就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！

當(dāng)前題目：數(shù)據(jù)結(jié)構(gòu)中散列表沖突的處理方式
本文網(wǎng)址：http://muchs.cn/article40/jojjho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、、用戶體驗(yàn)、電子商務(wù)、手機(jī)網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站

廣告

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