九章节检索.ppt
第九章 检索,任课教员：张 铭 http:/db.pku.edu.cn/mzhang/DS/ mzhangdb.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有，转载或翻印必究,北京大学信息学院 版权所有，转载或翻印必究 Page 2,9.1 基本概念 9.2 线性表的检索 9.3 散列表的检索,北京大学信息学院 版权所有，转载或翻印必究 Page 3,基本概念,检索：在一组记录集合中找到关键码值等于给定值的某个记录，或者找到关键码值符合特定条件的某些记录的过程 检索的效率非常重要 尤其对于大数据量 需要对数据进行特殊的存储处理,北京大学信息学院 版权所有，转载或翻印必究 Page 4,基本概念（续）,预排序 排序算法本身比较费时 只是预处理（在检索之前已经完成） 建立索引 检索时充分利用辅助索引信息 牺牲一定的空间 从而提高检索效率,北京大学信息学院 版权所有，转载或翻印必究 Page 5,基本概念（续）,散列技术 把数据组织到一个表中 根据关键码的值来确定表中每个记录的位置 缺点： 不适合进行范围查询 一般也不允许出现重复关键码 当散列方法不适合于基于磁盘的应用程序时，我们可以选择B树方法,北京大学信息学院 版权所有，转载或翻印必究 Page 6,平均检索长度(ASL),关键码的比较 检索运算的主要操作 平均检索长度(Average Search Length) 检索过程中对关键码需要执行的平均比较次数 是衡量检索算法优劣的时间标准,北京大学信息学院 版权所有，转载或翻印必究 Page 7,平均检索长度,ASL是存储结构中对象总数n的函数，其定义为： Pi 为检索第i个元素的概率 Ci 为找到第i个元素所需的关键码值与给定值的比较次数,北京大学信息学院 版权所有，转载或翻印必究 Page 8,平均检索长度,假设线性表为（a, b, c）检索a、b、c的概率分别为0.4、0.1、0.5 顺序检索算法的平均检索长度为0.4×1+0.1×2+0.5×3 = 2.1 即平均需要2.1次给定值与表中关键码值的比较才能找到待查元素,北京大学信息学院 版权所有，转载或翻印必究 Page 9,衡量一个检索算法还需要考虑 算法所需的存储量 算法的复杂性 .,北京大学信息学院 版权所有，转载或翻印必究 Page 10,9.1 基于线性表的检索,9.1.1 顺序检索 9.1.2 二分检索 9.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) key=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次（设置了一个监视哨）,北京大学信息学院 版权所有，转载或翻印必究 Page 15,顺序检索性能分析（续）,平均检索长度 假设检索成功的概率为p，检索失败的概率为q=(1-p)，则平均检索长度为 （n+1)/2 ASL (n+1) 优缺点 优点：插入元素可以直接加在表尾(1) 缺点：检索时间太长(n),北京大学信息学院 版权所有，转载或翻印必究 Page 16,9.1.2 二分检索法,有序表：线性表中所有数据元素按关键码值递增（或递减）的次序排列 在有序表的存储表示下，检索可以用效率更高的二分检索法实现。,北京大学信息学院 版权所有，转载或翻印必究 Page 17,9.1.2 二分法检索,有序表中所有元素按关键码值递增（或递减）的次序排列 将表中任一元素dataListi的关键码值Key与给定值K比较， 可根据三种比较结果区分出三种情况（以递增为例）： （1） Key = K，检索成功，dataListi即为待查元素 （2） Key K，说明待查元素若在表中，且一定排在dataListi之前 （3） Key K，说明待查元素若在表中，且一定排在dataListi之后 因此，在一次比较之后，若没有找到待查元素（即情况1未出现），则可根据比较结果缩小进一步检索的区间,北京大学信息学院 版权所有，转载或翻印必究 Page 18,二分法检索算法,/代码9-3 二分检索算法 template int BinSearch (vector* /检索失败，返回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 50) 优缺点 优点：平均检索长度与最大检索长度相近，检索速度快 缺点：要排序、顺序存储，不易更新(插/删),北京大学信息学院 版权所有，转载或翻印必究 Page 22,9.1.3 分块检索,顺序与二分法的折衷 既有较快的检索 又有较灵活的更改,北京大学信息学院 版权所有，转载或翻印必究 Page 23,分块检索思想,“按块有序” 设线性表中共有n个数据元素，将表分成b块 不需要均匀 每一块可能不满 每一块中的关键码不一定有序 但前一块中的最大关键码必须小于后一块中的最小关键码,北京大学信息学院 版权所有，转载或翻印必究 Page 24,索引表 各块中的最大关键码 及各块起始位置 可能还需要块中元素个数（每一块可能不满） 索引表是一个递增有序表 由于表是分块有序的,北京大学信息学院 版权所有，转载或翻印必究 Page 25,分块检索分两个阶段,（1）确定待查元素所在的块 （2）在块内检索待查的元素,北京大学信息学院 版权所有，转载或翻印必究 Page 26,分块检索索引顺序结构,索引表中每个索引项有两个域 块内最大关键码 块起始位置,北京大学信息学院 版权所有，转载或翻印必究 Page 27,分块检索性能分析,分块检索为两级检索 先在索引表中确定待查元素所在的块； 设在索引表中确定块号的时间开销是ASLb 然后在块内检索待查的元素。 在块中查找记录的时间开销为ASLw ASL(n) = ASLb + ASLw,北京大学信息学院 版权所有，转载或翻印必究 Page 28,分块检索性能分析(续1),索引表是按块内最大关键码有序的，且长度也不大，可以二分检索，也可以顺序检索 各子表内各个记录不是按记录关键码有序，只能顺序检索,北京大学信息学院 版权所有，转载或翻印必究 Page 29,分块检索性能分析(续2),假设在索引表中用顺序检索，在块内也用顺序检索 当s= 时，ASL取最小值， ASL = +1 ,北京大学信息学院 版权所有，转载或翻印必究 Page 30,分块检索性能分析(续3),当n=10,000时 顺序检索5,000次 二分法检索14次 分块检索100次 如果数据块（子表）存放在外存时，还会受到页块大小的制约 此时往往以外存一个/读取的数据（一页）作为一块,北京大学信息学院 版权所有，转载或翻印必究 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 散列检索,基于关键码比较的检索 顺序检索，=, != 二分法、树型 , = , 检索是直接面向用户的操作 当问题规模n很大时，上述检索的时间效率可能使得用户无法忍受 最理想的情况 根据关键码值，直接找到记录的存储地址 不需要把待查关键码与候选记录集合的某些记录进行逐个比较,北京大学信息学院 版权所有，转载或翻印必究 Page 34,例如，读取指定下标的数组元素 根据数组的起始存储地址、以及数组下标值而直接计算出来的，所花费的时间是O(1) 与数组元素个数的规模n无关 受此启发，计算机科学家发明了散列方法 散列是一种重要的存储方法 也是一种常见的检索方法,北京大学信息学院 版权所有，转载或翻印必究 Page 35,散列基本思想,一个确定的函数关系h 以结点的关键码K为自变量 函数值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 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 冲突 某个散列函数对于不相等的关键码计算出了相同的散列地址 在实际应用中，不产生冲突的散列函数极少存在 同义词 发生冲突的两个关键码,北京大学信息学院 版权所有，转载或翻印必究 Page 41,采用散列技术时需要考虑的两个首要问题是： （1）如何构造(选择)使结点“分布均匀”的散列函数？ （2）一旦发生冲突，用什么方法来解决？ 还需考虑散列表本身的组织方法,北京大学信息学院 版权所有，转载或翻印必究 Page 42,9.2.1 散列函数,散列函数：把关键码值映射到存储位置的函数，通常用h来表示 Address Hash ( key ),北京大学信息学院 版权所有，转载或翻印必究 Page 43,散列函数的选取原则,运算尽可能简单 函数的值域必须在表长的范围内 尽可能使得关键码不同时，其散列函数值亦不相同,北京大学信息学院 版权所有，转载或翻印必究 Page 44,需要考虑各种因素,关键码长度 散列表大小 关键码分布情况 记录的检索频率 ,北京大学信息学院 版权所有，转载或翻印必究 Page 45,常用散列函数选取方法,除余法 乘余取整法 平方取中法 数字分析法 基数转换法 折叠法 ELFhash字符串散列函数,北京大学信息学院 版权所有，转载或翻印必究 Page 46,9.2.1.1 除余法,除余法：用关键码x除以M(往往取散列表长度)，并取余数作为散列地址。散列函数为： h(x) x mod M 通常选择一个质数作为M值 函数值依赖于自变量x的所有位，而不仅仅是最右边k个低位 增大了均匀分布的可能性,北京大学信息学院 版权所有，转载或翻印必究 Page 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,除余法的潜在缺点 连续的关键码映射成连续的散列值 虽然能保证连续的关键码不发生冲突 但也意味着要占据连续的数组单元 可能导致程序性能的降低,北京大学信息学院 版权所有，转载或翻印必究 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(123456) = = 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 平方取中法,此时可采用平方取中法：先通过求关键码的平方来扩大差别，再取其中的几位或其组合作为散列地址 例如， 一组二进制关键码：(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 种不同的符号在各位上出现的频率不一定相同 可能在某些位上分布均匀些，每种符号出现的几率均等 在某些位上分布不均匀，只有某几种符号经常出现 可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址,北京大学信息学院 版权所有，转载或翻印必究 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 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）2×1+（0-8/10） 2 ×9=57.6 位，仅9出现8次， 2 =（8-8/10）2×1+（0-8/10） 2 ×9=57.6 位，0和2各出现两次，1出现4次 3 =（2-8/10）2×2+（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）2×2+（1-8/10） 2 ×4+ （0-8/10） 2 ×4 =5.6,北京大学信息学院 版权所有，转载或翻印必究 Page 58,数字分析法（续4）,数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况 它完全依赖于关键码集合 如果换一个关键码集合，选择哪几位数据要重新决定,北京大学信息学院 版权所有，转载或翻印必究 Page 59,9.2.1.5 基数转换法,把关键码看成是另一进制上的数后 再把它转换成原来进制上的数 取其中若干位作为散列地址 一般取大于原来基数的数作为转换的基数，并且两个基数要互素,北京大学信息学院 版权所有，转载或翻印必究 Page 60,例如，给定一个十进制数的关键码是(210485)10，把它看成以13为基数的十三进制数(210485)13 ，再把它转换为十进制 (210485)13 = 2×135 + 1×134 + 4×132 + 8×13 + 5 = (771932)10 假设散列表长度是10000，则可取低4位1932作为散列地址,北京大学信息学院 版权所有，转载或翻印必究 Page 61,9.2.1.6 折叠法,关键码所含的位数很多，采用平方取中法计算太复杂 折叠法 将关键码分割成位数相同的几部分（最后一部分的位数可以不同） 然后取这几部分的叠加和（舍去进位）作为散列地址,北京大学信息学院 版权所有，转载或翻印必究 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 4 1 0 0 8 8 6 0 9 2 h(key)=0088 h(key)=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,散列函数的应用,在实际应用中应根据关键码的特点，选用适当的散列函数 有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化” 若关键码不是整数而是字符串时，可以把每个字符串转换成整数，再应用平方取中法,北京大学信息学院 版权所有，转载或翻印必究 Page 67,碰撞的处理,开散列方法( open hashing，也称为拉链法，separate chaining ) 把发生冲突的关键码存储在散列表主表之外 闭散列方法( closed hashing，也称为开地址方法，open addressing ) 把发生冲突的关键码存储在表中另一个槽内,北京大学信息学院 版权所有，转载或翻印必究 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个位置平均放置，使得平均每一个链表中有n/M个记录 Mn 时，散列方法的平均代价就是(1),北京大学信息学院 版权所有，转载或翻印必究 Page 71,如果整个散列表存储在内存中，开散列方法比较容易实现 如果散列表存储在磁盘中，用开散列不太合适 一个同义词表中的元素可能存储在不同的磁盘页中 这就会导致在检索一个特定关键码值时引起多次磁盘访问，从而增加了检索时间,北京大学信息学院 版权所有，转载或翻印必究 Page 72,9.2.2.2 桶式散列,适合于存储于磁盘的散列表 基本思想: 把一个文件的记录分为若干存储桶，每个存储桶包含一个或多个页块 一个存储桶内的各页块用指针连接起来，每个页块包含若干记录 散列函数h(K)表示具有关键码值K的记录所在的存储桶号,北京大学信息学院 版权所有，转载或翻印必究 Page 73,桶式散列,下图表示了一个具有B个存储桶的散列文件组织 如果B很小，存储桶目录表可放在内存 如果B较大，要存放好多页块，则存储桶目录表就放到外存上,北京大学信息学院 版权所有，转载或翻印必究 Page 74,计算关键码K对应的散列函数值i= h(K)，得到存储桶号i 调存储桶目录表中包含第i个存储桶目录的页块进入内存 得到第i个存储桶的第一个页块的地址 根据这个地址把相应的页块调入内存 在这页块中顺序扫描每一个记录，检查有无关键码值等于K的记录， 若找到了就结束查找 若找不到就在该页块的头上找到链指针，从而找出i号存储桶的下一个页块地址，把下一个页块调入内存，以同样的方式查找 以此类推，直到找出关键码值等于K的记录或断定不存在关键码值等于K的记录(即找完桶中所有页块)为止,北京大学信息学院 版权所有，转载或翻印必究 Page 75,桶式散列文件组织,北京大学信息学院 版权所有，转载或翻印必究 Page 76,桶式散列文件的修改,假定我们要修改关键码值为K的记录的一个或多个字段 若要修改的字段中有一些是关键码的一部分，则这样的修改相当于删除加插入 如果修改的字段不涉及关键码字段，则 首先查找这个记录，若找到就按要求进行修改，并写回该修改后的记录(即把包含该修改后记录的页块写回外存)， 若找不到，则表示出错 因为修改一个不存在的记录是没有意义的,北京大学信息学院 版权所有，转载或翻印必究 Page 77,桶式散列文件的插入,查找与要插入记录具有相同关键码值K的记录 若找到，则表示出错 如找不到这个记录，则在该存储桶(即h(K)号桶)的各页块中找一个空子块，把要插入的记录放进去 若找不到一个空子块 则向文件系统申请一个新页块给此桶，新块头存入一个空指针 在该桶的最后一个页块的块头上存入指向新页块的指针，把新页块链上 把要插入的记录放在新页块的第一个子块中,北京大学信息学院 版权所有，转载或翻印必究 Page 78,桶式散列文件的删除,首先利用查找过程查找被删除的记录 若找不到，则表示出错，因为要删除一个文件中不存在的记录是没有意义的 若找到，则把该记录的删除标记置为0，表示该记录已被删除 该被删记录所占子块是否允许重新使用? 这要看有否来自其他地方的指针指向该子块 引用计数位,北京大学信息学院 版权所有，转载或翻印必究 Page 79,桶式散列文件的删除(续),如果文件中的记录不受其它条件约束 当要被删除的记录不是桶中最后一个记录时 可以将桶内最后一个记录移入被删记录的子块 这样既达到了删除的目的，又可以节省存储 当桶内最后一个页块的记录被移空时，可将该页块交回给文件系统，以备后用,北京大学信息学院 版权所有，转载或翻印必究 Page 80,桶式散列的磁盘访问性能分析,一个查找平均访外次数约为桶内页块数k的一半 调存储桶目录表进入内存(假定目录表不在内存) 为了寻找要求的记录必须逐个检查一个桶内各页块 实际上是(k+1)/2 对于修改、插入、删除等运算尚需另一次访外，用于重新写回外存,北京大学信息学院 版权所有，转载或翻印必究 Page 81,桶式散列的磁盘访问性能分析(续),最理想状况: 每个桶仅由一个页块组成， 这样只需访外二次(对检索)或三次(对其他运算) 要求 存储桶的个数大致等于记录存放所需的页块数 散列函数值分布均匀,北京大学信息学院 版权所有，转载或翻印必究 Page 82,理想状况很难实现 尤其当文件不断增长时，桶内的页块数也随之增多 由于分布不均匀，有些桶内页块数可能过多，严重影响检索效率 必要时需对文件进行重新组织 改变散列函数 增加存储桶目录表的大小,北京大学信息学院 版权所有，转载或翻印必究 Page 83,9.2.3 闭散列方法,把所有记录直接存储在散列表中。 每个记录关键码有一个基位置即h(key)，即由散列函数计算出来的地址 如果要插入一个关键码，而另一个记录已经占据了R的基位置(发生碰撞)， 那么就把R存储在表中的其它地址内，由冲突解决策略确定是哪个地址,北京大学信息学院 版权所有，转载或翻印必究 Page 84,闭散列表解决冲突的基本思想,当冲突发生时，使用某种方法为关键码K生成一个散列地址序列 d0，d1，d2，. di ，.dm-1 其中d0=h（K）称为K的基地址地置 所有di(0im)是后继散列地址 形成探查的方法不同，所得到的解决冲突的方法也不同,北京大学信息学院 版权所有，转载或翻印必究 Page 85,当插入K时，若基地址上的结点已被别的数据元素占用 则按上述地址序列依次探查，将找到的第一个开放的空闲位置di作为K的存储位置 若所有后继散列地址都不空闲，说明该闭散列表已满，报告溢出,北京大学信息学院 版权所有，转载或翻印必究 Page 86,检索过程,检索时也要像插入时一样遵循同样的策略 重复冲突解决过程 找出在基位置没有找到的记录,北京大学信息学院 版权所有，转载或翻印必究 Page 87,探查序列,插入和检索函数都假定每个关键码的探查序列中至少有一个存储位置是空的，否则它们就会进入一个无限循环中,北京大学信息学院 版权所有，转载或翻印必究 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 选P=13，则： h(key) =
