Hash表 构建方法 编程技巧.ppt

《Hash表 构建方法 编程技巧.ppt》由会员分享，可在线阅读，更多相关《Hash表 构建方法 编程技巧.ppt（47页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、散列（散列（Hashing)存贮存贮假定键值均是正整数.散列存贮是通过对结点的键值做某种运算来确定具有该键值的结点的存放位置。设有线性表F=(k1,k2,kn-1)和数组Tm，而结点ki的键值为Keyi，记F中所有结点的键值的集合为S.h(x)是从S到整数区间0,m-1上的一个一一对应函数。对于F中的任一结点Ki，都有一个h(keyi)的唯一值与之对应，Ki存放在数组Tm中的位置就由h(keyi)决定。这种存贮线性表F的方法，称为散列存贮散列存贮。称函数h(x)为散列函数（散列函数（HASH函数函数)。称存放结点的数组T(m)为散列表散列表(Hash表表).设F是含有六个结点的线性表，其中K0

2、=(9,e),k1=(12,b),k2=(20,e),K3=(26,a),k4=(34,d),k5=(48,f).若取散列函数h(x)=x mod 10，并使用能存放十个结点的数组T10作为Hash表，则下图表示了F的散列存贮的状况。012345678920E12b34d26a48f9C如果我们想找到key4=34的结点K4，那么只要计算出34 mod 10=4就能在数组元素T4中找到它。出现h(keyi)=h(keyj),称这种情况是冲突冲突。散列存贮的两个主要问题是：一是选取散列函数；二是选取解决冲突的办法。静态散列方法静态散列方法n n散列方法在散列方法在表项存储位置表项存储位置与与其关

3、键码其关键码之间建之间建立一个立一个确定的对应函数关系确定的对应函数关系Hash()，使每个使每个关键码与结构中一个唯一存储位置相对应：关键码与结构中一个唯一存储位置相对应：Address Hash(Rec.key)n n在搜索时在搜索时,先对表项的关键码进行函数计算先对表项的关键码进行函数计算,把函数值当做表项的存储位置把函数值当做表项的存储位置,在结构中按在结构中按此位置取表项比较。若关键码相等此位置取表项比较。若关键码相等,则搜索则搜索成功。在存放表项时成功。在存放表项时,依相同函数计算存储依相同函数计算存储位置位置,并按此位置存放。这种方法就是散列并按此位置存放。这种方法就是散列方法。

4、方法。n n在散列方法中使用的转换函数叫做在散列方法中使用的转换函数叫做散列函数散列函数。按此方法构造出来的表或结构就叫做按此方法构造出来的表或结构就叫做散列表散列表。n n使用散列方法进行搜索不必进行多次关键码使用散列方法进行搜索不必进行多次关键码的比较的比较,搜索速度比较快搜索速度比较快,可以直接到达或逼可以直接到达或逼近具有此关键码的表项的实际存放地址。近具有此关键码的表项的实际存放地址。n n散列函数是一个压缩映象函数散列函数是一个压缩映象函数。关键码集合。关键码集合比散列表地址集合大得多。因此有可能经过比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同散列函

5、数的计算，把不同的关键码映射到同一个散列地址上，这就产生了一个散列地址上，这就产生了冲突冲突。n n示例：有一组表项，其关键码分别是示例：有一组表项，其关键码分别是 12361,07251,03309,30976 采用的散列函数是采用的散列函数是采用的散列函数是采用的散列函数是 hashhash(x x)=)=x x%73+13420%73+13420 其中，其中，其中，其中，“%”“%”是除法取余操作。是除法取余操作。是除法取余操作。是除法取余操作。则有：则有：则有：则有：hashhash(12361)=(12361)=hashhash(07250)=(07250)=hashhash(033

6、09)=(03309)=hashhash(30976)=13444(30976)=13444。就是说就是说就是说就是说,对不同的关键码对不同的关键码对不同的关键码对不同的关键码,通通通通过散列函数的计算过散列函数的计算过散列函数的计算过散列函数的计算,得到了同一散列地址。得到了同一散列地址。得到了同一散列地址。得到了同一散列地址。我们称这我们称这我们称这我们称这些产生冲突的散列地址相同的不同关键码为些产生冲突的散列地址相同的不同关键码为些产生冲突的散列地址相同的不同关键码为些产生冲突的散列地址相同的不同关键码为同义词同义词同义词同义词。n n由于关键码集合比地址集合大得多由于关键码集合比地址集

7、合大得多由于关键码集合比地址集合大得多由于关键码集合比地址集合大得多,冲突很难避免。冲突很难避免。冲突很难避免。冲突很难避免。所以对于散列方法所以对于散列方法所以对于散列方法所以对于散列方法,需要讨论以下两个问题：需要讨论以下两个问题：需要讨论以下两个问题：需要讨论以下两个问题：构造散列函数时的几点要求：构造散列函数时的几点要求：n n 散列函数应是简单的，能在较短的时间内计散列函数应是简单的，能在较短的时间内计 算出结果。算出结果。n n 散列函数的定义域必须包括需要存储的全部散列函数的定义域必须包括需要存储的全部 关键码关键码,如果散列表允许有如果散列表允许有 m 个地址时个地址时,其其

