索引结构与散列技术.ppt

2019/7/20,1,第11章 索引结构与散列技术,2019/7/20,2,第11章 索引结构与散列技术,查找的基本概念 索引结构 散列技术 习题,2019/7/20,3,查找的基本概念,查找：给定值k，在n个记录中查找一个其关键字等于给定值的记录。若存在这样一个记录，则查找成功；否则查找失败。 关键字：数据元素中某个数据项的值，用以标识一个数据元素。 主关键字：可唯一地标识一个数据元素的关键字。 次关键字：用以识别若干记录的关键字。 使用基于主关键字的查找，查找结果应是唯一的。,2019/7/20,4,线性表的查找 顺序查找（线性查找） 查找过程：从表的一端开始查找，顺序用各记录的关键字与给定值x进行比较，若找到与其值相等的元素，则查找成功，给出该记录在表中的位置；否则，若直到最后一个记录仍未找到关键字与x相等的对象，则查找失败。 线性表可以是顺序存储结构或链式存储结构，可以是有序表或无序表。 二分查找（折半查找） 线性表必须是顺序存储结构，并且是有序表。具体查找方法在第12章中介绍。,2019/7/20,5,顺序查找算法 typedef struct keytype key; /关键字 datatype other; / 其他域 table; table Rn+1; int SEQSEARCH(table R , keytype k) / 在R中从后向前顺序查找关键字为k的结点 / 查找成功，函数返回向量下标，失败返回1 int i; R0.key=k; / R0作为监视哨使用 i=n; / 从表尾开始向前扫描 while (Ri.key!=k) i-; if (i=0) return(1); /若i等于0，则是监视哨本身的比较使循环结束 else return i; / SEQSEARCH,2019/7/20,6,算法分析 表中原始关键字： 26 5 37 1 61 11 59 15 48 19 输入希望查找的关键字值： k=37 R0.key=37 第一次查找：R10.key= 19 ，不等于k，继续查找 第二次查找：R 9.key= 48 ，不等于k ，继续查找 第三次查找：R 8.key= 15，不等于k，继续查找 第四次查找：R 7.key= 59 ，不等于k，继续查找 第五次查找：R 6.key= 11 ，不等于k ，继续查找 第六次查找：R 5.key= 61 ，不等于k ，继续查找 第七次查找：R 4.key= 1 ，不等于k ，继续查找 第八次查找：R 3.key= 37，等于k，查找成功 查找结果：要查的数据在表中的3号位置。,2019/7/20,7,输入希望查找的关键字值： k=25 R0.key=25 第1次查找：R10.key= 19 ，不等于k，继续查找 第2次查找：R 9.key= 48 ，不等于k ，继续查找 第3次查找：R 8.key= 15，不等于k，继续查找 第4次查找：R 7.key= 59 ，不等于k，继续查找 第5次查找：R 6.key= 11 ，不等于k ，继续查找 第6次查找：R 5.key= 61 ，不等于k ，继续查找 第7次查找：R 4.key= 1 ，不等于k ，继续查找 第8次查找：R 3.key= 37 ，不等于k ，继续查找 第9次查找：R 2.key= 5 ，不等于k ，继续查找 第10次查找：R 1.key= 26 ，不等于k ，继续查找 第11次查找：R 0.key= 25 ，等于k ，查找失败,2019/7/20,8,顺序查找的平均查找长度,设查找第 i 个元素的概率为 pi，查找到第 i 个元素所需比较次数为 ci，则查找成功的平均查找长度:,在顺序查找情况下，ci = n-i +1, i = 1, , n，因此,在等概率情况下，pi = 1/n, i = 1,2, , n。,2019/7/20,9,11.1 索引结构,索引结构包括两部分：索引表和数据表 索引表指示结点与其存储位置之间的关系，每个索引项包括关键字和地址。 数据表存储结点信息。 11.1.1 线性索引 线性索引：索引表为线性表 稠密索引：每个索引项对应数据表中的一个记录 稀疏索引：每个索引项对应数据表中的一组记录,2019/7/20,10,若索引表是顺序存储结构并且是有序表，对索引表可以采用顺序查找或折半查找。 分块查找 分块查找也称索引顺序查找。进行分块查找时，除数据表本身以外，尚需建立一个“索引表”。,2019/7/20,11,数据表有序或者分块有序。“分块有序”是指第i+1个子表中所有记录的关键字值均大于第i个子表的，而块内无序。索引表存放每块中最大的记录的关键字和块的起始地址，索引表按关键字值有序。 若块的长度不等长，在索引表中还需存放块的长度或块的终端地址。 分块查找需分两步进行，即先使用顺序查找或折半查找算法确定待查记录所在的块，然后在块内使用顺序查找算法查找所需的记录。 分块查找算法： typedef int keytype; typedef struct keytype key; /块的最大关键字 int start,end; /块的起、终点 IDtable; /索引表结点类型,2019/7/20,12,typedef struct keytype key; /记录的关键字项 datatype other; /记录的其他数据项 table; /数据表结点类型 int BLKSERCH(table R,IDtable ID,keytype k,int bn) /R为数据表，ID为索引表，k为所要查找的关键字，bn为索引表长度 int i,j; IDbn.key=k; i=0; while(kIDi.key) i+; /从前向后顺序查找索引表 if(i=bn) printf(“查找不到”); return (-1); /在索引表中查找不到 else j=IDi.start; while( jIDi.end ) j=-1；/在块内查找不到 return j; ,2019/7/20,13,11.1.2 倒排表 针对记录的主关键字建立主索引，次关键字建立次索引。主索引指示所有记录，次索引值是具有相同属性的记录。 先通过搜索次索引确定该记录的主关键字，再通过搜索主索引确定记录的存放地址。如图11-3 11.1.3 多级索引 若索引表很大，可以建立多级索引表，索引表中有一级索引、二级索引、 如图11-4,2019/7/20,14,11.2 散列技术,hash表的查找采用计算寻址的方式进行查找，查找效率与比较次数无关或关系较小，所以查找的效率较高。 11.2.1 散列表的概念 构造hash表：以结点的关键字k为自变量，通过一个确定的函数关系f，计算出对应的hash函数值f(k)，把这个值解释为结点的存储地址（hash地址），将结点存入f(k)所指的存储位置上。 查找hash表：根据给定值k，计算hash函数值f(k),得到hash地址，然后在指定的存储位置上取所查找的记录。 用散列法存储的线性表叫散列表或哈希表。 通常散列表的存储空间是一个一维数组，数组的长度m应大于结点的个数n。装填因子=n/m。通常0.65 0.9， 越小，产生冲突的可能性就越小。,2019/7/20,15,冲突：对于两个不同的关键字，得到相同的hash地址，即key1key2，而f(key1)=f(key2),这种现象称为冲突。一般情况下，冲突不可避免，但选择合适的hash函数可以减少冲突的发生，而且还要采取一种解决冲突的方法。 例：关键字序列: at,as,be,can,cat,for,face,force hash函数： H(key)=key0-a （key0存放关键字的第一个字母） 例如关键字at、as的hash地址都是0。 H(at)=0、H(as)=0 产生冲突,2019/7/20,16,11.2.2 散列函数的构造,构造hash函数的原则： 运算尽可能简单 能使一组关键字的hash地址均匀分布在整个地址空间上，从而减少冲突。 常用的构造hash函数的方法，可以采用数字选择法、平方取中法、折叠法、除留余数法、基数转换法、随机数法等。,2019/7/20,17,散列地址1：取第4、6、7位 散列地址2：取第4、6位与第7、8位之和并舍去进位,2019/7/20,18,平方取中法 先通过关键字的平方值扩大差别，然后，再取中间的几位或其组合作为散列地址。 例如： 关键字集合(0100,0110,1010,1001,0111) 的平方结果是 (0010000,0012100,1020100,1002001,0012321) 若表长为1000，则可取中间三位作为散列地址集是 (100,121,201,020,123),2019/7/20,19,折叠法 若关键字位数较多，也可将关键字分割成位数相同的几段（最后一段的位数可以不同），段的长度取决于散列表的地址位数，然后将各段的叠加和（舍去进位）作为散列地址。折叠法又分移位叠加和边界叠加两种。移位叠加是将各段的最低位对齐，然后相加；边界叠加则是两个相邻的段沿边界来回折叠，然后对齐相加。 例如关键字key=58242324169，散列表长度为1000，则将此关键字分成三位一段，两种叠加结果如下： 移位叠加 边界叠加 582 582 423 324 241 241 + 69 + 96 1315 1243 H(key)=315 H(key)=243,2019/7/20,20,除留余数法 基本思想： 选择适当的正整数p，用p去除关键字，取所得余数作为散列地址，即： H(key)=key % p 一般地选p为小于或等于散列表长度m的某个最大素数比较好。 例如： m=8, 16, 32, 64, 128, 256, 512, 1024 p=7, 13, 31, 61, 127, 251, 503, 1019,2019/7/20,21,基数转换法 基本思想： 把关键字看成是另一个进制上的数后，再把它转换成原来进制上的数，取其中的若干位作为散列地址。一般取大于原来基数的数作为转换的基数，并且两个基数要互素。 例如： 给定一个十进制数的关键字为(210485)10，我们把它看成以15为基数的十五进制(210485)15，再把它转换为十进制： (210485)15=2155+1154+0153+4152+815+5=(771932)10 假设散列表长度10000，则可取低四位1932作为散列地址。,2019/7/20,22,随机数法 选择一个随机函数，取关键字的随机函数值为它的散列地址，即 H(key)=random(key) 其中：random为随机函数。,2019/7/20,23,11.2.3 解决冲突的方法,选择合适的散列函数可以减少冲突，但不能避免冲突，还需要具有解决冲突的方法。 开放地址法 当发生冲突时，使用某种方法在散列表中形成一个探查序列，沿着此序列逐个单元进行查找，直到找到一个空的单元时将新结点放入。 探查序列包括： 线性探查法 二次探查法 随机探查法,选择不同的开放地址法，散列地址的“堆积”程度不同。,2019/7/20,24,线性探查法,线性探查法的基本思想是：散列表的长度为m，将散列表看成是一个环形表，若发生冲突的单元地址为d，则依次探查d+1,d+2,m1,0,1,d1，直到找到一个空单元为止。开放地址公式为： di= (d+i) % m (1im1) 其中d=H (key)。 已知一组关键字集(26,36,41,38,44,15,68,12,06,51,25)，用线性探查法解决冲突，试构造这组关键字的散列表。 关键字个数n=11，取=0.75，散列表长度m=n/=15。散列函数为：H(key)%13,2019/7/20,25,二次探查法,二次探查法的探查序列依次是：12,12,22,22,等，也就是说，发生冲突时，将同义词来回散列在第一个地址d=H(key)的两端。由此可知，发生冲突时，求下一个开放地址的公式为： d2i1=(d+i2) % m d2i=(di2) % m (1i(m1)/2),2019/7/20,26,随机探查法,采用一个随机数作为地址位移计算下一个单元地址，即求下一个开放地址的公式为： di=(d+Ri) % m (1im1) 其中：d=H(key)，R1,R2，,Rm-1是1,2,，m1的一个随机排列。,2019/7/20,27,拉链法,将所有关键字为同义词的结点链接到同一个单链表中。若选定的散列函数的值域为0到m1，则可将散列表定义为一个由m个头指针组成的指针数组HTPm，凡是散列地址为i的结点，均插入到以HTPi为头指针的单链表中。 拉链法不会产生散列地址的“堆积”现象。 例：已知一组有11个关键字的集(26,36,41,38,44,15,68,12,06,51,25)，用拉链法解决冲突，试构造这组关键字的散列表。 取，m=n/=15，取p=13 散列表为HT13 散列函数为：H(key)%13,2019/7/20,28,散列表的查找算法,利用线性探查法解决冲突的查找和插入算法如下： # define nil 0 / nil为空结点标记 # define m 18 / 这时假设表长m为18 typedef struct / 散列表结点结构 ke