《九章节检索.ppt》由会员分享，可在线阅读，更多相关《九章节检索.ppt（138页珍藏版）》请在三一办公上搜索。
1、第九章 检索,任课教员：张 铭http:/,北京大学信息学院 版权所有，转载或翻印必究 Page 2,9.1 基本概念9.2 线性表的检索9.3 散列表的检索,北京大学信息学院 版权所有，转载或翻印必究 Page 3,基本概念,检索：在一组记录集合中找到关键码值等于给定值的某个记录，或者找到关键码值符合特定条件的某些记录的过程检索的效率非常重要尤其对于大数据量需要对数据进行特殊的存储处理,北京大学信息学院 版权所有，转载或翻印必究 Page 4,基本概念（续）,预排序排序算法本身比较费时只是预处理（在检索之前已经完成）建立索引检索时充分利用辅助索引信息牺牲一定的空间从而提高检索效率,北京大学信
2、息学院 版权所有，转载或翻印必究 Page 5,基本概念（续）,散列技术把数据组织到一个表中根据关键码的值来确定表中每个记录的位置缺点：不适合进行范围查询一般也不允许出现重复关键码当散列方法不适合于基于磁盘的应用程序时，我们可以选择B树方法,北京大学信息学院 版权所有，转载或翻印必究 Page 6,平均检索长度(ASL),关键码的比较检索运算的主要操作平均检索长度(Average Search Length)检索过程中对关键码需要执行的平均比较次数是衡量检索算法优劣的时间标准,北京大学信息学院 版权所有，转载或翻印必究 Page 7,平均检索长度,ASL是存储结构中对象总数n的函数，其定义为：
3、Pi 为检索第i个元素的概率Ci 为找到第i个元素所需的关键码值与给定值的比较次数,北京大学信息学院 版权所有，转载或翻印必究 Page 8,平均检索长度,假设线性表为（a,b,c）检索a、b、c的概率分别为0.4、0.1、0.5顺序检索算法的平均检索长度为0.41+0.12+0.53=2.1即平均需要2.1次给定值与表中关键码值的比较才能找到待查元素,北京大学信息学院 版权所有，转载或翻印必究 Page 9,衡量一个检索算法还需要考虑算法所需的存储量算法的复杂性.,北京大学信息学院 版权所有，转载或翻印必究 Page 10,9.1 基于线性表的检索,9.1.1 顺序检索9.1.2 二分检索9
4、.1.3 分块检索,北京大学信息学院 版权所有，转载或翻印必究 Page 11,9.1.1 顺序检索,针对线性表里的所有记录，逐个进行关键码和给定值的比较。若某个记录的关键码和给定值比较相等，则检索成功；否则检索失败(找遍了仍找不到)。存储：可以顺序、链接排序要求：无,北京大学信息学院 版权所有，转载或翻印必究 Page 12,顺序检索算法,/代码9-1 顺序检索的存储结构类型定义 template class Item public:Item(Type value):key(value)Type getKey()return key;/获取关键码值;void setKey(Type k)ke
5、y=k;/设置关键码private:Type key;/关键码域string other;/其它域;vector*dataList;,北京大学信息学院 版权所有，转载或翻印必究 Page 13,“监视哨”顺序检索算法,位置0用来做监视哨,位置1到length用来存储实际元素检索成功时返回元素位置，检索失败时统一返回0;/代码9-2 顺序检索算法 template int SeqSearch(vector*/返回元素位置,北京大学信息学院 版权所有，转载或翻印必究 Page 14,顺序检索性能分析,检索成功假设检索每个关键码是等概率的，Pi=1/n检索失败假设检索失败时都需要比较n+1次（设置了
6、一个监视哨）,北京大学信息学院 版权所有，转载或翻印必究 Page 15,顺序检索性能分析（续）,平均检索长度假设检索成功的概率为p，检索失败的概率为q=(1-p)，则平均检索长度为（n+1)/2 ASL(n+1)优缺点优点：插入元素可以直接加在表尾(1)缺点：检索时间太长(n),北京大学信息学院 版权所有，转载或翻印必究 Page 16,9.1.2 二分检索法,有序表：线性表中所有数据元素按关键码值递增（或递减）的次序排列 在有序表的存储表示下，检索可以用效率更高的二分检索法实现。,北京大学信息学院 版权所有，转载或翻印必究 Page 17,9.1.2 二分法检索,有序表中所有元素按关键码值
7、递增（或递减）的次序排列将表中任一元素dataListi的关键码值Key与给定值K比较，可根据三种比较结果区分出三种情况（以递增为例）：（1）Key=K，检索成功，dataListi即为待查元素（2）Key K，说明待查元素若在表中，且一定排在dataListi之前（3）Key K，说明待查元素若在表中，且一定排在dataListi之后因此，在一次比较之后，若没有找到待查元素（即情况1未出现），则可根据比较结果缩小进一步检索的区间,北京大学信息学院 版权所有，转载或翻印必究 Page 18,二分法检索算法,/代码9-3 二分检索算法 template int BinSearch(vector*
8、/检索失败，返回0,北京大学信息学院 版权所有，转载或翻印必究 Page 19,检索关键码18。low=1;high=9;K=18第一次：mid=5;array5=3518 high=4;(low=1)第二次：mid=2;array2=1718 low=3;(high=4)第三次：mid=3;array3=18=18 mid=3；return 8,二分法检索图示,北京大学信息学院 版权所有，转载或翻印必究 Page 20,二分法检索性能分析,最大检索长度为 失败的检索长度是 或,北京大学信息学院 版权所有，转载或翻印必究 Page 21,二分法检索性能分析（续）,成功的平均检索长度为：(n 5
9、0)优缺点优点：平均检索长度与最大检索长度相近，检索速度快缺点：要排序、顺序存储，不易更新(插/删),北京大学信息学院 版权所有，转载或翻印必究 Page 22,9.1.3 分块检索,顺序与二分法的折衷既有较快的检索又有较灵活的更改,北京大学信息学院 版权所有，转载或翻印必究 Page 23,分块检索思想,“按块有序”设线性表中共有n个数据元素，将表分成b块不需要均匀每一块可能不满每一块中的关键码不一定有序但前一块中的最大关键码必须小于后一块中的最小关键码,北京大学信息学院 版权所有，转载或翻印必究 Page 24,索引表各块中的最大关键码及各块起始位置可能还需要块中元素个数（每一块可能不满）
10、索引表是一个递增有序表由于表是分块有序的,北京大学信息学院 版权所有，转载或翻印必究 Page 25,分块检索分两个阶段,（1）确定待查元素所在的块（2）在块内检索待查的元素,北京大学信息学院 版权所有，转载或翻印必究 Page 26,分块检索索引顺序结构,索引表中每个索引项有两个域块内最大关键码块起始位置,北京大学信息学院 版权所有，转载或翻印必究 Page 27,分块检索性能分析,分块检索为两级检索先在索引表中确定待查元素所在的块；设在索引表中确定块号的时间开销是ASLb然后在块内检索待查的元素。在块中查找记录的时间开销为ASLwASL(n)=ASLb+ASLw,北京大学信息学院 版权所有
11、，转载或翻印必究 Page 28,分块检索性能分析(续1),索引表是按块内最大关键码有序的，且长度也不大，可以二分检索，也可以顺序检索各子表内各个记录不是按记录关键码有序，只能顺序检索,北京大学信息学院 版权所有，转载或翻印必究 Page 29,分块检索性能分析(续2),假设在索引表中用顺序检索，在块内也用顺序检索 当s=时，ASL取最小值，ASL=+1,北京大学信息学院 版权所有，转载或翻印必究 Page 30,分块检索性能分析(续3),当n=10,000时顺序检索5,000次二分法检索14次分块检索100次如果数据块（子表）存放在外存时，还会受到页块大小的制约此时往往以外存一个/读取的数据
12、（一页）作为一块,北京大学信息学院 版权所有，转载或翻印必究 Page 31,分块检索性能分析(续4),若采用二分法检索确定记录所在的子表，则检索成功时的平均检索长度为ASL=ASLb+ASLw log2(b+1)-1+(s+1)/2 log2(1+n/s)+s/2,北京大学信息学院 版权所有，转载或翻印必究 Page 32,分块检索的优缺点,优点：插入、删除相对较易没有大量记录移动缺点：增加一个辅助数组的存储空间初始线性表分块排序当大量插入/删除时，或结点分布不均匀时，速度下降,北京大学信息学院 版权所有，转载或翻印必究 Page 33,9.2 散列检索,基于关键码比较的检索 顺序检索，=,
13、!=二分法、树型,=,检索是直接面向用户的操作当问题规模n很大时，上述检索的时间效率可能使得用户无法忍受最理想的情况根据关键码值，直接找到记录的存储地址不需要把待查关键码与候选记录集合的某些记录进行逐个比较,北京大学信息学院 版权所有，转载或翻印必究 Page 34,例如，读取指定下标的数组元素根据数组的起始存储地址、以及数组下标值而直接计算出来的，所花费的时间是O(1)与数组元素个数的规模n无关受此启发，计算机科学家发明了散列方法散列是一种重要的存储方法也是一种常见的检索方法,北京大学信息学院 版权所有，转载或翻印必究 Page 35,散列基本思想,一个确定的函数关系h以结点的关键码K为自变
14、量函数值h(K)作为结点的存储地址检索时也是根据这个函数计算其存储位置通常散列表的存储空间是一个一维数组散列地址是数组的下标,北京大学信息学院 版权所有，转载或翻印必究 Page 36,例9.1：已知线性表关键码集合为：S=and,begin,do,end,for,go,if,repeat,then,until,while可设散列表为：char HT2268;散列函数H(key)的值，取为关键码key中的第一个字母在字母表a,b,c,.,z中的序号，即：H(key)=key0 a,北京大学信息学院 版权所有，转载或翻印必究 Page 37,北京大学信息学院 版权所有，转载或翻印必究 Page
15、38,例9.2：在集合S中增加4个关键码，集合S1=S+else,array,with,up要修改散列函数：散列函数的值为key中首尾字母在字母表中序号的平均值，即：int H3(key)char key;int i;i=0;while(i8)return(key0+key(i-1)2*a)/2),北京大学信息学院 版权所有，转载或翻印必究 Page 39,北京大学信息学院 版权所有，转载或翻印必究 Page 40,负载因子=n/m散列表的空间大小为m填入表中的结点数为n冲突某个散列函数对于不相等的关键码计算出了相同的散列地址在实际应用中，不产生冲突的散列函数极少存在同义词发生冲突的两个关键码
16、,北京大学信息学院 版权所有，转载或翻印必究 Page 41,采用散列技术时需要考虑的两个首要问题是：（1）如何构造(选择)使结点“分布均匀”的散列函数？（2）一旦发生冲突，用什么方法来解决？还需考虑散列表本身的组织方法,北京大学信息学院 版权所有，转载或翻印必究 Page 42,9.2.1 散列函数,散列函数：把关键码值映射到存储位置的函数，通常用h来表示 Address Hash(key),北京大学信息学院 版权所有，转载或翻印必究 Page 43,散列函数的选取原则,运算尽可能简单函数的值域必须在表长的范围内尽可能使得关键码不同时，其散列函数值亦不相同,北京大学信息学院 版权所有，转载或
17、翻印必究 Page 44,需要考虑各种因素,关键码长度散列表大小关键码分布情况记录的检索频率,北京大学信息学院 版权所有，转载或翻印必究 Page 45,常用散列函数选取方法,除余法乘余取整法平方取中法数字分析法基数转换法折叠法ELFhash字符串散列函数,北京大学信息学院 版权所有，转载或翻印必究 Page 46,9.2.1.1 除余法,除余法：用关键码x除以M(往往取散列表长度)，并取余数作为散列地址。散列函数为：h(x)x mod M通常选择一个质数作为M值函数值依赖于自变量x的所有位，而不仅仅是最右边k个低位增大了均匀分布的可能性,北京大学信息学院 版权所有，转载或翻印必究 Page
18、47,若把M设置为偶数x是偶数，h(x)也是偶数x是奇数，h(x)也是奇数缺点：分布不均匀如果偶数关键码比奇数关键码出现的概率大，那么函数值就不能均匀分布反之亦然,北京大学信息学院 版权所有，转载或翻印必究 Page 48,若把M设置为2的幂那么，h(x)x mod 2k 仅仅是x(用二进制表示)最右边的k个位(bit)若把M设置为10的幂那么，h(x)x mod 10k 仅仅是x(用十进制表示)最右边的k个十进制位(digital)缺点：散列值不依赖于x的全部比特位,北京大学信息学院 版权所有，转载或翻印必究 Page 49,除余法的潜在缺点连续的关键码映射成连续的散列值虽然能保证连续的关键
19、码不发生冲突但也意味着要占据连续的数组单元可能导致程序性能的降低,北京大学信息学院 版权所有，转载或翻印必究 Page 50,9.2.1.2 乘余取整法,先让关键码 key 乘上一个常数A(0A 1)，提取乘积的小数部分然后，再用整数 n 乘以这个值，对结果向下取整，把它做为散列的地址散列函数为：hash(key)=n*(A*key%1)“A*key%1”表示取 A*key 小数部分:A*key%1=A*key-A*key,北京大学信息学院 版权所有，转载或翻印必究 Page 51,乘余取整法示例,设关键码 key=123456,n=10000且取 A=0.6180339，因此有 hash(1
20、23456)=10000*(0.6180339*123456%1)=10000*(76300.0041151%1)=10000*0.0041151=41,北京大学信息学院 版权所有，转载或翻印必究 Page 52,乘余取整法参数取值的考虑,若地址空间为p位，就取n=2p所求出的散列地址正好是计算出来的 A*key%1=A*key-A*key 值的小数点后最左p位值此方法的优点:对 n 的选择无关紧要Knuth认为：A可以取任何值，与待排序的数据特征有关。一般情况下取黄金分割 最理想,北京大学信息学院 版权所有，转载或翻印必究 Page 53,9.2.1.3 平方取中法,此时可采用平方取中法：先
21、通过求关键码的平方来扩大差别，再取其中的几位或其组合作为散列地址例如，一组二进制关键码：(00000100，00000110，000001010，000001001，000000111)平方结果为：(00010000，00100100，01100010，01010001，00110001)若表长为4个二进制位，则可取中间四位作为散列地址：(0100，1001，1000，0100，1100),北京大学信息学院 版权所有，转载或翻印必究 Page 54,9.2.1.4 数字分析法,设有 n 个 d 位数，每一位可能有 r 种不同的符号这 r 种不同的符号在各位上出现的频率不一定相同可能在某些位上分
22、布均匀些，每种符号出现的几率均等在某些位上分布不均匀，只有某几种符号经常出现可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址,北京大学信息学院 版权所有，转载或翻印必究 Page 55,数字分析法（续1）,计算各位数字中符号分布的均匀度 k 的公式：其中，表示第 i 个符号在第 k 位上出现的次数，n/r 表示各种符号在 n 个数中均匀出现的期望值。计算出的 k 值越小，表明在该位(第k 位)各种符号分布得越均匀,北京大学信息学院 版权所有，转载或翻印必究 Page 56,9 9 2 1 4 8 位，1=57.60 9 9 1 2 6 9位，2=57.60 9 9 0 5 2
23、7位，3=17.60 9 9 1 6 3 0位，4=5.60 9 9 1 8 0 5位，5=5.60 9 9 1 5 5 8位，6=5.60 9 9 2 0 4 7 9 9 0 0 0 1,若散列表地址范围有 3 位数字,取各关键码的位做为记录的散列地址也可以把第，和第位相加，舍去进位，变成一位数，与第，位合起来作为散列地址。还可以用其它方法,北京大学信息学院 版权所有，转载或翻印必究 Page 57,数字分析法（续3）,位，仅9出现8次，1=（8-8/10）21+（0-8/10）2 9=57.6位，仅9出现8次，2=（8-8/10）21+（0-8/10）2 9=57.6 位，0和2各出现两次
24、，1出现4次 3=（2-8/10）22+（4-8/10）2 1+（0-8/10）2 7=17.6位，0和5各出现两次，1、2、6、8各出现1次位，0和4各出现两次，2、3、5、6各出现1次位，7和8各出现两次，0、1、5、9各出现1次 4=5=6=（2-8/10）22+（1-8/10）2 4+（0-8/10）2 4=5.6,北京大学信息学院 版权所有，转载或翻印必究 Page 58,数字分析法（续4）,数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况它完全依赖于关键码集合如果换一个关键码集合，选择哪几位数据要重新决定,北京大学信息学院 版权所有，转载或翻印必究 Page 59,
25、9.2.1.5 基数转换法,把关键码看成是另一进制上的数后再把它转换成原来进制上的数取其中若干位作为散列地址一般取大于原来基数的数作为转换的基数，并且两个基数要互素,北京大学信息学院 版权所有，转载或翻印必究 Page 60,例如，给定一个十进制数的关键码是(210485)10，把它看成以13为基数的十三进制数(210485)13，再把它转换为十进制(210485)13=2135+1134+4132+813+5=(771932)10假设散列表长度是10000，则可取低4位1932作为散列地址,北京大学信息学院 版权所有，转载或翻印必究 Page 61,9.2.1.6 折叠法,关键码所含的位数很
26、多，采用平方取中法计算太复杂折叠法将关键码分割成位数相同的几部分（最后一部分的位数可以不同）然后取这几部分的叠加和（舍去进位）作为散列地址,北京大学信息学院 版权所有，转载或翻印必究 Page 62,两种叠加方法：移位叠加 把各部分的最后一位对齐相加分界叠加 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址,北京大学信息学院 版权所有，转载或翻印必究 Page 63,例9.6 如果一本书的编号为0-442-20586-4 5 8 6 4 5 8 6 4 4 2 2 0 0 2 2 4+0 4+0 41 0 0 8 8 6 0 9 2h(key)=0088 h(key
27、)=6092(a)移位叠加(b)分界叠加,北京大学信息学院 版权所有，转载或翻印必究 Page 64,9.2.1.7 ELFhash字符串散列函数,用于UNIX系统V4.0“可执行链接格式”(Executable and Linking Format，即ELF)int ELFhash(char*key)unsigned long h=0;while(*key)h=(h 24;h,北京大学信息学院 版权所有，转载或翻印必究 Page 65,长字符串和短字符串都很有效字符串中每个字符都有同样的作用对于散列表中的位置不可能产生不平均的分布,北京大学信息学院 版权所有，转载或翻印必究 Page 66,
28、散列函数的应用,在实际应用中应根据关键码的特点，选用适当的散列函数有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化”若关键码不是整数而是字符串时，可以把每个字符串转换成整数，再应用平方取中法,北京大学信息学院 版权所有，转载或翻印必究 Page 67,碰撞的处理,开散列方法(open hashing，也称为拉链法，separate chaining)把发生冲突的关键码存储在散列表主表之外闭散列方法(closed hashing，也称为开地址方法，open addressing)把发生冲突的关键码存储在表中另一个槽内,北京大学信息学院 版权所有，转载或翻印必
29、究 Page 68,9.2.2 开散列方法,当碰撞发生时就拉出一条链，建立一个链表方式的同义词子表 动态申请同义词的空间，适合于内存操作例：77、7、110、95、14、75、62 h(Key)=Key%11,北京大学信息学院 版权所有，转载或翻印必究 Page 69,9.2.2.1 拉链法,表中的空单元其实应该有特殊值标记出来，例如-1或INFINITY或者使得散列表中的内容就是指针，空单元则内容为空指针。插入同义词时，可以对同义词链排序插入,北京大学信息学院 版权所有，转载或翻印必究 Page 70,给定一个大小为M存储n个记录的表散列函数(在理想情况下)将把记录在表中M个位置平均放置，使
30、得平均每一个链表中有n/M个记录Mn 时，散列方法的平均代价就是(1),北京大学信息学院 版权所有，转载或翻印必究 Page 71,如果整个散列表存储在内存中，开散列方法比较容易实现如果散列表存储在磁盘中，用开散列不太合适一个同义词表中的元素可能存储在不同的磁盘页中这就会导致在检索一个特定关键码值时引起多次磁盘访问，从而增加了检索时间,北京大学信息学院 版权所有，转载或翻印必究 Page 72,9.2.2.2 桶式散列,适合于存储于磁盘的散列表基本思想:把一个文件的记录分为若干存储桶，每个存储桶包含一个或多个页块一个存储桶内的各页块用指针连接起来，每个页块包含若干记录散列函数h(K)表示具有关
31、键码值K的记录所在的存储桶号,北京大学信息学院 版权所有，转载或翻印必究 Page 73,桶式散列,下图表示了一个具有B个存储桶的散列文件组织如果B很小，存储桶目录表可放在内存如果B较大，要存放好多页块，则存储桶目录表就放到外存上,北京大学信息学院 版权所有，转载或翻印必究 Page 74,计算关键码K对应的散列函数值i=h(K)，得到存储桶号i 调存储桶目录表中包含第i个存储桶目录的页块进入内存得到第i个存储桶的第一个页块的地址根据这个地址把相应的页块调入内存在这页块中顺序扫描每一个记录，检查有无关键码值等于K的记录，若找到了就结束查找若找不到就在该页块的头上找到链指针，从而找出i号存储桶的
32、下一个页块地址，把下一个页块调入内存，以同样的方式查找以此类推，直到找出关键码值等于K的记录或断定不存在关键码值等于K的记录(即找完桶中所有页块)为止,北京大学信息学院 版权所有，转载或翻印必究 Page 75,桶式散列文件组织,北京大学信息学院 版权所有，转载或翻印必究 Page 76,桶式散列文件的修改,假定我们要修改关键码值为K的记录的一个或多个字段若要修改的字段中有一些是关键码的一部分，则这样的修改相当于删除加插入如果修改的字段不涉及关键码字段，则首先查找这个记录，若找到就按要求进行修改，并写回该修改后的记录(即把包含该修改后记录的页块写回外存)，若找不到，则表示出错因为修改一个不存在
33、的记录是没有意义的,北京大学信息学院 版权所有，转载或翻印必究 Page 77,桶式散列文件的插入,查找与要插入记录具有相同关键码值K的记录若找到，则表示出错如找不到这个记录，则在该存储桶(即h(K)号桶)的各页块中找一个空子块，把要插入的记录放进去若找不到一个空子块则向文件系统申请一个新页块给此桶，新块头存入一个空指针在该桶的最后一个页块的块头上存入指向新页块的指针，把新页块链上把要插入的记录放在新页块的第一个子块中,北京大学信息学院 版权所有，转载或翻印必究 Page 78,桶式散列文件的删除,首先利用查找过程查找被删除的记录若找不到，则表示出错，因为要删除一个文件中不存在的记录是没有意义
34、的若找到，则把该记录的删除标记置为0，表示该记录已被删除该被删记录所占子块是否允许重新使用?这要看有否来自其他地方的指针指向该子块引用计数位,北京大学信息学院 版权所有，转载或翻印必究 Page 79,桶式散列文件的删除(续),如果文件中的记录不受其它条件约束当要被删除的记录不是桶中最后一个记录时可以将桶内最后一个记录移入被删记录的子块这样既达到了删除的目的，又可以节省存储当桶内最后一个页块的记录被移空时，可将该页块交回给文件系统，以备后用,北京大学信息学院 版权所有，转载或翻印必究 Page 80,桶式散列的磁盘访问性能分析,一个查找平均访外次数约为桶内页块数k的一半调存储桶目录表进入内存(
35、假定目录表不在内存)为了寻找要求的记录必须逐个检查一个桶内各页块实际上是(k+1)/2对于修改、插入、删除等运算尚需另一次访外，用于重新写回外存,北京大学信息学院 版权所有，转载或翻印必究 Page 81,桶式散列的磁盘访问性能分析(续),最理想状况:每个桶仅由一个页块组成，这样只需访外二次(对检索)或三次(对其他运算)要求存储桶的个数大致等于记录存放所需的页块数散列函数值分布均匀,北京大学信息学院 版权所有，转载或翻印必究 Page 82,理想状况很难实现尤其当文件不断增长时，桶内的页块数也随之增多由于分布不均匀，有些桶内页块数可能过多，严重影响检索效率必要时需对文件进行重新组织改变散列函数
36、增加存储桶目录表的大小,北京大学信息学院 版权所有，转载或翻印必究 Page 83,9.2.3 闭散列方法,把所有记录直接存储在散列表中。每个记录关键码有一个基位置即h(key)，即由散列函数计算出来的地址如果要插入一个关键码，而另一个记录已经占据了R的基位置(发生碰撞)，那么就把R存储在表中的其它地址内，由冲突解决策略确定是哪个地址,北京大学信息学院 版权所有，转载或翻印必究 Page 84,闭散列表解决冲突的基本思想,当冲突发生时，使用某种方法为关键码K生成一个散列地址序列 d0，d1，d2，.di，.dm-1其中d0=h（K）称为K的基地址地置所有di(0im)是后继散列地址形成探查的方
37、法不同，所得到的解决冲突的方法也不同,北京大学信息学院 版权所有，转载或翻印必究 Page 85,当插入K时，若基地址上的结点已被别的数据元素占用则按上述地址序列依次探查，将找到的第一个开放的空闲位置di作为K的存储位置若所有后继散列地址都不空闲，说明该闭散列表已满，报告溢出,北京大学信息学院 版权所有，转载或翻印必究 Page 86,检索过程,检索时也要像插入时一样遵循同样的策略重复冲突解决过程找出在基位置没有找到的记录,北京大学信息学院 版权所有，转载或翻印必究 Page 87,探查序列,插入和检索函数都假定每个关键码的探查序列中至少有一个存储位置是空的，否则它们就会进入一个无限循环中,北
38、京大学信息学院 版权所有，转载或翻印必究 Page 88,9.2.3.1 线性探查,基本思想：如果记录的基位置存储位置被占用，那么就在表中下移，直到找到一个空存储位置。依次探查下述地址单元：d+1，d+2，.，M-1，0，1，.，d-1 用于简单线性探查的探查函数是：p(K，i)=i线性探查的优点表中所有的存储位置都可以作为插入新记录的候选位置,北京大学信息学院 版权所有，转载或翻印必究 Page 89,线性探查示例,例9.7：已知一组关键码为（26，36，41，38，44，15，68，12，06，51，25），散列表长度M=15，用线性探查法解决冲突构造这组关键码的散列表n=11，M=15选
39、P=13，则：h(key)=key%13,北京大学信息学院 版权所有，转载或翻印必究 Page 90,线性探查示例(续),按顺序插入各个结点：26:h(26)=0，36:h(36)=10，41:h(41)=2，38:h(38)=12，44:h(44)=5 插入15时，其散列地址为2，由于2已被关键码为41的元素占用，故需进行探查按顺序探查法，显然3为开放的空闲地址，故可将其放在3单元类似地，68和12可分别放在4和13单元中，依次类推,北京大学信息学院 版权所有，转载或翻印必究 Page 91,可建立如下的散列：,M=15 h(key)=key%13,北京大学信息学院 版权所有，转载或翻印必究
40、 Page 92,“聚集”（clustering，或称为“堆积”）散列地址不同的结点，争夺同一后继散列地址小的聚集可能汇合成大的聚集导致很长的探查序列在理想情况下，表中的每个空槽都应该有相同的机会接收下一个要插入的记录。下一条记录放在第11个槽中的概率是2/15放到第7个槽中的概率是11/15,北京大学信息学院 版权所有，转载或翻印必究 Page 93,改进线性探查,每次跳过常数c个而不是1个槽探查序列中的第i个槽是(h(K)+ic)mod M基位置相邻的记录就不会进入同一个探查序列了 探查函数是p(K，i)=i*c必须使常数c与M互素,北京大学信息学院 版权所有，转载或翻印必究 Page 9
41、4,例如，c=2，要插入关键码k1和k2，h(k1)=3，h(k2)=5探查序列k1的探查序列是3、5、7、9、.k2的探查序列就是5、7、9、.k1和k2的探查序列还是纠缠在一起，从而导致了聚集,北京大学信息学院 版权所有，转载或翻印必究 Page 95,9.2.3.2 二次探查,探查序列依次为：12，-12，22，-22，.，即探查函数是 d2i-1=(d+i2)%M d2i=(d i2)%M用于简单线性探查的探查函数是 p(K，2i-1)=i*i p(K，2i)=-i*i,北京大学信息学院 版权所有，转载或翻印必究 Page 96,例：使用一个大小M=13的表 假定对于关键码k1和k2，
42、h(k1)=3，h(k2)=2探查序列k1的探查序列是3、4、2、7、.k2的探查序列是2、3、1、6、.尽管k2会把k1的基位置作为第2个选择来探查，但是这两个关键码的探查序列此后就立即分开了,北京大学信息学院 版权所有，转载或翻印必究 Page 97,9.2.3.3 伪随机数序列探查,探查函数 p(K，i)=permi-1这里perm是一个长度为M-1的数组包含值从1到M-1的随机序列,北京大学信息学院 版权所有，转载或翻印必究 Page 98,产生n个数的伪随机排列,void permute(int*array,int n)for(int i=1;i=n;i+)swap(arrayi-1
43、,arrayRandom(i);,北京大学信息学院 版权所有，转载或翻印必究 Page 99,例：考虑一个大小为M=13的表，perm0=2，perm1=3，perm2=7。假定两个关键码k1和k2，h(k1)=4，h(k2)=2探查序列k1的探查序列是4、6、7、11、.k2的探查序列是2、4、5、9、.尽管k2会把k1的基位置作为第2个选择来探查，但是这两个关键码的探查序列此后就立即分开了,北京大学信息学院 版权所有，转载或翻印必究 Page 100,二级聚集,能消除基本聚集基地址不同的关键码，其探查序列的某些段重叠在一起伪随机探查和二次探查可以消除二级聚集(secondary clust
44、ering)如果两个关键码散列到同一个基地址，还是得到同样的探查序列，所产生的聚集原因探查序列只是基地址的函数，而不是原来关键码值的函数例子：伪随机探查和二次探查,北京大学信息学院 版权所有，转载或翻印必究 Page 101,9.2.3.4 双散列探查法,避免二级聚集探查序列是原来关键码值的函数而不仅仅是基位置的函数双散列探查法利用第二个散列函数作为常数每次跳过常数项，做线性探查,北京大学信息学院 版权所有，转载或翻印必究 Page 102,双散列探查法使用两个散列函数h1和h2若在地址h1(key)=d发生冲突，则再计算h2(key)，得到的探查序列为：(d+h2(key)%M，(d+2h2
45、(key)%M，(d+3h2(key)%M，.,北京大学信息学院 版权所有，转载或翻印必究 Page 103,双散列函数探查法序列公式：di=(d+i h2(key)%M双散列函数公式：p(K,i)=i*h2(key),北京大学信息学院 版权所有，转载或翻印必究 Page 104,双散列探查法(续),h2(key)必须与M互素使发生冲突的同义词地址均匀地分布在整个表中否则可能造成同义词地址的循环计算双散列的优点:不易产生“聚集”缺点：计算量增大,北京大学信息学院 版权所有，转载或翻印必究 Page 105,方法1：选择M为一个素数，h2返回的值在1h2(K)M 1范围之间方法2：设置M=2m，
46、让h2返回一个1到2m之间的奇数值方法3：若M是素数，h1(K)=K mod Mh2(K)=K mod(M-2)+1或者h2(K)=K/M mod(M-2)+1 方法4：若M是任意数，h1(K)=K mod p，(p 是小于M的最大素数)h2(K)=K mod q+1(q是小于p的最大素数),北京大学信息学院 版权所有，转载或翻印必究 Page 106,9.2.4 闭散列表的算法实现,插入算法：假设给定的值为K，根据所设定的散列函数h，计算出散列地址h(K)若表中该地址对应的空间未被占用，则把待插入记录填入该地址如果该地址中的值与K相等，则报告“散列表中已有此记录”否则，按设定的处理冲突方法查
47、找探查序列的下一个地址，如此反复下去直到某个地址空间未被占用（可以插入）或者关键码比较相等（有重复记录，不需要插入）为止,北京大学信息学院 版权所有，转载或翻印必究 Page 107,/代码9-6 散列表插入算法/将数据元素e插入到散列表 HTtemplate bool hashdict:hashInsert(const Elem,北京大学信息学院 版权所有，转载或翻印必究 Page 108,散列表的检索,插入过程类似采用的探查序列也相同,北京大学信息学院 版权所有，转载或翻印必究 Page 109,检索算法：假设给定的值为K，根据所设定的散列函数h，计算出散列地址h(K)若表中该地址对应的空
48、间未被占用，则检索失败否则将该地址中的值与K比较，若相等则检索成功否则，按建表时设定的处理冲突方法查找探查序列的下一个地址，如此反复下去直到某个地址空间未被占用（可以插入）或者关键码比较相等（有重复记录，不需要插入）为止,北京大学信息学院 版权所有，转载或翻印必究 Page 110,散列表示例,M=15 h(key)=key%13,北京大学信息学院 版权所有，转载或翻印必究 Page 111,/代码9-7 散列表检索算法/检索关键码值为k的记录。假定每个关键码的探查序列中至少有一个槽是空的，否则它们就会进入一个无限循环中。template bool hashdict:hashSearch(co
49、nst Key,北京大学信息学院 版权所有，转载或翻印必究 Page 112,删除,删除记录的时候，有两点需要重点考虑：(1)删除一个记录一定不能影响后面的检索(2)释放的存储位置应该能够为将来插入使用 只有开散列方法（分离的同义词子表）可以真正删除闭散列方法都只能作标记（墓碑），不能真正删除若真正删除了探查序列将断掉检索算法“直到某个地址空间未被占用（检索失败）”墓碑标记增加了平均检索长度,北京大学信息学院 版权所有，转载或翻印必究 Page 113,删除，断线索,M=15 h(key)=key%13删除41，检索15关键码41和15的基地址都是第2个槽，15被线性探查放到第3个如果从表中删
50、除41，对15的检索必须仍然探查第2个槽，断线索,北京大学信息学院 版权所有，转载或翻印必究 Page 114,删除带来的问题?,另一方面，删除后释放的槽应该能够为将来的插入使用不想让散列表中的位置由于删除而永远不可用,北京大学信息学院 版权所有，转载或翻印必究 Page 115,下列方法可取吗?,把被删除位置的探查序列之后其他记录逐步前移？因为一个单元可能处于不只一个探查序列中（考虑前面讨论过的“聚集”现象）这可能会把其他同义词表中的记录给挪动了，而造成其他混乱或者把该探查序列中最后的记录填入到刚刚被删除的单元？需要考察该纪录与被删除纪录是否为“同义词”,北京大学信息学院 版权所有，转载或翻