8、值域必须在值域必须在 0 到到 m-1 之间。之间。散列函数散列函数uu 对于给定的一个关键码集合对于给定的一个关键码集合,选择一个计选择一个计算简单且地址分布比较均匀的散列函数算简单且地址分布比较均匀的散列函数,避避免或尽量减少冲突；免或尽量减少冲突；uu 拟订解决冲突的方案。拟订解决冲突的方案。一、开式寻址法解决冲突一、开式寻址法解决冲突假定键值是大于零的整数，所选用的Hash函数是h(x),并用数组tm作为Hash表，这个表共有m个位置。1.建立建立Hash表的插入运算。表的插入运算。为了把键值k存入Hash表，先计算出h(k)=i.如果ti 是一个空位置（即ti=0),那么把k存入ti

9、,插入过程结束；如果ti不是空位置（即ti0),那么再判断ti是否等于k，若ti=k,则键值k已在Hash表中，插入过程结束；否则，ti已被另一个键值所占用（发生冲突），此时必须为k找另一个空位置，最简单的办法是进行线性探测，我们可使用下面的循环探测地址序列：(i+1)mod m(i+2)mod m(i+m-1)mod m一旦找到一个空位置，就把k存入刚探测到的空位置上，插入过程结束；如果用完整个探测地址序列还没有找到空位置，那么Hash表满，插入失败，过程结束。例Hash(x)=x%10 n n Hash(1)=1 Hash(4)=4 Hash(11)=1 Hash(31)=1 Hash(2

10、0)=0 Hash(7)=7 Hash(50)=0 Hash(14)=4n n设散列表设散列表 HT26,m=26。采用采用线性探查法线性探查法处理冲突处理冲突,则散列结果如图所示。则散列结果如图所示。0 1 2 3 40 1 2 3 4 20 1 11 31 4 50 14 7 5 6 7 8 9 5 6 7 8 9(1)(1)(2)(3)(1)(1)(1)(2)(3)(1)(6)(3)(1)(6)(3)(1)2.查找键值查找键值k首先计算出h(k)=i.如果ti=k,则查找成功，查找过程结束；如果ti不等于k,那么必须按照上面所给出的循环探测地址序列进行查找。查找过程一直进行到下面三种情况

11、之一出现为止：（1）当前位置上的键值等于k，则查找成功。（2）找到一个空位置，则查找失败。（3）用完循环探测地址序列还没有找到k,则查找失败。3.删除键值删除键值K.首先在Hash表tm上进行查找。如果查找成功，假定tj=k,那么应把tj删除。但是，我们不能把tj置成空，而只能标上已被删除的标记，否则将会影响以后的查找。因此，在插入时，凡遇到标有删除标记的位置都可以插入；而在查找时，凡遇到标有删除标记的位置，还要继续查下去。实现上面各种运算的程序。我们假定所使用的键值是大于零的整数，用0对Hash表tM进行初始化，用1作为删除标记，所使用的Hash函数是h(x).#define M 100vo

