Hash表 構(gòu)建方法 編程技巧

1、散列（Hashing)存貯假定鍵值均是正整數(shù).散列存貯是通過對結(jié)點的鍵值做某種運算來確定具有該鍵值的結(jié)點的存放位置。設(shè)有線性表F=(k1,k2,kn-1)Tm，而結(jié)點ki的鍵值為Keyi，記F中所有結(jié)點的鍵值的集合為S. h(x)是從S到整數(shù)區(qū)間0,m-1上的一個一一對應(yīng)函數(shù)。對于F中的任一結(jié)點Ki，h(keyi)的唯一值與之對應(yīng)， Ki存放在數(shù)組Tm中的位置就由h(keyi)決定。1這種存貯線性表F的方法，稱為散列存貯。稱函數(shù)h(x)為散列函數(shù)（HASH函數(shù))。稱存放結(jié)點的數(shù)組T(m)為散列表(Hash表).設(shè)F是含有六個結(jié)點的線性表，其中K0=(9,e) ,k1=(12,b), k2=(2

2、0,e),K3=(26,a), k4=(34,d), k5=(48,f).若取散列函數(shù)h(x)=x mod 10，并使用能存放十個結(jié)點的數(shù)組T10作為Hash表，則下圖表示了F的散列存貯的狀況。201234567893如果我們想找到key4=34的結(jié)點K4，那么只要計算出34 mod 10=4就能在數(shù)組元素T4中找到它。出現(xiàn)h(keyi)=h(keyj),稱這種情況是沖突。散列存貯的兩個主要問題是：一是選取散列函數(shù)；二是選取解決沖突的辦法。4靜態(tài)散列方法散列方法在表項存儲位置與其關(guān)鍵碼之間建立一個確定的對應(yīng)函數(shù)關(guān)系Hash( )，使每個關(guān)鍵碼與結(jié)構(gòu)中一個唯一存儲位置相對應(yīng)： Address H

3、ash ( Rec.key )在搜索時, 先對表項的關(guān)鍵碼進行函數(shù)計算,把函數(shù)值當做表項的存儲位置, 在結(jié)構(gòu)中按此位置取表項比較。若關(guān)鍵碼相等, 則搜索成功。在存放表項時, 依相同函數(shù)計算存儲位置, 并按此位置存放。這種方法就是散列方法。5在散列方法中使用的轉(zhuǎn)換函數(shù)叫做散列函數(shù)。按此方法構(gòu)造出來的表或結(jié)構(gòu)就叫做散列表。使用散列方法進行搜索不必進行多次關(guān)鍵碼的比較, 搜索速度比較快, 可以直接到達或逼近具有此關(guān)鍵碼的表項的實際存放地址。散列函數(shù)是一個壓縮映象函數(shù)。關(guān)鍵碼集合比散列表地址集合大得多。因此有可能經(jīng)過散列函數(shù)的計算，把不同的關(guān)鍵碼映射到同一個散列地址上，這就產(chǎn)生了沖突。示例：有一組表項

4、，其關(guān)鍵碼分別是 12361, 07251, 03309, 30976 6 采用的散列函數(shù)是 hash(x) = x % 73 + 13420 其中，“%”是除法取余操作。則有：hash(12361) = hash(07250) = hash(03309) = hash(30976) = 13444。就是說, 對不同的關(guān)鍵碼, 通過散列函數(shù)的計算, 得到了同一散列地址。我們稱這些產(chǎn)生沖突的散列地址相同的不同關(guān)鍵碼為同義詞。由于關(guān)鍵碼集合比地址集合大得多, 沖突很難避免。所以對于散列方法, 需要討論以下兩個問題： 7構(gòu)造散列函數(shù)時的幾點要求： 散列函數(shù)應(yīng)是簡單的，能在較短的時間內(nèi)計 算出結(jié)果。

5、散列函數(shù)的定義域必須包括需要存儲的全部 關(guān)鍵碼, 如果散列表允許有 m 個地址時, 其 值域必須在 0 到 m-1 之間。 散列函數(shù) 對于給定的一個關(guān)鍵碼集合, 選擇一個計算簡單且地址分布比較均勻的散列函數(shù), 避免或盡量減少沖突； 擬訂解決沖突的方案。8一、開式尋址法解決沖突假定鍵值是大于零的整數(shù)，所選用的Hash函數(shù)是h(x),并用數(shù)組tm作為Hash表，這個表共有m個位置。91.建立Hash表的插入運算。為了把鍵值k存入Hash表，先計算出h(k)=i.如果ti 是一個空位置（即ti=0),那么把k存入ti,插入過程結(jié)束；如果ti不是空位置（即ti0),那么再判斷ti是否等于k，若ti=k

