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