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=(9,e),k1=(12,b),k

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

3、Hash(Rec.key)在搜索时,先对表项的关键码进行函数计算,把函数值当做表项的存储位置,在结构中按此位置取表项比较。若关键码相等,则搜索成功。在存放表项时,依相同函数计算存储位置,并按此位置存放。这种方法就是散列方法。,在散列方法中使用的转换函数叫做散列函数。按此方法构造出来的表或结构就叫做散列表。使用散列方法进行搜索不必进行多次关键码的比较,搜索速度比较快,可以直接到达或逼近具有此关键码的表项的实际存放地址。散列函数是一个压缩映象函数。关键码集合比散列表地址集合大得多。因此有可能经过散列函数的计算，把不同的关键码映射到同一个散列地址上，这就产生了冲突。示例：有一组表项，其关键码分别是

4、12361,07251,03309,30976,采用的散列函数是 hash(x)=x%73+13420 其中，“%”是除法取余操作。则有：hash(12361)=hash(07250)=hash(03309)=hash(30976)=13444。就是说,对不同的关键码,通过散列函数的计算,得到了同一散列地址。我们称这些产生冲突的散列地址相同的不同关键码为同义词。由于关键码集合比地址集合大得多,冲突很难避免。所以对于散列方法,需要讨论以下两个问题：,构造散列函数时的几点要求：散列函数应是简单的，能在较短的时间内计 算出结果。散列函数的定义域必须包括需要存储的全部 关键码,如果散列表允许有 m 个

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

6、突），此时必须为k找另一个空位置，最简单的办法是进行线性探测，我们可使用下面的循环探测地址序列：,(i+1)mod m(i+2)mod m(i+m-1)mod m一旦找到一个空位置，就把k存入刚探测到的空位置上，插入过程结束；如果用完整个探测地址序列还没有找到空位置，那么Hash表满，插入失败，过程结束。例Hash(x)=x%10,Hash(1)=1 Hash(4)=4 Hash(11)=1 Hash(31)=1 Hash(20)=0 Hash(7)=7 Hash(50)=0 Hash(14)=4设散列表 HT26,m=26。采用线性探查法处理冲突,则散列结果如图所示。,0 1 2 3 4,2

7、0 1 11 31 4,50 14 7,5 6 7 8 9,(1)(1)(2)(3)(1),(6)(3)(1),2.查找键值k首先计算出h(k)=i.如果ti=k,则查找成功，查找过程结束；如果ti不等于k,那么必须按照上面所给出的循环探测地址序列进行查找。查找过程一直进行到下面三种情况之一出现为止：（1）当前位置上的键值等于k，则查找成功。（2）找到一个空位置，则查找失败。（3）用完循环探测地址序列还没有找到k,则查找失败。,3.删除键值K.首先在Hash表tm上进行查找。如果查找成功，假定tj=k,那么应把tj删除。但是，我们不能把tj置成空，而只能标上已被删除的标记，否则将会影响以后的查

8、找。因此，在插入时，凡遇到标有删除标记的位置都可以插入；而在查找时，凡遇到标有删除标记的位置，还要继续查下去。,实现上面各种运算的程序。我们假定所使用的键值是大于零的整数，用0对Hash表tM进行初始化，用1作为删除标记，所使用的Hash函数是h(x).,#define M 100void 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=

9、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 32,5 6 7 8 9 10,(8)(1)(1),(6)(1)(1)(1)(1)(1),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,

10、0 1 2 3 4,32,5 6 7 8 9 10,(1),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 i=h(36)=3;for(j=0;j11,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),int search1(t,k)int t,k;int i,j;i=h(k);for(j=0;jm,i=h(k);for

11、(j=0;jm,0 1 2 3 4,70 25 48,36 94 18 63 75 32,5 6 7 8 9 10,(3),int deletel(t,k)int t,k;int i,j;i=h(k);for(j=0;jm,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 refer to the linked lists f

12、rom 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 avoid overflow.If the hash t

13、able 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 pointers in the hash table is t

14、hat 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 links require space.,二、用拉链法解

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

16、link;typedef struct node NODE;NODE*tM;,void makenull2(t)NODE*t;int i;for(i=0;im;i+)ti=NULL;,void search2(t,k,p,q)NODE*t;int k;NODE*p,*q;*p=NULL;*q=th(k);while(*q!=NULL)if(*q)-key=k)return;else*p=*q;*q=(*q)-link;,01234,10,15,12,17,24,19,14,search2(t,17,p,q)*p=NULL;*q=th(k);while(*q!=NULL)if(*q)-key=k

17、)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,*p,01234,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=(*q)-link;*p=NULL;*q=t

18、h(17)=t2；/链表头指针;while(*q!=)if(*q)-key=12=12)return;/*p=;*q;表示链表中第一个结点,*q,01234,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)else*p=*q;*q=(*q)-link;while(*q!=)if(*q)-key=17=22)e

19、lse*p=*q;*q=(*q)-link;,*q,*p,01234,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=;表示链表中查不到所需结点;3.*p=；*q;表示查到的是链表中第一个结点 4.*p;*q;表示查到的是链表中的非首结点,int insert2(t,k)NODE*t;int k;NODE*p,*q,*r;se

20、arch2(t,k,01234,10,15,12,17,24,19,14,insert2(t,22)search2(t,22,*q,22,*p,r,17,01234,10,15,12,24,19,14,22,r,int delete2(t,k)NODE*t;int k;NODE*p,*q;search2(t,k,17,01234,10,15,12,24,19,14,22,delete2(t,k)search2(t,k,*q,*qlink,17,01234,10,15,24,19,14,22,*qlink,17,01234,10,15,12,24,19,14,22,delete2(t,k)search2(t,k,*p,*q,*qlink,01234,10,15,12,24,19,14,22,*p,*qlink,17,01234,10,15,12,24,19,14,22,delete2(t,k)search2(t,k,*p,*q,*qlink,17,01234,10,15,12,24,19,14,*p,*qlink,