影響哈希查找效率的一個(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è)法
Hi = ( Hash(key) + di ) % 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)造哈希表如下表所示：
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 11 | 22 | 47 | 92 | 16 | 3 | 7 | 29 | 8 |
47，7赦役，11麻敌，16，92均是由哈希函數(shù)得到的沒(méi)有沖突的哈希地址掂摔，因而是直接存入的术羔。Hash(29)=7赢赊，哈希地址上沖突，需尋找下一個(gè)空的哈希地址：
H1 = ( Hash(29) + 1 ) % 11 = 8级历，哈希地址8為空释移，所以將29存入。
另外寥殖，22玩讳，8同樣在哈希地址上有沖突，也是由 找到空的哈希地址的嚼贡；而Hash(3)=3熏纯，哈希地址上沖突，因?yàn)椋?br>
H1 = ( Hash(3) + 1 ) % 11 = 4编曼，仍然沖突
H2 = ( Hash(3) + 2 ) % 11 = 5豆巨，仍然沖突
H3 = ( 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è)法
Hi = ( Hash(key) + di ) % m
其中串塑，Hash(key)為哈希函數(shù)，m為哈希表長(zhǎng)度北苟， d為增量序列桩匪，
，
友鼻，
傻昙，…，
彩扔，
且
仍對(duì)前面例子的關(guān)鍵碼序列{47妆档，7，29虫碉，11贾惦，16，92，22纤虽，8乳绕，3}绞惦，用二次探測(cè)法處理沖突逼纸，構(gòu)造哈希表如下表所示。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 11 | 22 | 3 | 92 | 16 | 7 | 29 | 8 |
與關(guān)鍵碼尋找空的哈希地址只有3這個(gè)關(guān)鍵碼不同济蝉，Hash(3)=3杰刽，哈希地址上沖突，由[圖片上傳失敗...(image-c7d04d-1609756554547)]
H1 = ( Hash(3) + ) % 11 = 4王滤，仍然沖突
H2 = ( Hash(3) - ) % 11 = 2贺嫂，找到空的哈希地址，存入雁乡。
- ③ 再哈希法
Hi = ( 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è)的地址序列為：
H1 = ( a + 1 *b ) % m，仍然沖突
H2 = ( a + 2 *b ) % m伙判，仍然沖突
H3 = ( 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)行查找声离。
