【文章內(nèi)容簡(jiǎn)介】 中存在著關(guān)鍵字與給定值相等的記錄 ， 則一定存儲(chǔ)在 H(key)位置上 ， 從而不需要比較既可按地址直接存取記錄 。 這種對(duì)應(yīng)關(guān)系 H被稱為散列函數(shù) ， 或哈希函數(shù) ， 利用這種方法建立的表稱為散列表或哈希表 。 散列表 當(dāng)關(guān)鍵字集合很大時(shí) ， 關(guān)鍵字值不同的記錄通過散列函數(shù)的計(jì)算 ， 可能會(huì)映象到散列表的同一地址上 ， 即 K1≠K 2， 但H(K1)=H(K2)， 這種現(xiàn)象稱為沖突 ， 此時(shí)稱 K1與 K2為同義詞 。 ? 構(gòu)造散列表主要包括以下兩方面的內(nèi)容： 構(gòu)造散列表主要包括以下兩方面的內(nèi)容： ? 如何構(gòu)造哈希函數(shù)； ? 如何處理沖突 。 散列函數(shù)的構(gòu)造方法 ? 下面介紹構(gòu)造哈希函數(shù)常用的五種方法 。 ? 1. 數(shù)字分析法： 如果事先知道關(guān)鍵字集合 ， 并且每個(gè)關(guān)鍵字的位數(shù)比散列表的地址位數(shù)多時(shí) ， 可以從關(guān)鍵字中選出分布較均勻的若干位 ， 構(gòu)成散列地址 。 ? 2. 平方取中法： 當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時(shí) ， 可以先求出關(guān)鍵字的平方值 ， 然后按需要取平方值的中間幾位作為散列地址 。 取值的位數(shù)由表長(zhǎng)決定 。 ? 3. 分段疊加法： 這種方法是按散列表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾部分 (最后一部分可以較短 )， 然后將這幾部分相加 ， 舍棄最高進(jìn)位后的結(jié)果 ， 既是該關(guān)鍵字的散列地址 。 具體方法有折疊法與移位法 。 ? 4. 除留余數(shù)法： 取關(guān)鍵字被某個(gè)不大于表長(zhǎng) m的素?cái)?shù) p除后 ， 所得余數(shù)為散列地址 。 ? 5. 偽隨機(jī)數(shù)法： 采用一個(gè)偽隨機(jī)函數(shù)作散列函數(shù) ， 即 H(key)= random(key)。 ? 在實(shí)際應(yīng)用中 ， 應(yīng)根據(jù)具體情況 ， 采用不同的方法 。 在構(gòu)造散列函數(shù)時(shí) ， 通常應(yīng)考慮以下五個(gè)因素：計(jì)算散列函數(shù)所需的時(shí)間 ， 關(guān)鍵字的長(zhǎng)度 ， 散列表的大小 ， 關(guān)鍵字的分布情況 ， 查找記錄的頻率 。 處理沖突的方法 ? 常用的解決沖突方法有以下四種 : ? ： 這種方法也稱再散列法 ， 其基本思想是：當(dāng)關(guān)鍵字 key的散列地址 p=H(key)出現(xiàn)沖突時(shí) ， 以 p為基礎(chǔ) ， 產(chǎn)生另一個(gè)散列地址 p1， 如果 p1仍然沖突 ， 再以 p1為基礎(chǔ) ， 產(chǎn)生另一個(gè)散列地址 p2， ?? ， 直到找出一個(gè)不沖突的散列地址 pi， 將相應(yīng)記錄存入其中 。 可以有以下三種增量序列的取值方法：線性探測(cè)再散列 ， 二次探測(cè)再散列 ， 偽隨機(jī)探測(cè)再散列 。 ? ： 這種方法是同時(shí)構(gòu)造多個(gè)不同的散列函數(shù)； H i ＝ RH i (key)， i ＝ l， 2， ? ， k 當(dāng)散列地址 H 1 = RH l (key) 發(fā)生沖突時(shí) ， 再計(jì)算 H 2 = RH 2 (key)， ?? 直到?jīng)]有沖突發(fā)生 。 這種方法不易產(chǎn)生聚集 ， 但增加了計(jì)算時(shí)間 。 ? ： 這種方法的基本思想是將所有關(guān)鍵字為同義詞的記錄分別鏈成一個(gè)線性鏈表 (單鏈表 )， 稱為同義詞鏈 。 ? ： 這種方法的基本思想是將散列表分為基本表和溢出表兩部分 ， 凡是與基本表發(fā)生沖突的元素一律填入溢出表 。 處理沖突的方法 圖 鏈地址法處理沖突的散列表 例 83 已知一組關(guān)鍵字 (32， 40， 36，53， 16， 46， 71， 27， 42， 24，49， 64)， 散列表長(zhǎng)度為 13，散列函數(shù)為： H(key)＝ key MOD 13， 則用鏈地址法處理沖突 ， 如圖 。 散列表的查找 ? 散列表的查找過程與散列表的構(gòu)造過程是一致的 。 ? 當(dāng)查找關(guān)鍵字為 key的記錄時(shí) ， 首先計(jì)算 p0 = hash(key)。 如果存儲(chǔ)單元 p0為空 ， 則待查找記錄不存在；如果存儲(chǔ)單元 p0中記錄的關(guān)鍵字為key， 則找到待查找記錄；如果存儲(chǔ)單元 p0中元素的關(guān)鍵字不等于 key， 則重復(fù)執(zhí)行下列解決沖突的過程：按處理沖突的方法 ， 找出下一個(gè)散列地址 p1， 如果存儲(chǔ)單元 p1為空 ， 則所查找記錄不存在：如果存儲(chǔ)單元 p1中元素的關(guān)鍵字為 key， 則找到待查找記錄 ， 否則繼續(xù)查找 p2， …… 直至找到關(guān)鍵字為 key的記錄 ， 或直至找遍整個(gè)表 ， 沒有找到 ， 則待查找記錄不存在 。 ? 下面以線性探測(cè)再散列為例 ， 給出散列表的查找算法 (算法 )。 define m /* 散列表的長(zhǎng)度 */ typedef int KeyType。 typedef struct { KeyType key。 … }RecordType。 typedef RecordType HashTable[m]。 散列表的查找 下面以線性探測(cè)再散列為例 ， 給出散列表的查找算法 (算法 )。 define m /* 散列表的長(zhǎng)度 */ typedef int KeyType。 typedef struct { KeyType key。 ? }RecordType。 typedef RecordType HashTable[m]。 int HashSearch(HashTable HT, KeyType key) { p0=hash(key)。 if(HT[P0].key = = NULL) return(－ 1)； else { for(i =1。 i= m－ 1。 i++) { pi=(p0 + i) MOD m。 if(HT[pi] == NULL) return(－ 1)。 else if(HT[pi] == key) return(pi)。 } return (－ 1 )。 } } 散列技術(shù)性能分析 ? 評(píng)價(jià)查找性能的 “ 優(yōu)劣 ” 時(shí) ， 首先要考慮其產(chǎn)生沖突的頻率是多少 。 散列技術(shù)中影響關(guān)鍵字比較次數(shù)的因素有三個(gè)：散列函數(shù)的構(gòu)造方法 、 處理沖突的方法以及散列表的裝填因子 。 ? 散列表的裝填因子的定義如下： α 可描述散列表的裝滿程度。顯然， α 越小，發(fā)生沖突的可能性越小，而 α 越大，發(fā)生沖突的可能性也越大。 散列技術(shù)性能分析 (2) 散列技術(shù)性能分析 (3) 參見教材：例 84 上 機(jī) 實(shí) 習(xí) ? 實(shí)習(xí) 1 ? 實(shí)習(xí) 2 ? 實(shí)習(xí) 3 實(shí)習(xí) 1 ? 二叉排序樹的建立 。 ? 題目：設(shè)計(jì)算法 ， 將一串讀入的整數(shù)構(gòu)成一棵二叉排序樹 。 typedef struct node { int key。 /*關(guān)鍵字 */ int other。 /*其他數(shù)據(jù)項(xiàng) */ struct node *lchild,*rchild /*左 、 右孩子指針 */ }bstnode。 void inorder(bstnode *t) /*中序遍歷二叉樹 */ { if(t!=null) { inorder(tlchild)。 printf(%4d,tkey)。 inorder(trchild)。 printf(%4d,tkey)。 } }/*inorder*/ 實(shí)習(xí) 1（ 2） bstnode *insertbst(bstnode *t,bstnode*s) { bstnode *f,*p。 p=t。 while(p!=null) { f=p。 if(skey==pkey) return t。 if(skeypkey) p=plchild。 else p=prchild。 } if(t==null) return s。 if(skeyfkey) flchild=s。 else frchlid=s。 return t。 }/* insertbst*/ 實(shí)習(xí) 1（ 3） bstnode *creatord() /*返回二叉排序樹 */ { bstnode *t,*s。 int key,data。 t=null。 scanf(%d,amp。key)。 while (key!=0) { s=(bstnode*)malloc(sizeof(bstnode))。 skey=key。 slchild=null。 srchild=null。 scanf(%d,amp。data)。 sother=data。 t=insertbst(t,s)。 scanf(%d,amp。key)。 } return t。 }/*creatord*/ main() { bstnode *root。 root=creatord()。 inorder(root)。 }/*main*/ 實(shí)習(xí) 2 ? 掌握散列表對(duì)矩陣的散列存儲(chǔ)方法 。 ? 題目： 假設(shè)有一個(gè) 100*100的稀疏矩陣 ， 其中非零元占 1%， 試設(shè)計(jì)散列表對(duì)稀疏矩陣進(jìn)行散列存儲(chǔ) ， 散列函數(shù)由稀疏矩陣中非零元素所在的行 、 列構(gòu)成 ， 且散列表中存儲(chǔ)的每個(gè)元素均為一個(gè)三元組 (i,j,val)。 ? 提示： 根據(jù)題目給定的 100*100的稀疏矩陣中 ， 非零元素個(gè)數(shù)應(yīng)在 100*100*1%=100以內(nèi) ， 且每個(gè)元素均以一個(gè)三元組 (i,j,val)形式存儲(chǔ) 。 對(duì)這 100個(gè)元素進(jìn)行散列存儲(chǔ) ， 首先要開辟一個(gè)長(zhǎng)度為 m的一維數(shù)組 HT[0..m－ 1]， 因?yàn)檠b填因子 α 為 ， 則m=100/=125左右 ， 因此 ， 取 m =127；然后根據(jù)非零元素在數(shù)組中的行 i、 列 j位置 ， 確定散列函數(shù) H[i,j]=(3*i+2*j)%127；為了解決沖突 ， 可采用線性探測(cè)法 hk=(hk1+1)%127 1≤ k≤ 127, h0=h(i,j)。 實(shí)習(xí) 2（ 2） define smax 12。 typedef struct { int i,j。 /*行號(hào)，列號(hào) */ char v。 /*元素值 */ }node node HT[smax]。 /*散列表 HT*/ create(node[] HT) { int k,h,i,j。 char val。 for(h=0。h12。h++) { HT[h].i=0。 HT[h].j=0。 HT[h].v=/。 } 實(shí)習(xí) 2（ 3） for(k=0。k12。k++) { scanf(%d,%d,%c,amp。i,amp。j,amp。val)。 h=(3*i+2*j)%12。 while(HT[h].v!=/) h=(h+1)%12。 HT[h].i=i。 HT[h].j=j。 HT[h].v=val。 } }/*create*/ main() { node []H。 int k,h,i,j。 char val。 create(H) for(h=0。h12。h++) printf(%d,%d,%c,H[h] .i,H[h].j,H[h].v)； }/*main*/ 實(shí)習(xí) 3 ? 掌握在散列表中查找下標(biāo)為 i， j 的非零元素的算法 。 ? 題目：設(shè)計(jì)一個(gè)從上題得到的散列表 HT中檢索下標(biāo)為 i， j的非零元素的算法 。 datatype find(node []HT, int i,intj) { int h。 h=(3*i+2*j)%127。 /*根據(jù)行 、 列值 ， 求此元素的散列地址 */ while(((HT[h].i!=i)||(HT[h].j!=j)) amp。amp。 Ht[h].v!=0)) h=(h+1)%127。 /*利用線性探測(cè)法檢索下標(biāo)為 i,j的元素 ， 若 HT[h].i=i,且 HT[h].j=j, 則 HT[h].v