這篇文章給大家分享的是有關數(shù)據(jù)結構中散列表沖突的處理方式的內容。小編覺得挺實用的，因此分享給大家做個參考。一起跟隨小編過來看看吧。
散列是在記錄的存儲位置和它的關鍵字之間建立一個確定的對應關系f，使得每個關鍵字key對應一個存儲位置f(key)，建立了關鍵字與存儲位置的相互對應關系，這種關系 f 稱為散列函數(shù)（哈希函數(shù)）。
查找過程中，關鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個因素：
1. 散列函數(shù)是否均勻；
2. 處理沖突的方法；
3. 散列表的裝填因子。
散列表的裝填因子定義為：α= 填入表中的元素個數(shù) / 散列表的長度
α是散列表裝滿程度的標志因子。由于表長是定值，α與“填入表中的元素個數(shù)”成正比，所以，α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。
實際上，散列表的平均查找長度是裝填因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。
解決哈希沖突的方法一般有：
NO.1開放定址法
所謂的開放定址法就是一旦發(fā)生了沖突，就去尋找下一個空的散列地址，只要散列表足夠大，空的散列地址總能找到，并將記錄存入。
公式：f(key)=(f(key)+di)%m(di=1,2,3….m-1)
比如說，關鍵字集合為{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，表長為12。散列函數(shù)f(key) = key mod 12。
當計算前5個數(shù){12, 67, 56, 16, 25}時，都是沒有沖突的散列地址，直接存入；計算key = 37時，發(fā)現(xiàn)f(37) = 1，此時就與25所在的位置沖突。于是應用上面的公式f(37) = (f(37) + 1) mod 12 =2,。于是將37存入下標為2的位置。接下來22,29,15,47都沒有沖突，正常的存入。到了48，計算得到f(48) = 0，與12所在的0位置沖突了，不要緊，我們f(48) = (f(48) + 1） mod 12 = 1，此時又與25所在的位置沖突。于是f(48) = (f(48) + 2） mod 12 = 2，還是沖突......一直到f(48) = (f(48) + 6） mod 12 = 6時，才有空位，如下表所示。
| 序號 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 關鍵字 | 12 | 25 | 16 | 67 | 56 |
NO.2再哈希法
對于散列表來說，可以事先準備多個散列函數(shù)。
公式：fi(key)=RHi(key)(i=1,2,3…,k)
這里RHi 就是不同的散列函數(shù)，可以把除留余數(shù)、折疊、平方取中全部用上。每當發(fā)生散列地址沖突時，就換一個散列函數(shù)計算。
這種方法能夠使得關鍵字不產(chǎn)生聚集，但相應地也增加了計算的時間。
NO.3鏈地址法（拉鏈法）
將所有關鍵字為同義詞的記錄存儲在一個單鏈表中，稱這種表為同義詞子表，在散列表中只存儲所有同義詞子表前面的指針。對于關鍵字集合{12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}，用前面同樣的12為余數(shù)，進行除留余數(shù)法，可以得到下圖結構。
NO.4建立公共溢出區(qū)
這個方法是當你時重新給你找個地址，為所有沖突的關鍵字建立一個公共的溢出區(qū)來存放。
就前面的例子而言，共有三個關鍵字37、48、34與之前的關鍵字位置有沖突，那就將它們存儲到溢出表中。如下圖所示。
在查找時，對給定值通過散列函數(shù)計算出散列地址后，先與基本表的相應位置進行比對，如果相等，則查找成功；如果不相等，則到溢出表中進行順序查找。如果相對于基本表而言，有沖突的數(shù)據(jù)很少的情況下，公共溢出區(qū)的結構對查找性能來說還是非常高的。
感謝各位的閱讀！關于數(shù)據(jù)結構中散列表沖突的處理方式就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
另外有需要云服務器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
重慶分公司
重慶分公司
