数据结构课件chp.ppt

《数据结构课件chp.ppt》由会员分享，可在线阅读，更多相关《数据结构课件chp.ppt（50页珍藏版）》请在三一办公上搜索。

1、散列(Hash)静态散列,第八章 散列,散列(Hashing),在计算机科学中把字典当作一种抽象数据类型。在讨论字典抽象数据类型时，把字典定义为 对的集合。根据问题的不同，可以为名字和属性赋予不同的含义。,在现实中，经常遇到按给定的值进行查询的事例。为此，必须在开发相应软件时考虑在记录的存放位置和用以标识它的数据项(称为关键字)之间的对应关系，从而选择适当的数据结构，很方便地根据记录的关键字检索到对应记录的信息。,字典(Dictionary)的抽象数据类型,例如，在图书馆检索目录中，名字是书名，属性是索书号及作者等信息；在计算机活动文件表中，名字是文件名，属性是文件地址、大小等信息；而在编译程

2、序建立的变量表中，名字是变量标识符，属性是变量的属性、存放地址等信息。,字典的抽象数据类型const int DefaultSize=26;templateclass HashTable public:Dictionary(int size=DefaultSize);int IsIn(Name name);,Attribute*Find(Name name);void Insert(Name name,Attribute attr);void Remove(Name name);,在字典的所有操作中，最基本的只有3种：Find(搜索)Insert(插入)Remove(删除)在选择字典的表示时，

3、必须确保这几个操作的实现。,通常，用文件(表格)来表示实际的对象集合，用文件记录(表格的表项)来表示单个对象。这样，字典中的对将被存于记录(表项)中，通过表项的关键字(即对的名字)来标识该表项。表项的存放位置及其关键字之间的对应关系可以用一个二元组表示：(关键字key，表项位置指针addr)这个二元组构成搜索某一指定表项的索引项。考虑到搜索效率，可以用顺序表的方式组织字典，也可以用二叉搜索树或多路搜索树的方式组织字典，本章讨论一种搜索效率很高的组织字典的方法，即散列结构。,静态散列方法,散列方法在表项的存储位置与它的关键字之间建立一个确定的对应函数关系Hash()，使每个关键字与结构中一个唯一

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

5、突(Collision)。示例：有一组表项，其关键字分别是 12361,07251,03309,30976 采用的散列函数是 hash(x)=x%73+13420 其中，“%”是除法取余操作。,则有：hash(12361)=hash(07250)=hash(03309)=hash(30976)=13444。就是说，对不同的关键字，通过散列函数的计算，得到了同一散列地址。我们称这些产生冲突的散列地址相同的不同关键字为同义词。由于关键字集合比地址集合大得多，冲突很难避免。所以对于散列方法，需要讨论以下两个问题：对于给定的一个关键字集合，选择一个计算简单且地址分布比较均匀的散列函数，避免或尽量减少冲

6、突；拟订解决冲突的方案。,构造散列函数时的几点要求：散列函数的定义域必须包括需要存储的全部关 键码，如果散列表允许有 m 个地址时,其值域 必须在 0 到 m-1 之间。散列函数计算出来的地址应能均匀分布在整个 地址空间中：若 key 是从关键字集合中随机抽 取的一个关键字，散列函数应能以同等概率取 0 到 m-1 中的每一个值。散列函数应是简单的，能在较短的时间内计算 出结果。,散列函数,直接定址法 此类函数取关键字的某个线性函数值作为散列地址：Hash(key)a*key+b a,b为常数 这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键字集合的大小相同。

7、示例：有一组关键字如下：942148,941269,940527,941630,941805,941558,942047,940001。散列函数为 Hash(key)=key-940000 则有,Hash(942148)=2148 Hash(941269)=1269 Hash(940527)=527 Hash(941630)=1630 Hash(941805)=1805 Hash(941558)=1558 Hash(942047)=2047 Hash(940001)=1 可以按计算出的地址存放记录。数字分析法 设有 n 个 d 位数，每一位可能有 r 种不同的符号。这 r 种不同的符号在各位上