6、,則鍵值k已在Hash表中，插入過程結(jié)束；否則，ti已被另一個鍵值所占用（發(fā)生沖突），此時必須為k找另一個空位置，最簡單的辦法是進行線性探測，我們可使用下面的循環(huán)探測地址序列：10(i+1) mod m(i+2) mod m (i+m-1) mod m一旦找到一個空位置，就把k存入剛探測到的空位置上，插入過程結(jié)束；如果用完整個探測地址序列還沒有找到空位置，那么Hash表滿，插入失敗，過程結(jié)束。例Hash(x)=x%1011 Hash (1) = 1 Hash (4) = 4 Hash (11) = 1 Hash (31) = 1 Hash (20) = 0 Hash (7) = 7 Hash

7、(50) = 0 Hash (14) = 4設(shè)散列表 HT26, m = 26。采用線性探查法處理沖突, 則散列結(jié)果如圖所示。0 1 2 3 4 20 1 11 31 4 50 14 7 5 6 7 8 9 (1) (1) (2) (3) (1)(6) (3) (1)122.查找鍵值k首先計算出h(k)=i.如果ti=k,則查找成功，查找過程結(jié)束；如果ti不等于k,那么必須按照上面所給出的循環(huán)探測地址序列進行查找。查找過程一直進行到下面三種情況之一出現(xiàn)為止：（1）當前位置上的鍵值等于k，則查找成功。（2）找到一個空位置，則查找失敗。（3）用完循環(huán)探測地址序列還沒有找到k,則查找失敗。133.刪

8、除鍵值K.首先在Hash表tm上進行查找。如果查找成功，假定tj=k,那么應(yīng)把tj刪除。但是，我們不能把tj置成空，而只能標上已被刪除的標記，否則將會影響以后的查找。因此，在插入時，凡遇到標有刪除標記的位置都可以插入；而在查找時，凡遇到標有刪除標記的位置，還要繼續(xù)查下去。14 實現(xiàn)上面各種運算的程序。我們假定所使用的鍵值是大于零的整數(shù)，用0對Hash表tM進行初始化，用1作為刪除標記，所使用的Hash函數(shù)是h(x). 15#define M 100void makenull(t)int t ;int i; for(i=0;im;i+)ti=0; 16int insert1(t,k)int t

9、,k;int i,j;i=h(k);for(j=0;j0;j+);i=(i+j)%M; if (ti=0)ti=k;return(0);return(1);17 i=h(k);for(j=0;j0;j+); i=(i+j)%M; if (ti=0ti=k;return(0); Hash (32) = 10 Hash (75) = 9 Hash (63) = 8 Hash (48) = 4 Hash (94) = 6 Hash (25) = 3 Hash (36) = 3 Hash (18) =7 Hash (70) = 4 0 1 2 3 4 70 25 48 36 94 18 63 75 3

10、2 5 6 7 8 9 10(8) (1) (1)(6) (1) (1) (1) (1) (1)18 i=h(k)=10; /Hash (32) = 10 for(j=0;j0;j+); i=(i+j)%M; if (ti=0ti=k;return(0); j=0;jm=11&t(10+0) !=32&t(10+0) =0; i=(10+0)%11=10; if (t10=0t10=32;return(0); 0 1 2 3 4 32 5 6 7 8 9 10 (1)19 i=h(k);for(j=0;j0;j+); i=(i+j)%M; if (ti=0ti=k;return(0); Has

11、h (32) = 10 Hash (75) = 9 Hash (63) = 8 Hash (48) = 4 Hash (94) = 6 Hash (25) = 3 i=h(36)=3;for(j=0;j11&t3+0=25!=(k=36)/沖突j=1; t3+1=48!=(k=36)；j=2 &t3+2=0; i=3+2=5; if (t5=0t5=36;return(0); 0 1 2 3 4 25 48 36 94 63 75 32 5 6 7 8 9 10 (1) (1) (3) (1) (1) (1) (1)20int search1(t, k)int t ,k;int i ,j;i

12、=h(k);for(j=0;jm&t(i+j)%M!=k&t(i+j)%M!=0;j+); i=(i+j)%M;if(ti=k)return(i);return(-1);21 i =h(k);for(j=0;jm&t(i+j)%M!=k&t(i+j)%M!=0;j+); i=(i+j)%M;if(ti=k)return(i); i =h(36)=3;for(j=0;j t3+0=25 !=(k=36)!=0;j+); j =1; t3+1=48 !=(k=36)!=0;j+);j =2;t3+2!=36 =(k=36); i=(3+2)%11=5;if(t5=36)return(5); 0 1

13、 2 3 4 70 25 48 36 94 18 63 75 32 5 6 7 8 9 10 (3)22int deletel(t,k)int t ,k;int i,j; i=h(k);for(j=0;jm &t(i+j)%M!=k&t(i+j)%M!=0;j+);i=(i+j)%M;if(ti=k)ti= -1;return(0);return(1);23Collision resolution by chainingWe can take the hash table itself as an array of pointers to the record,that is,as an ar

14、ray of linked lists.It is traditional to refer to the linked lists from hash as chains and call this method collision resolution by chaining.把來自hash表中的一些鏈表叫做鏈，稱該方法為拉鏈法。241.Advantage of chaining The first,is that considerable space may be saved. Since the hash table is a continuous array, enough spac

15、e must be set aside at compilation time to avoid overflow.If the hash table contains only pointers to the records,pointers that require only one word each,the size of the hash table may be reduced by a large factor and will become small relative to the space available for the record,or for other use

16、s. 25The second advantage of keeping only pointers in the hash table is that it allows simple and efficient collision handing.We need only add a link field to each record, and organize all the records with a single hash address as linked list. Finally, deletion becomes a quick and easy task in chain

17、ed hush table.2. Disadvantage of chainingAll the links require space.26二、用拉鏈法解決沖突 這種解決沖突的處理方法是把具有相同hash地址的鍵值都存放在同一個鏈表中，有m個hash地址就有m個鏈表，同時用數(shù)組tm存放各個鏈表的頭指針。27示例：給出一組表項關(guān)鍵碼 10, 15,12, 17, 19, 14, 24 。散列函數(shù)為：Hash (x) x %5用它計算可得： Hash (24) = 4 Hash (19) = 4 Hash (14) = 4 Hash (10) = 0 Hash (12) = 2 Hash (15

18、) = 0 Hash (17) = 2散列表為 T0T4。2801234 10 15 12 17 24 19 1429#include #define M 100struct node int key; struct node *link; ;typedef struct node NODE;NODE *tM;30 void makenull2(t) NODE *t; int i; for (i=0;ikey=k) return; else*p=*q; *q=(*q)-link; 3201234 10 15 12 17 24 19 14 search2(t,17 ,p,q) *p=NULL;*

19、q=th(k); while(* q!=NULL) if (* q)-key=k) return; else* p=* q; * q=(* q)-link; *p=NULL;*q=th(17)=t2；/鏈表頭指針; while(* q!=) if (* q)-key=12=17) else* p=* q; * q=(* q)-link;while(* q!=) if (* q)-key=17=17) return; / *p ; *q ;表示鏈表中的非首結(jié)點*q*p3301234 10 15 12 17 24 19 14 search2(t,12 ,p,q) *p=NULL;*q=th(k);

20、 while(* q!=NULL) if (* q)-key=k) return; else* p=* q; * q=(* q)-link; *p=NULL;*q=th(17)=t2；/鏈表頭指針; while(* q!=) if (* q)-key=12=12) return; / *p= ; *q ;表示鏈表中第一個結(jié)點*q3401234 10 15 12 17 24 19 14 search2(t,22 ,p,q) *p=NULL;*q=th(k); while(* q!=NULL) if (* q)-key=k) return; else* p=* q; * q=(* q)-link;

