【正文】 另外 ， 2 8同樣在哈希地址上有沖突 ， 也是由 H1找到空的哈希地址的； 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 52 而 Hash(3)=3， 哈希地址上沖突 ， 由 H1=(Hash(3)+1) mod 11=4 仍然沖突； H2=(Hash(3)+2) mod 11=5 仍然沖突； H3=(Hash(3)+3) mod 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)題 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 53 2. 二次 探測(cè)法 Hi=(Hash(key)177。 di) mod m 其中： Hash(key)為哈希函數(shù) m為哈希表長(zhǎng)度 ， m要求是某個(gè) 4k+3的質(zhì)數(shù) (k是整數(shù) ) di 為增量序列 12， 12， 22， 22， …… ， q2， q2且q≤ (1/2)*(m1) 【 例 】 關(guān)鍵碼集為 {47， 7， 29， 11， 16， 92， 22，8， 3}， 用二次探測(cè)法處理沖突 ， 建表如下： 0 1 2 3 4 5 6 7 8 9 10 11 22 3 47 92 16 7 29 8 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 54 對(duì)關(guān)鍵碼尋找空的哈希地址只有 3這個(gè)關(guān)鍵碼與上例不同 ， Hash(3)=3， 哈希地址上沖突 ， 由 H1=(Hash(3)+12) mod 11=4 仍然沖突； H2=(Hash(3)12) mod 11=2 找到空的哈希地址 ，存入 。 3. 雙哈希函數(shù)探測(cè)法 Hi=(Hash(key)+i*ReHash(key)) mod m (i=1，2， …… ， m1) 其中： Hash(key)， ReHash(key)是兩個(gè)哈希函數(shù) ， m為哈希表長(zhǎng)度 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 55 雙哈希函數(shù)探測(cè)法 ， 先用第一個(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+b) mod m， H2=(a+2b) mod m， …… ，Hm1=(a+(m1)b) mod m 二 . 拉鏈法 設(shè)哈希函數(shù)得到的哈希地址域在區(qū)間 [0， m1]上 ，以每個(gè)哈希地址作為一個(gè)指針 ， 指向一個(gè)鏈 ， 即分配指針數(shù)組 ElemType *eptr[m]；建立 m個(gè)空鏈表 ，由哈希函數(shù)對(duì)關(guān)鍵碼轉(zhuǎn)換后 ， 映射到同一哈希地址 i的同義詞均加入到 *eptr[i]指向的鏈表中 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 56 【 例 】 關(guān)鍵碼序列為 47,7,29,11,16,92,22,8,3,50,37,89, 94,21，哈希函數(shù)為 Hash(key)=key mod 11，建表如下圖 0 1 2 ^ 3 4 5 6 7 8 9 ^ 10 22 89 ^ 3 37 16 ^ 94 29 8 ^ 21 ^ 11 ^ 47 ^ 92 ^ 50 ^ 7 ^ 拉鏈法處理沖突時(shí)的哈希表 （向鏈表中插入元素均在表頭進(jìn)行） 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 57 【 算法 】 define m 11 int CreateHashTbl(NodeType **l_tbl,ElemType *eptr) { /* 建立哈希表 ， l_tbl 為指向 m個(gè)哈希地址對(duì)應(yīng)的鏈表指針數(shù)組基址 ， eptr為待放入哈希表的元素基址 ， 建表成功返回 1，否則 ， 返回 0 */ int finished。 InitLinkTbl(l_tbl)。 /* 初始化指向鏈表的指針數(shù)組 */ for(。eptrkey!=0。eptr++) { /* 待放入哈希表的元素表 ， 關(guān)鍵碼 0表示結(jié)束位置 */ finished=MovElemToHashTbl(eptr,linktbl,Hash(eptrkey))。 if(!finished) break。 } return finished。 } 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 58 InitLinkTbl(NodeType **l_tbl) {int i。 for(i=0。im。i++) *(l_tbl+i)=NULL。} int Hash(KeyType kx) /* 按關(guān)鍵碼得到哈希地址 */ { return (kx%m)。 } int MovElemToHashTbl(ElemType *e_addr,NodeType **l_tbl,int h_addr) { /* 待放入元素放入哈希表 ， e_addr為元素地址 ， l_tbl為指向 m個(gè)哈希地址對(duì)應(yīng)的鏈表指針數(shù)組基址 , h_addr為哈希地址 */ int status=0。 NodeType *q。 q=(NodeType *)malloc(sizeof(NodeType))。 if(q) { qelem=*e_addr。 qnptr=*(l_tbl+h_addr)。 *(l_tbl+h_addr)=q。 status=1。 } return status。 } 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 59 三 . 建立一個(gè)公共溢出區(qū) 設(shè)哈希函數(shù)產(chǎn)生的哈希地址集為 [0， m1]， 則分配兩個(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)行查找 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 60 哈希表的查找分析 哈希表的查找過(guò)程基本上和造表過(guò)程相同 。 一些關(guān)鍵碼可通過(guò)哈希函數(shù)轉(zhuǎn)換的地址直接找到 ， 另一些關(guān)鍵碼在哈希函數(shù)得到的地址上產(chǎn)生了沖突 ，需要按處理沖突的方法進(jìn)行查找 。 在介紹的三種處理沖突的方法中 ， 產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過(guò)程 。 所以 ， 對(duì)哈希表查找效率的量度 ， 依然用平均查找長(zhǎng)度來(lái)衡量 。 查找過(guò)程中 ， 關(guān)鍵碼的比較次數(shù) ， 取決于產(chǎn)生沖突的多少 ， 產(chǎn)生的沖突少 ， 查找效率就高 ， 產(chǎn)生的沖突多 ， 查找效率就低 。 因此 ， 影響產(chǎn)生沖突多少的因素 ， 也就是影響查找效率的因素 。 影響產(chǎn)生沖突多少有以下三個(gè)因素： 1. 哈希函數(shù)是否均勻； 2. 處理沖突的方法； 3. 哈希表的裝填因子 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 61 分析這三個(gè)因素，盡管哈希函數(shù)的“好壞”直接影響沖突產(chǎn)生的頻度，但一般情況下，我們總認(rèn)為所選的哈希函數(shù)是“均勻的”，因此，可不考慮哈希函數(shù)對(duì)平均查找長(zhǎng)度的影響。就線性探測(cè)法和二次探測(cè)法處理沖突的例子看，如 【 例 】 和【 例 】 相同的關(guān)鍵碼集合、同樣的哈希函數(shù)，但在數(shù)據(jù)元素查找等概率情況下，它們的平均查找長(zhǎng)度卻不同： 線性探測(cè)法的平均查找長(zhǎng)度ASL=(5 1+3 2+1 4)/9=5/3 二次探測(cè)法的平均查找長(zhǎng)度 ASL=(5 1+3 2+1 2)/9=13/9 哈希表的裝填因子定義為： α = 填入表中的元素個(gè)數(shù) 哈希表的長(zhǎng)度 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 62 α是哈希表裝滿程度的標(biāo)志因子 。 由于表長(zhǎng)是定值 ，α與 “ 填入表中的元素個(gè)數(shù) ” 成正比 ， 所以 ， α越大 ，填入表中的元素較多 ， 產(chǎn)生沖突的可能性就越大； α越小 ， 填入表中的元素較少 ， 產(chǎn)生沖突的可能性就越小 。 實(shí)際上 ， 哈希表的平均查找長(zhǎng)度是裝填因子 α的函數(shù) ，只是不同處理沖突的方法有不同的函數(shù) 。 以下給出幾種不同處理沖突方法的平均查找長(zhǎng)度： 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 63 處理沖突的方法 平均查找長(zhǎng)度 查找成功時(shí) 查找不成功時(shí) 線性探測(cè)法 二次探測(cè)法 與雙哈希法 拉鏈法 )1 11(21 ????nlS ))1(11(212????nlU)1ln (1 ?? ???nrS??? 11nrU21???ncS?? ??? eUnc 哈希方法存取速度快 ， 也較節(jié)省空間 ， 靜態(tài)查找 、 動(dòng)態(tài)查找均適用 ， 但由于存取是隨機(jī)的 ， 因此 ， 不便于順序查找 。