8、出现的频率不一定相同，可能在某些位上分布均匀些；在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。,计算各位数字中符号分布的均匀度 k 的公式：其中，表示第 i 个符号在第 k 位上出现的次数，n/r 表示各种符号在 n 个数中均匀出现的期望值。计算出的 k 值越小，表明在该位(第k 位)各种符号分布得越均匀。若散列表地址范围有 3 位数字,取各关键字的位做为记录的散列地址。也可以把第，和第位相加，舍去进位位，变成一位数，与第，位合起来作为散列地址。还有其它方法。,9 4 2 1 4 8位，1=510.60 9 4 1 2 6 9位

9、，2=510.60 9 4 0 5 2 7位，3=110.60 9 4 1 6 3 0位，4=110.60 9 4 1 8 0 5位，5=110.60 9 4 1 5 5 8位，6=110.60 9 4 2 0 4 7 9 4 0 0 0 1,数字分析法仅适用于事先明确知道表中所有关键字每一位数值的分布情况，它完全依赖于关键字集合。如果换一个关键字集合，选择哪几位要重新决定。,除留余数法设散列表中允许的地址数为 m,取一个不大于 m，但最接近于或等于 m 的质数 p,或选取一 个不小于 20 的质因数的合数作为除数，利用以下公式把关键字转换成散列地址。散列函数为：hash(key)=key%p

10、 p m其中,“%”是整数除法取余的运算，要求这时的质数 p 不是接近2的幂。示例：有一个关键字 key=962148，散列表大小 m=25，即 HT25。取质数 p=23。散列函数 hash(key)=key%p。则散列地址为,hash(962148)=962148%23=12。可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是 0到 22，因此，从23到24这几个散列地址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。乘余取整法使用此方法时，先让关键字 key 乘上一个常数 A(0 A 1)，提取乘积的小数部分。然后，再用整数 n

11、乘以这个值，对结果向下取整，把它做为散列的地址。散列函数为：hash(key)=n*(A*key%1),其中,“A*key%1”表示取 A*key 小数部分:A*key%1=A*key-A*key 示例：设关键字 key=123456，n=10000，且 取 A=0.6180339，则hash(key)=10000*(0.6180339*key%1)因此有 hash(123456)=10000*(0.6180339*123456%1)=10000*(76300.0041151%1)=10000*0041151=41 此方法的优点是对 n 的选择不很关键。,平方取中法此方法在字典处理中使用十分广

12、泛。它先计算构成关键字的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定，所以对不同的标识符计算出的散列地址大多不相同，即使其中有些字符相同。在平方取中法中，一般取散列地址为 2 的某次幂。例如，若散列地址总数取为 m=2r，则对内码的平方数取中间的 r 位。如果 r=3，所取得的散列地址参看图的最右一列。,标识符 内码 内码的平方 散列地址A 01 01 001A1 0134 20420 042A9 0144 23420 342 B 02 4 004 DMAX 04150130 21

13、526443617100 443DMAX1 0415013034 5264473522151420 352 AMAX 01150130 135423617100 236AMAX1 0115013034 3454246522151420 652,标识符的八进制内码表示及其平方值,折叠法此方法把关键字自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。把这些部分的数据叠加起来，就可以得到具有该关键字的记录的散列地址。有两种叠加方法：移位法 把各部分的最后一位对齐相加；分界法 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址

14、。,示例：设给定的关键字为 key=23938587841，若存储空间限定 3 位,则划分结果为每段 3 位.上述关键字可划分为 4段：239 385 878 41把超出地址位数的最高位删去,仅保留最低的3位，做为可用的散列地址。,一般当关键字的位数很多，而且关键字每一位上数字的分布大致比较均匀时，可用这种方法得到散列地址。以上介绍了几种常用的散列函数。在实际工作中应根据关键字的特点，选用适当的方法。有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化”。在应用平方取中法时，若关键字不是整数而是字符串时，可以把每个字符串转换成整数。,处理冲突-溢出的方法,解决