21、 *p=NULL;*q=th(17)=t2；/鏈表頭指針; while(* q!=) if (* q)-key=12=22) else*p=*q; *q=(*q)-link;while(* q!=) if (* q)-key=17=22) else*p=*q; *q=(*q)-link;*q*p3501234 10 15 12 17 24 19 14 while(* q!=) if (* q)-key=17=22) else*p=*q; *q=(*q)-link= ;while(* q!=);/跳出循環(huán)，結(jié)束/ *p ; *q = ;表示鏈表中查不到所需結(jié)點*q*p36查找結(jié)果小結(jié)四種返回情況

22、 1. *p= ; *q = ;表示鏈表中無結(jié)點 2. *p ; *q = ;表示鏈表中查不到所需結(jié)點; 3. *p= ； *q ;表示查到的是鏈表中第一個結(jié)點 4. *p ; *q ;表示查到的是鏈表中的非首結(jié)點37 int insert2(t,k) NODE *t ; int k; NODE *p,*q,*r; search2(t,k,&p,&q); if (*q)=NULL) r=(NODE *)malloc(sizeof(NODE); r-key=k; r-link=NULL; if(*p)=NULL) th(k)=r; else (*p)-link=r; return(0); els

23、e return(1);3801234 10 15 12 17 24 19 14 insert2(t,22) search2(t,22,&p,&q); /2鏈表中查不到所需結(jié)點，返回 *p ; *q = ; if (*q)=NULL) r=(NODE* )malloc(sizeof(NODE); r-key=k=22; r-link=NULL; if(*p)=NULL) else (*p)-link=r; return(0); *q 22 *pr39 17 01234 10 15 12 24 19 14 22 r40 int delete2(t,k) NODE *t ; int k; NODE

24、 *p,*q; search2(t,k,&p,&q); if (*q)!=NULL) if (*p)=NULL) th(k)=(*q)-link; else (*p)-link=(*q)-link; free(q); return(0); return(1); 41 17 01234 10 15 12 24 19 14 22 delete2(t,k) search2(t,k,&p,&q); if (q!=NULL)if (*p)=NULL) th(k)=(*q)-link; else(* p)-link=(*q)-link; free(*q); return(0); delete2(t,12) search2(t, 12,&p,&q); /返回