12、id makenull(t)int t;int i;for(i=0;im;i+)ti=0;int insert1(t,k)int t,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);i=h(k);for(j=0;j0;j+);i=(i+j)%M;if(ti=0ti=k;return(0);Hash Hash(32)=10 (32)=10 HashHash(75)=9 (75)=9 HashHash(63)=8 (63)=8 HashHash(48)=4 (48)=4 HashHash(94)=

13、6 (94)=6 HashHash(25)=3(25)=3 HashHash(3636)=)=3 HashHash(18)=7 (18)=7 HashHash(7070)=)=4 4 0 1 2 3 40 1 2 3 4 70 25 48 36 94 18 63 75 32 5 6 7 8 9 105 6 7 8 9 10(8)(1)(1)(8)(1)(1)(6)(1)(1)(1)(1)(6)(1)(1)(1)(1)(1)(1)i=h(k)=10;/Hash Hash(32)=10(32)=10 for(j=0;j0;j+);i=(i+j)%M;if(ti=0ti=k;return(0);j=

14、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 40 1 2 3 4 32 5 6 7 8 9 105 6 7 8 9 10 (1)(1)i=h(k);for(j=0;j0;j+);i=(i+j)%M;if(ti=0ti=k;return(0);Hash Hash(32)=10 (32)=10 HashHash(75)=9 (75)=9 HashHash(63)=8 (63)=8 HashHash(48)=4 (48)=4 HashHash(94)=6 (94)=6 HashHash(2

15、5)=3(25)=3 i=h(36)=3;=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 40 1 2 3 4 25 48 36 94 63 75 32 5 6 7 8 9 105 6 7 8 9 10 (1)(1)(1)(1)(3)(1)(1)(1)(1)(3)(1)(1)(1)(1)int search1(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

16、+);i=(i+j)%M;if(ti=k)return(i);return(-1);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 2 3 40 1 2 3 4 70 25 48 36 94 18 63 75 32 5 6 7 8 9 105 6

17、7 8 9 10 (3)(3)int 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);Collision resolution by chainingWe can take the hash table itself as an array of pointers to the record,that is,as an array of linked lists.It is traditional to re

18、fer to the linked lists from hash as chains and call this method collision resolution by chaining.把来自hash表中的一些链表叫做链链，称该方法为拉链法拉链法。1.Advantage of chaining The first,is that considerable space may be saved.Since the hash table is a continuous array,enough space must be set aside at compilation time to

19、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 uses.The second advantage of keeping only poin

20、ters 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 chained hush table.2.Disadvantage of chainingAll the l

21、inks require space.二、用拉链法解决冲突二、用拉链法解决冲突 这种解决冲突的处理方法是把具有相同hash地址的键值都存放在同一个链表中，有m个hash地址就有m个链表，同时用数组tm存放各个链表的头指针。n n示例：给出一组表项关键码示例：给出一组表项关键码 n n 10,15,12,17,19,14,24。n n散列函数为：散列函数为：Hash(x)x%5n n用它计算可得：用它计算可得：Hash(24)=4 Hash(19)=4 Hash(14)=4 Hash(10)=0 Hash(12)=2 Hash(15)=0 Hash(17)=2n n散列表为散列表为 T0T4。0

22、 01 12 23 34 4 10 15 12 17 24 19 14#include#define M 100struct node int key;struct node*link;typedef struct node NODE;NODE*tM;void makenull2(t)NODE*t;int i;for(i=0;ikey=k)return;else*p=*q;*q=(*q)-link;0 01 12 23 34 4 10 15 12 17 24 19 14 search2(t,17,p,q)*p=NULL;*q=th(k);while(*q!=NULL)if(*q)-key=k)

23、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 ;表示链表中的非首结点表示链表中的非首结点*q*p0 01 12 23 34 4 10 15 12 17 24 19 14 search2(t,12,p,q)*p=NULL;*q=th(k);while(*q!=NULL)if(*q)-key=k)return;else*p=*q;*q

24、=(*q)-link;*p=NULL;*q=th(17)=t2；/链表头指针链表头指针;while(*q!=)if(*q)-key=12=12)return;/*p=;*q ;表示表示链表中第一个结点链表中第一个结点*q0 01 12 23 34 4 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;*p=NULL;*q=th(17)=t2；/链表头指针链表头指针;while(*q!=)if(*q)-key=12=22)

25、else*p=*q;*q=(*q)-link;while(*q!=)if(*q)-key=17=22)else*p=*q;*q=(*q)-link;*q*p0 01 12 23 34 4 10 15 12 17 24 19 14 while(*q!=)if(*q)-key=17=22)else*p=*q;*q=(*q)-link=;while(*q!=);/跳出循环，结束跳出循环，结束/*p ;*q=;表示链表中查不到所需结点表示链表中查不到所需结点*q*p查找结果小结查找结果小结四种返回情况四种返回情况 1.*p=;*q=;表示链表中无结点表示链表中无结点 2.*p ;*q=;表示链表中查不

26、到所需结点表示链表中查不到所需结点;3.*p=；*q ;表示表示查到的是链表中第一个结点查到的是链表中第一个结点 4.*p ;*q ;表示查到的是链表中的非首结点表示查到的是链表中的非首结点 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);else return(1);0 01 12 23 34 4 10 15

27、 12 17 24 19 14 insert2(t,22)search2(t,22,&p,&q);/2链表中查不到所需结点，链表中查不到所需结点，返回返回*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 *pr 17 0 01 12 23 34 4 10 15 12 24 19 14 22 r int delete2(t,k)NODE*t;int k;NODE*p,*q;search2(t,k,&p,&q);if(

28、*q)!=NULL)if(*p)=NULL)th(k)=(*q)-link;else(*p)-link=(*q)-link;free(q);return(0);return(1);17 0 01 12 23 34 4 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);/返回返回*p=；*q ;首结点首结点if(*q

29、)!=NULL)if(*(p)=NULL)th(k)=(*q)-link=&17;/取地址取地址 free(*q);return(0);*q*qlink 17 0 01 12 23 34 4 10 15 24 19 14 22 *qlink 17 0 01 12 23 34 4 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,17)search2(t,17,

30、&p,&q);/返回返回*p ;*q ;非首结点非首结点if(*q)!=NULL)if(*p)=NULL)else(*p)-link=(*q)-link=&22;/取地址取地址 free(*q);return(0);*p*q*qlink0 01 12 23 34 4 10 15 12 24 19 14 22 *p*qlink 17 0 01 12 23 34 4 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,22)search2(t,22,&p,&q);/返回返回*p ;*q ;非首结点非首结点if(*q)!=NULL)if(*p)=NULL)else(*p)-link=(*q)-link=;free(*q);return(0);*p*q*qlink 17 0 01 12 23 34 4 10 15 12 24 19 14*p*qlink