15、冲突的方法又称为溢出处理技术。因为任一种散列函数也不能避免产生冲突，因此选择好的解决冲突溢出的方法十分重要。,为了减少冲突，对散列表加以改造。若设散列表 HT 有 m 个地址,将其改为 m 个桶。其桶号与散列地址一一对应,第 i(0 i m)个桶的桶号即为第 i 个散列地址。每个桶可存放 s 个表项,这些表项的关键字互为同义词。如果对两个不同表项的关键字用散列函数计算得到同一个散列地址，就产生了冲突，它们可以放在同一个桶内的不同位置。只有当桶内所有 s 个表项位置都放满表项后再加入表项才会产生溢出。通常桶的大小 s 取的比较小,因此在桶内大多采用顺序搜索。,闭散列是处理溢出的一种常用的方法,也

16、叫做开地址法。所有的桶都直接放在散列表数组中。因此每个桶只有一个表项(s=1)。若设散列表中各桶的编址为 0 到 m-1，当要加入一个表项 R2时,用它的关键字 R2.key，通过散列函数 hash(R2.key)的计算，得到它的存放桶号 j，但是在存放时发现这个桶已经被另一个表项 R1 占据了。这时不但发生了冲突，还必须处理溢出。为此，必须把 R2 存放到表中“下一个”空桶中。如果表未被装满，则在允许的范围内必定还有空桶。,(1)线性探查法(Linear Probing),假设给出一组表项，它们的关键字为 Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,E

17、derly。采用的散列函数是：取其第一个字母在字母表中的位置。Hash(x)=ord(x)-ord(A)/ord()是求字符内码的函数这样，可得 Hash(Burke)=1 Hash(Ekers)=4 Hash(Broad)=1 Hash(Blum)=1 Hash(Attlee)=0 Hash(Hecht)=7 Hash(Alton)=0 Hash(Ederly)=4,又设散列表为HT26，m=26。采用线性探查法处理溢出，则上述关键字在散列表中散列位置如图所示。括号内的数字表示找到空桶时的比较次数。,0 1 2 3 4,Attlee Burke Broad Blum Ekers,Alton

18、Ederly Hecht,5 6 7 8 9,(1)(1)(2)(3)(1),(6)(3)(1),需要搜索或加入一个表项时，使用散列函数计算桶号：H0=hash(key)一旦发生冲突，在表中顺次向后寻找“下一个”空桶 Hi 的公式为：Hi=(Hi-1+1)%m，i=1,2,m-1 即用以下的线性探查序列在表中寻找“下一个”空桶的桶号：H0+1,H0+2,m-1,0,1,2,H0-1 亦可写成 Hi=(H0+i)%m，i=1,2,m-1,当发生冲突时,探查下一个桶。当循环 m-1次后就会回到开始探查时的位置,说明待查关键字不在表内,而且表已满,不能再插入新关键字。用平均搜索长度ASL(Avera

19、gy Search Length)衡量散列方法的搜索性能。根据搜索成功与否，它又有搜索成功的平均搜索长度ASLsucc和搜索不成功的平均搜索长度ASLunsucc之分。搜索成功的平均搜索长度 ASLsucc 是指搜索到表中已有表项的平均探查次数。它是找到表中各个已有表项的探查次数的平均值。,搜索不成功的平均搜索长度 ASLunsucc 是指在表中搜索不到待查的表项，但找到插入位置的平均探查次数。它是表中所有可能散列到的位置上要插入新元素时为找到空桶的探查次数的平均值。在使用线性探查法对示例进行搜索时，搜索成功的平均搜索长度为：搜索不成功的平均搜索长度为：,线性探查方法容易产生“堆积”，不同探查

20、序列的关键字占据可用的空桶，为寻找某一关键字需要经历不同的探查序列，导致搜索时间增加。,(2)二次探查法(quadratic probing),为改善“堆积”问题，减少为完成搜索所需的平均探查次数，可使用二次探查法。通过某一个散列函数对表项的关键字 x 进行计算，得到桶号，它是一个非负整数。H0=hash(x)二次探查法在表中寻找“下一个”空桶的公式为：Hi=(Hi-1+i 2)%m,Hi=(Hi-1-i 2)%m,i=1,2,(m-1)/2式中的 m 是表的大小，它应是一个值为 4k+3 的质数，其中k是一个整数。这样的质数如 3,7,11,19,23,31,43,59,127,251,50

