影響哈希查找效率的一個(gè)重要因素是哈希函數(shù)本身。當(dāng)兩個(gè)不同的數(shù)據(jù)元素的哈希值相同時(shí)，就會(huì)發(fā)生沖突。為減少發(fā)生沖突的可能性，哈希函數(shù)應(yīng)該將數(shù)據(jù)盡可能分散地映射到哈希表的每一個(gè)表項(xiàng)中。解決沖突的方法有以下兩種：

1、開(kāi)放定址法：

所謂開(kāi)放定址法，即由關(guān)鍵碼得到的哈希地址一旦產(chǎn)生了沖突，也就是說(shuō)，該地址已經(jīng)存放了數(shù)據(jù)元素。我們需要尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。常用的找空哈希地址方法有下列三種。

• ① 線性探測(cè)法
  H_i = ( Hash(key) + d_i ) % m
  其中，Hash(key)為哈希函數(shù)，m為哈希表長(zhǎng)度， d為增量序列1，2，…，m-1，且 = i 。
  設(shè)關(guān)鍵碼集為 {47，7，29，11，16，92，22，8，3}，哈希表表長(zhǎng)為11，Hash(key)=key % 11，用線性探測(cè)法處理沖突，構(gòu)造哈希表如下表所示：

47，7，11，16，92均是由哈希函數(shù)得到的沒(méi)有沖突的哈希地址，因而是直接存入的。Hash(29)=7，哈希地址上沖突，需尋找下一個(gè)空的哈希地址：
H₁ = ( Hash(29) + 1 ) % 11 = 8，哈希地址8為空，所以將29存入。
另外，22，8同樣在哈希地址上有沖突，也是由 找到空的哈希地址的；而Hash(3)=3，哈希地址上沖突，因?yàn)椋?br> H₁ = ( Hash(3) + 1 ) % 11 = 4，仍然沖突
H₂ = ( Hash(3) + 2 ) % 11 = 5，仍然沖突
H₃ = ( Hash(3) + 3 ) % 11 = 6，找到空的哈希地址，存入。
線性探測(cè)法可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞……因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來(lái)，大大降低了查找效率。為此，可采用二次探測(cè)法，或再哈希函數(shù)探測(cè)法，以改善“堆積”問(wèn)題。

• ② 二次探測(cè)法
  H_i = ( Hash(key) + d_i ) % m
  其中，Hash(key)為哈希函數(shù)，m為哈希表長(zhǎng)度， d為增量序列，，，，…，，且
  仍對(duì)前面例子的關(guān)鍵碼序列{47，7，29，11，16，92，22，8，3}，用二次探測(cè)法處理沖突，構(gòu)造哈希表如下表所示。

與關(guān)鍵碼尋找空的哈希地址只有3這個(gè)關(guān)鍵碼不同，Hash(3)=3，哈希地址上沖突，由[圖片上傳失敗...(image-c7d04d-1609756554547)]
H₁ = ( Hash(3) + ) % 11 = 4，仍然沖突
H₂ = ( Hash(3) - ) % 11 = 2，找到空的哈希地址，存入。

• ③ 再哈希法
  H_i = ( Hash(key) + i * ReHash(key) ) % m
  其中，Hash(key)，ReHash(key)是兩個(gè)哈希函數(shù)，m為哈希表長(zhǎng)度。
  再哈希法，先用第一個(gè)函數(shù)Hash(key)對(duì)關(guān)鍵碼計(jì)算哈希地址，一旦產(chǎn)生地址沖突，再用第二個(gè)函數(shù)ReHash(key)確定移動(dòng)的步長(zhǎng)因子，最后，通過(guò)步長(zhǎng)因子序列由探測(cè)函數(shù)尋找空的哈希地址。
  比如，Hash(key)=a時(shí)產(chǎn)生地址沖突，就計(jì)算ReHash(key)=b，則探測(cè)的地址序列為：
  H₁ = ( a + 1 *b ) % m，仍然沖突
  H₂ = ( a + 2 *b ) % m，仍然沖突
  H₃ = ( a + 3 *b ) % m，找到空的哈希地址，存入。

2、鏈地址法：

將哈希值相同的數(shù)據(jù)元素存放在一個(gè)鏈表中，在查找哈希表的過(guò)程中，當(dāng)查找到這個(gè)鏈表時(shí)，必須采用線性查找方法。這樣的好處是，不怕沖突多；缺點(diǎn)是降低了散列結(jié)構(gòu)的隨機(jī)存儲(chǔ)性能。本質(zhì)是用單鏈表結(jié)構(gòu)輔助散列結(jié)構(gòu)的不足。
鏈地址法又稱拉鏈法，設(shè)哈希函數(shù)得到的哈希地址域在區(qū)間[0，m-1]上，以每個(gè)哈希地址作為一個(gè)指針，指向一個(gè)鏈，即分配指針數(shù)組：
ElemType eptr[m]；
建立m個(gè)空鏈表，由哈希函數(shù)對(duì)關(guān)鍵碼轉(zhuǎn)換后，映射到同一哈希地址i的同義詞均加入eptr[i]指向的鏈表中。
對(duì)關(guān)鍵碼序列為 {47，7，29，11，16，92，22，8，3，50，37，89，94，10}，哈希函數(shù)為Hash(key)=key % 11，用拉鏈法處理沖突，建表下所示。

鏈地址法

3、建立一個(gè)公共溢出區(qū)

設(shè)哈希函數(shù)產(chǎn)生的哈希地址集為[0，m-1]，則分配兩個(gè)表：
一個(gè)基本表ElemType base_tbl[m]；每個(gè)單元只能存放一個(gè)元素。
一個(gè)溢出表ElemType over_tbl[k]；只要關(guān)鍵碼對(duì)應(yīng)的哈希地址在基本表上產(chǎn)生沖突，則所有這樣的元素一律存入該表中。
查找時(shí)，對(duì)給定值kx通過(guò)哈希函數(shù)計(jì)算出哈希地址i，先與基本表的base_tbl[i]單元比較，若相等，查找成功；否則，再到溢出表中進(jìn)行查找。