21、3,1019,。,下面给出求下一个大于参数表中所给正整数 N 的质数的算法。int NextPrime(int N)if(N%2=0)N+;/偶数不是质数 for(;!IsPrime(N);N+=2);/不是质数,继续求 return N;int IsPrime(int N)/判断N是否质数 for(int i=3;i*i=N;i+=2)if(N%i=0)return 0;/不是,返回0 return 1;/是,返回1,探查序列形如 H0,H0+1,H0-1,H0+4,H0-4,。在做(H0-i2)%m 的运算时，当 H0-i2 0 时，运算结果也是负数。实际算式可改为 if(j=(H0-i2

22、)%m)0)j+=m示例：给出一组关键字 Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly。散列函数为：Hash(x)ord(x)ord(A)用它计算可得 Hash(Burke)=1 Hash(Ekers)=4 Hash(Broad)=1 Hash(Blum)=1 Hash(Attlee)=0 Hash(Hecht)=7 Hash(Alton)=0 Hash(Ederly)=4,若设表的长度为TableSize=23，则利用二次探查法所得到的散列结果如图所示。,0 1 2 3 4 5,Blum Burke Broad Ekers Ederly,H

23、echt,6 7 8 9 10 11,Alton Attlee,(3)(1)(2)(1)(2),(1),17 18 19 20 21 22,(5)(3),利用二次探查法处理溢出,使用二次探查法处理溢出时的搜索成功的平均搜索长度为：搜索不成功的平均搜索长度为：,(3)双散列法,使用双散列方法时，需要两个散列函数。第一个散列函数 Hash()按表项的关键字 key 计算表项所在的桶号 H0=Hash(key)。一旦冲突，利用第二个散列函数 ReHash()计算该表项到达“下一个”桶的移位量。它的取值与 key 的值有关，要求它的取值应当是小于地址空间大小 TableSize，且与 TableSiz

24、e 互质的正整数。若设表的长度为 m=TableSize，则在表中寻找“下一个”桶的公式为：,j=H0=Hash(key)，p=ReHash(key)；j=(j+p)%m；p是小于m且与m互质的整数利用双散列法，按一定的距离，跳跃式地寻找“下一个”桶，减少了“堆积”的机会。双散列法的探查序列也可写成：Hi=(H0+i*ReHash(key)%m，i=1,2,m-1最多经过m-1次探查，它会遍历表中所有位置，回到H0 位置。,示例：给出一组表项关键字 22,41,53,46,30,13,01,67。散列函数为：Hash(x)(3x)%11。散列表为 HT0.10，m=11。因此，再散列函数为 R

25、eHash(x)=(7x)%10+1。Hi=(Hi-1+(7x)%10+1)%11,i=1,2,H0(22)=0 H0(41)=2 H0(53)=5 H0(46)=6 H0(30)=2 冲突 H1=(2+1)=3 H0(13)=6 冲突 H1=(6+2)=8 H0(01)=3 冲突 H1=(3+8)=0 H2=(0+8)=8 H3=(8+8)=5 H4=(5+8)=2 H5=(2+8)=10 H0(67)=3 冲突 H1=(3+10)=2 H2=(2+10)=1,搜索成功的平均搜索长度搜索不成功的平均搜索长度 每一散列位置的移位量有10种：1,2,10。先算出各种移位量的情况下找到下一个空位的

26、比较次数，求出平均值；再累加各个位置的平均比较次数，求出总平均值。,22 67 41 30 53 46 13 01,(1)(3)(1)(2)(1)(1)(2)(6),0 1 2 3 4 5 6 7 8 9 10,1 8 2 5 3 4 6 7,Rehash()的取法很多。例如，当m是质数时，可定义 ReHash(key)=key%(m-2)+1 ReHash(key)=key/m%(m-2)+1当 m 是 2 的方幂时，ReHash(key)可取从 0 到m-1 中的任意一个奇数。,处理溢出的开散列方法 链地址法,开散列方法首先对关键字集合用某一个散列函数计算它们的存放位置。若设散列表地址空间

27、的所有位置是从0到m-1，则关键字集合中的所有关键字被划分为m个子集，具有相同地址的关键字归于同一子集。我们称同一子集中的关键字互为同义词。每一个子集称为一个桶。通常各个桶中的表项通过一个单链表链接起来，称之为同义词子表。所有桶号相同的表项都链接在同一个同义词子表中，各链表的表头结点组成一个向量。,向量的元素个数与桶数一致。桶号为 i 的同义词子表的表头结点是向量中的第 i 个元素。示例：给出一组表项关键字 Burke,Ekers,Broad,Blum,Attlee,Alton,Hecht,Ederly。散列函数为：Hash(x)ord(x)ord(A)。用它计算可得：Hash(Burke)=

28、1 Hash(Ekers)=4 Hash(Broad)=1 Hash(Blum)=1 Hash(Attlee)=0 Hash(Hecht)=7 Hash(Alton)=0 Hash(Ederly)=4散列表为 HT0.25，m=26。,采用开散列法处理溢出，则上述关键字在散列表中的散列位置如图所示。,通常，每个桶中的同义词子表都很短，设有n 个关键字通过某一个散列函数，存放到散列表中的 m 个桶中。那么每一个桶中的同义词子表的平均长度为 n/m。这样，以搜索平均长度为 n/m 的同义词子表代替了搜索长度为 n 的顺序表，搜索速度快得多。,应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开

29、销。事实上，由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装填因子 0.5，而表项所占空间又比指针大得多，所以使用链地址法反而比开地址法节省存储空间。散列表分析 散列表是一种直接计算记录存放地址的方法，它在关键字与存储位置之间直接建立了映象。当选择的散列函数能够得到均匀的地址分布时，在搜索过程中可以不做多次探查。,由于很难避免冲突，就增加了搜索时间。冲突的出现，与散列函数的选取(地址分布是否均匀)，处理溢出的方法(是否产生堆积)有关。在实际应用中，在使用关键字进行散列时，如在用作关键字的许多标识符具有相同的前缀或后缀，或者是相同字符的不同排列的场合，不同的散列函数往往导致散

30、列表具有不同的搜索性能。下图给出一些实验结果，列出在采用不同的散列函数和不同的处理溢出的方法时，搜索关键字所需的对桶访问的平均次数。实验数据为 33575,24050,4909,3072,2241,930,762,500。,搜索关键字时所需对桶的平均访问次数,从图中可以看出，链地址法优于开地址法；在散列函数中，用除留余数法作散列函数优于其它类型的散列函数，最差的是折叠法。,当装填因子 较高时，选择的散列函数不同，散列表的搜索性能差别很大。在一般情况下多选用除留余数法，其中的除数在实用上应选择不含有20以下的质因数的质数。对散列表技术进行的实验评估表明，它具有很好的平均性能，优于一些传统的技术，

31、如平衡树。但散列表在最坏情况下性能很不好。如果对一 个有 n 个关键字的散列表执行一次搜索或插入操作，最坏情况下需要 O(n)的时间。Knuth对不同的溢出处理方法进行了概率分析。,若设 是散列表的装填因子：用地址分布均匀的散列函数Hash()计算桶号。Sn 是搜索一个随机选择的关键字 xi(1 i n)所需的关键字比较次数的期望值Un 是在长度为 m 的散列表中 n 个桶已装入表项的情况下，装入第 n+1 项所需执行的关键字比较次数期望值。前者称为在=n/m 时的搜索成功的平均搜索长度，后者称为在=n/m时的搜索不成功的平均搜索长度。,用不同的方法溢出处理冲突时散列表的平均搜索长度如图所示。,各种方法处理溢出时的平均搜索长度,