2数据结构与算法北大讲义

1、1平均检索长度（ASL）n 关键码的比较：检索运算的主要操作n 平均检索长度(Average Search Length)n 检索过程中对关键码的平均比较次数n 衡量检索算法优劣的时间标准nA S L= åPi C ii = 1Pi 为检索第i个元素的概率Ci 为找到第i个元素所需的关键码值与给定值的比较次数信息学院张铭 编写Ó 所有， 或Page 6基本概念（续）n 散列技术n 把数据组织到一个表中n 根据关键码的值来确定表中每个的位置n 缺点：n 不适合进行范围n 一般也不出现重复关键码n 当散列方法不适合于基于磁盘的应用程序时，我们可以选择B树方法信息学院张铭 编写&

2、#211; 所有， 或Page 5基本概念（续）n 预排序n 排序算法本身比较费时n 只是预处理（在检索之前已经完成）n 建立索引n 检索时充分利用辅助索引信息n 牺牲一定的空间n 从而提高检索效率信息学院张铭 编写Ó 所有， 或Page 4基本概念n 检索：在一组 集合中找到关键码值等于给定值的某个 ，或者找到关键码值符合特定条件的某些 的过程n 检索的效率非常重要n 尤其对于大数据量n 需要对数据进行特殊的处理信息学院张铭 编写 Ó 所有， 或Page 3第九章 检索n 基本概念9.1 线性表的检索n 9.2 集合的检索9.3 散列表的检索n 9.4 总结信息学院张铭

3、编写Ó 所有， 或Page 2数据结构与算法第九章 检索任课教员：张 铭mzhang信息科学与技术学院网络与信息系统Ó所有，或2“监视哨”顺序检索算法n 检索返回元素位置，检索失败统一返回0; template <class Type> intSeqSearch(vector<Item<Type>*>& dataList,int length, Type k) int i=length;/将第0个元素设为待检索值dataList0->setKey (k); /设监视哨while(dataListi->getKey()!

4、=k) i-; return i;/返回元素位置信息学院张铭 编写Ó 所有， 或Page 12顺序检索算法plate <class Type> class Item public:Item(Type value):key(value) Type getKey() return key; /取关键码值; void setKey(Type k) key=k; /置关键码private:Type key;/关键码域string other;/其它域;vector<Item<Type>*> dataList;信息学院张铭 编写Ó 所有， 或Pag

5、e 11tem9.1.1 顺序检索n 线性表里的所有，逐个进行关键码和给定值的比较 。n 若某个的关键码和给定值比较相等，则检索；n 否则检索失败(找遍了仍找不到)。n ：可以顺序、n 排序要求：无信息学院张铭 编写Ó 所有， 或Page 109.1 基于线性表的检索n 9.1.1 顺序检索n 9.1.2 二分检索n 9.1.3 分块检索信息学院张铭 编写Ó 所有， 或Page 9检索算法评估的几个问题n 衡量一个检索算法还需要考虑n 算法所需的量n 算法的复杂性n .信息学院张铭 编写Ó 所有， 或Page 8平均检索长度的例子n 假设线性表为（a, b, c）

6、检索a、b、c的概率分别为0.4、0.1、0.5n 顺序检索算法的平均检索长度为0.4×1+0.1×2+0.5×3 = 2.1n 即平均需要2.1次给定值与表中关键码值的比较才能找到待查元素信息学院张铭 编写Ó 所有， 或Page 73二分法检索图示lowmidhigh检索关键码18 low=1 high=9K=18第一次：mid=5; array5=35>18 high=4; (low=1)第二次：mid=2; array2=17<18 low=3; (high=4)第三次：mid=3; array3=18=18 mid=3；return

7、8信息学院张铭 编写Ó 所有， 或Page 18123456789151718223551608893二分法检索算法template <class Type> int BinSearch (vector<Item<Type>*>& dataList,int length,Type k) int low=1, high=length, mid;while (low<=high) mid=(low+high)/2;if (k<dataListmid->getKey()high = mid-1;/右缩检索区间else if (k

8、>dataListmid->getKey()low = mid+1;/左缩检索区间else return mid; /返回位置return 0; /检索失败，返回0信息学院张铭 编写Ó 所有， 或Page 179.1.2 二分检索法n 将任一元素dataListi .Key与给定值K比较n 三种情况：（1）Key = K，检索，返回dataListi（2） Key > K，若有则一定排在dataListi前（3） Key < K，若右则一定排在dataListi后n 缩小进一步检索的区间信息学院张铭 编写Ó 所有， 或Page 16顺序检索优缺点n

9、优点：元素可以直接加在表尾(1)n 缺点：检索时间太长(n)信息学院张铭 编写Ó 所有， 或Page 15顺序检索平均检索长度n 假设检索的概率为p，检索失败的概率为q=(1-p)n + 1AS L = p ×+ q × ( n + 1)2= p × n + 1 + (1 - p )( n + 1) 2= ( n + 1)(1 - p / 2 )n （n+1)/2 < ASL < (n+1)信息学院张铭 编写Ó 所有， 或Page 14顺序检索性能分析n 检索假设检索每个关键码是等概率的，Pi = 1/nn - 11 n - 1&#

10、229; Pi·(n - i) =å(n - i) i = 0ni = 0= n i = n + 1åi = 12n 检索失败假设检索失败时都需要比较n+1次（设置了一个监视哨）信息学院张铭 编写Ó 所有， 或Page 134分块检索分两个阶段n （1）确定待查元素所在的块n （2）在块内检索待查的元素分块检索索引顺序结构信息学院张铭 编写Ó 所有， 或Page 24索引表n 索引表n 各块中的最大关键码n 及各块起始位置n 可能还需要块中元素个数（每一块可能不满）n 索引表是一个递增有序表n 由于表是分块有序的信息学院张铭 编写Ó

11、所有， 或Page 23分块检索思想n “按块有序”n 设线性表中共有n个数据元素，将表分成b块n 不需要均匀n 每一块可能不满n 每一块中的关键码不一定有序n 但前一块中的最大关键码必须小于后一块中的最小关键码信息学院张铭 编写Ó 所有， 或Page 229.1.3 分块检索n 顺序与二分法的折衷n 既有较快的检索n 又有较灵活的更改信息学院张铭 编写Ó 所有， 或Page 21二分法检索性能分析（续）n 的平均检索长度为：1ji - 1 AS L =( å i × 2)n i = 1= n + 1 lo g ( n + 1) - 1n2»

12、lo g 2 ( n + 1) - 1(n > 50)n 优缺点n 优点：平均与最大检索长度相近，检索速度快n 缺点：要排序、顺序，不易更新(插/删)信息学院张铭 编写Ó 所有， 或Page 20二分法检索性能分析n 最大检索长度为5élog（2 n +1）ù2 17n 失败的检索长度是n 停止在内部叶结点élog （2 n + 1）ù或ëlog （2 n + 1）ûn 停止在外部空结点，则加1信息学院张铭 编写Ó 所有， 或Page 195分块检索性能分析(续4)n 若采用二分法检索确定 所在的子表，则检索

13、 时的平均检索长度为ASL= ASLb + ASLw» log2 (b+1)-1 + (s+1)/2» log2(1+n / s ) + s/2信息学院张铭 编写Ó 所有， 或Page 30分块检索性能分析(续3)n 当n=10,000时n 顺序检索5,000次n 二分法检索14次n 分块检索100次n 如果数据块（子表）存放在外存时，还会受到页块大小的制约n 此时往往以外存一个/的数据（一页）作为一块信息学院张铭 编写Ó 所有， 或Page 29分块检索性能分析(续2)n 假设在索引表中用顺序检索，在块内也用顺序检索ASL = b + 1ASL = s

14、 + 1b2w2ASL = b + 1 + s + 1 = b + s + 1222= n + s 2 +12 sn 当s= n 时，ASL取最小值，ASL = n +1 n信息学院张铭 编写Ó 所有， 或Page 28分块检索性能分析(续1)n 索引表是按块内最大关键码有序的， 且长度也不大，可以二分检索，也可以顺序检索n 各子表内各个 不是按 关键码有序，只能顺序检索信息学院张铭 编写Ó 所有， 或Page 27分块检索性能分析n 分块检索为两级检索n 先在索引表中确定待查元素所在的块；n 设在索引表中确定块号的时间开销是ASLbn 然后在块内检索待查的元素。n 在块中

15、查找的时间开销为ASLwn ASL(n) = ASLb + ASLw信息学院张铭 编写Ó 所有， 或Page 26分块检索索引顺序结构0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 172212133342443824486080744986link: 块内最大关键码Key: 块起始位置Size: 块内有效元素个数信息学院张铭 编写Ó 所有， 或Page 2506122248863656=9.3.0 散列中的基本问题n 基于关键码比较的检索n 顺序检索，=, !=n 二分法、树型 >, = , <n 检索是直接面向用户的操作n

16、当问题规模n很大时，上述检索的时间效率可能使得用户受n 最理想的情况n 根据关键码值，直接找到的地址n 不需要把待查关键码与候选集合的某些进行逐个比较信息学院张铭 编写Ó 所有， 或Page 369.3 散列检索n 9.3.0 散列中的基本问题n 9.3.1 散列函数n 碰撞的处理9.3.2 开散列方法9.3.3 闭散列方法9.3.4 闭散列表的算法实现n 9.3.5 散列方法的效率分析信息学院张铭 编写Ó 所有， 或Page 35实际实现用无符合长整数数组集元素个数N=40的集合，集35, 9, 7, 5, 3, 1表示为00 0000 0000 0000 0000 00

17、00 10000000 0000 0000 0000 0000 0010 1010 1010不够一个usigned long, 左补0信息学院张铭 编写Ó 所有， 或Page 34例：计算0到15之间所有的奇素数奇数：素数：奇素数：信息学院张铭 编写Ó 所有， 或Page 3300110000010100101112500011000101009.2 集合的检索n 用位向量来表示集合n 对于密集型集合（数据范围小，而集合中有效元素个数比较多）信息学院张铭 编写Ó 所有， 或Page 320011010100010100分块检索的优缺点n 优点：n 、删除相对较易n

18、 没有大量移动n 缺点：n 增加一个辅助数组的空间n 初始线性表分块排序n 当大量/删除时，或结点分布不均匀时，速度下降信息学院张铭 编写Ó 所有， 或Page 317信息学院张铭 编写Ó 所有， 或Page 42散列 地址 关键码 1 3w h ile14 w ith1 5until16 th en17 18 rep ea t19 20 21 22 23 24 2 5散 列地址 关键 码01an d23en d4e lse56if7b egin8d o910 g o11fo r12 arra y例子2例9.2：在集合S中增加4个关键码，集合S1 = S + else, a

19、rray, with, up要修改散列函数：散列函数的值为key中首尾字母在字母表中序号的平均值，即：int H3(key)char key; int i; i = 0;while (i<8) && (keyi!=0) i+;return(key0 + key(i-1) 2*a) /2 )信息学院张铭 编写Ó 所有， 或Page 41信息学院张铭 编写Ó 所有， 或Page 40散列地址 关键码 13 14 15 16 17 r e p e at 18 19 t h e n20 u n t i l21 22 w h i le (w i t h )23

20、24 25 散列地 址关键 码0a n d( ar r ay) 1be g in23d o4e n d (e l s e )5f or 6go 78i f910 11 12 例子1例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 39散列基本思想n 一个确定的函数关系

21、hn 以结点的关键码K为自变量n 函数值h(K)作为结点的地址n 检索时也是根据这个函数计算其位置n 通常散列表的空间是一个一维数组n 散列地址是数组的下标信息学院张铭 编写Ó 所有， 或Page 38由数组的直接寻址想到的n 例如， 指定下标的数组元素n 根据数组的起始 地址、以及数组下标值而直接计算出来的， 所花费的时间是O(1)n 与数组元素个数的规模n无关n 受此启发，计算机科学家发明了散列方法（Hash, 有人称“哈希”，还有称“杂凑”）散列是一种重要的方法n 也是一种常见的检索方法信息学院张铭 编写Ó 所有， 或Page 378常用散列函数n 1. 除余法2.

22、乘余取整法n 3. 平方取中法4. 数字分析法5. 基数转换法6. 折叠法7. ELFhash字符串散列函数信息学院张铭 编写Ó 所有， 或Page 48需要考虑各种因素n 关键码长度n 散列表大小n 关键码分布情况n 的检索频率n 信息学院张铭 编写Ó 所有， 或Page 47散列函数的选取原则n 运算尽可能简单n 函数的值域必须在表长的范围内n 尽可能使得关键码不同时，其散列函数值亦不相同信息学院张铭 编写Ó 所有， 或Page 469.3.1散列函数n 散列函数：把关键码值到位置的函数，通常用h来表示Address Hash ( key )信息学院张铭 编写

23、Ó 所有， 或Page 45散列技术的两个重要问题n 采用散列技术时需要考虑的两个首要问题是：n （1）如何构造(选择)使结点“分布均匀”的散列函数？n （2）一旦发生，用什么方法来解决？n 还需考虑散列表本身的组织方法信息学院张铭 编写Ó 所有， 或Page 44几个重要概念n 负载因子=n/mn 散列表的空间大小为mn 填入表中的结点数为nn 某个散列函数对于不相等的关键码计算出了相同的散列地址n 在实际应用中，不产生的散列函数极少存在n 同义词n 发生的两个关键码信息学院张铭 编写Ó 所有， 或Page 439乘余取整法示例n 设关键码 key = 1234

24、56, n = 10000且取 A = ( 5 -1) / 2 = 0.6180339，n 因此有hash(123456) = ë10000*(0.6180339*123456 % 1)û = ë10000 * (76300.0041151 % 1)û = ë10000 * 0.0041151û = 41信息学院张铭 编写Ó 所有， 或Page 542. 乘余取整法n 先让关键码 key 乘上一个常数A (0<A < 1)，提取乘积的小数部分n 然后，再用整数 n 乘以这个值，对结果向下取整，把它作为散列地址n

25、散列函数为：hash ( key ) = ë n * ( A * key % 1 ) ûn “A * key % 1”表示取 A * key 小数部分:A * key % 1 = A * key - ë A * key û信息学院张铭 编写Ó 所有， 或Page 53除余法的问题n 除余法的潜在缺点n 连续的关键码成连续的散列值n 虽然能保证连续的关键码不发生n 但也意味着要占据连续的数组单元n 可能导致散列性能的降低信息学院张铭 编写Ó 所有， 或Page 52M不用幂x mod 28 选择最右边8位n 若把M设置为2的幂n 那么，

26、h(x)x mod 2k 仅仅是x(用二进制表示)最右边的k个位(bit)n 若把M设置为10的幂n 那么，h(x)x mod 10k 仅仅是x(用十进制表示)最右边的k个十进制位(digital)n 缺点：散列值不依赖于x的全部比特位信息学院张铭 编写Ó 所有， 或Page 510M为什么不用偶数n 若把M设置为偶数n x是偶数，h(x)也是偶数n x是奇数，h(x)也是奇数n 缺点：分布不均匀n 如果偶数关键码比奇数关键码出现的概率大，那么函数值就不能均匀分布n 反之亦然信息学院张铭 编写Ó 所有， 或Page 501. 除余法n 除余法：用关键码x除以M(往往取散列表

27、长度)，并取余数作为散列地址。散列函数为：h(x) x mod Mn 通常选择一个质数作为M值n 函数值依赖于自变量x的所有位，而不仅仅是最右边k个低位n 增大了均匀分布的可能性n 例如，4093信息学院张铭 编写Ó 所有， 或Page 4910数字分析法（续3）n 位，仅9出现8次，n l 1 =（8-8/10）2×1+（0-8/10） 2 ×9=57.6n 位，仅9出现8次，n l 2 =（8-8/10）2×1+（0-8/10） 2 ×9=57.6n 位，0和2各出现两次，1出现4次n l 3 =（2-8/10）2×2+（4-8/

28、10） 2 ×1+ （0-8/10） 2×7 =17.6n 位，0和5各出现两次，1、2、6、8各出现1次n 位，0和4各出现两次，2、3、5、6各出现1次n 位，7和8各出现两次，0、1、5、9各出现1次n l 4 = l 5 = l 6 = （2-8/10）2×2+（1-8/10） 2 ×4+（0-8/10） 2 ×4 =5.6信息学院张铭 编写Ó 所有， 或Page 60数字分析法（续2）9 9 2 1 4 8位， l 1 = 57.609 9 1 2 6 9位， l 2 = 57.609 9 0 5 2 7位， l 3 = 1

29、7.609 9 1 6 3 0位， l 4 = 5.609 9 1 8 0 5位， l 5 = 5.609 9 1 5 5 8位， l 6 = 5.609 9 2 0 4 79 9 0 0 0 1 n 若散列表地址范围有 3 位数字, 取各关键码的位做为的散列地址n 也可以把第，和第位相加，舍去进位，变成一位数，与第，位合起来作为散列地址。还可以用其它方法信息学院张铭 编写Ó 所有， 或Page 59数字分析法（续1）n 计算各位数字中符号分布的均匀度 lk 的公式：rk2k = å(i - n / r)i =1n 其中， k 表示第 i 个符号在第 k 位上出i现的次数，

30、n n/r 表示各种符号在 n 个数中均匀出现的期望值。n 计算出的 lk 值越小，表明在该位 (第k 位) 各种符号分布得越均匀信息学院张铭 编写Ó 所有， 或Page 584. 数字分析法n 设有 n 个 d 位数，每一位可能有 r 种不同的符号n 这 r 种不同的符号在各位上出现的频率不一定相同n 可能在某些位上分布均匀些，每种符号出现的几率均等n 在某些位上分布不均匀，只有某几种符号经常出现n 可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址信息学院张铭 编写Ó 所有， 或Page 573. 平方取中法n 此时可采用平方取中法：先通过求关键码的平方来

31、扩大差别，再取其中的几位或其组合作为散列地址n 例如，n 一组二进制关键码：(00000100，00000110， 000001010，000001001，000000111)n 平方结果为：(00010000，00100100，01100010， 01010001，00110001)n 若表长为4个二进制位，则可取中间四位作为散列地址：(0100，1001，1000，0100，1100)信息学院张铭 编写 Ó 所有， 或Page 56乘余取整法参数取值的考虑n 若地址空间为p位，就取n=2pn 所求出的散列地址正好是计算出来的A * key % 1 = A * key - 

32、5; A * key û 值的小数点后最左p位（bit）值n 此方法的优点:对 n 的选择无关紧要n Knuth认为：A可以取任何值，与待 排序的数据特征有关。一般情况下 取黄金分割 ( 5 - 1) 2 最理想信息学院张铭 编写Ó 所有， 或Page 5511例：折叠法n 例9.6 如果一本书的编号为04-42-20586-4n 5 8 6 45 8 6 4n 4 2 2 00 2 2 4n +0 4+0 4n 1 0 0 8 86 0 9 2n h(key)=0088h(key)=6092n (a)移位叠加(b)分界叠加信息学院张铭 编写Ó 所有， 或Page

33、 66两种折叠方法n 两种叠加方法：n 移位叠加 把各部分的最后一位对齐相加n 分界叠加 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址信息学院张铭 编写 Ó 所有， 或Page 656. 折叠法n 关键码所含的位数很多，采用平方取中法计算太复杂n 折叠法n 将关键码分割成位数相同的几部分（最后一部分的位数可以不同）n 然后取这几部分的叠加和（舍去进位）作为散列地址信息学院张铭 编写Ó 所有， 或Page 64例：基数转换法n 例如，给定一个十进制数的关键码是(210485)10，把它看成以13为基数的十三 进制数(210485)13 ，再把它

34、转换为十进制(210485)13 = 2×135 + 1×134 + 4×132 + 8×13 + 5= (771932)10n 假设散列表长度是10000，则可取低4位1932作为散列地址信息学院张铭 编写Ó 所有， 或Page 635. 基数转换法n 把关键码看成是另一进制上的数后n 再把它转换成原来进制上的数n 取其中若干位作为散列地址n 一般取大于原来基数的数作为转换的基数，并且两个基数要互素信息学院张铭 编写Ó 所有， 或Page 62数字分析法（续4）n 数字分析法仅适用于事先明确知道表中所有关键码每一位数值的分布情况n

35、它完全依赖于关键码集合n 如果换一个关键码集合，选择哪几位数据要重新决定信息学院张铭 编写Ó 所有， 或Page 61121. 拉链法345678910 n 表中的空单元其实应该有特殊值标记出来，例如-1或INFIn 或者使得散列表中的内容就是指针，空单元则内容为空指针。n 同义词时，可以对同义词链排序信息学院张铭 编写Ó 所有， 或Page 72201277 9.3.2 开散列方法n 当碰撞发生时就拉出一条链，建立一个链表方式的同义词子表动态申请同义词的空间，适合于内存操作例：77、7、110、95、14、75、62 h(Key) = Key % 111. 拉链法n 2.

36、 桶式散列信息学院张铭 编写Ó 所有， 或Page 71：碰撞的处理开散列方法( open hashing，也称为拉链法，separate chaining )n 把发生的关键码在散列表主表之外n 闭散列方法( closed hashing，也称为开地址方法，open addressing )n 把发生的关键码在表中另一个槽内信息学院张铭 编写Ó 所有， 或Page 70散列函数的应用n 在实际应用中应根据关键码的特点，选用适当的散列函数n 有人曾用“ 赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化”n 若关键码不是整数而是字符串时，可以把每个字符

37、串转换成整数，再应用平方取中法信息学院张铭 编写Ó 所有， 或Page 69ELFhash函数特征n 长字符串和短字符串都很有效n 字符串中每个字符都有同样的作用n 对于散列表中的位置不可能产生不平均的分布信息学院张铭 编写Ó 所有， 或Page 687. ELFhash字符串散列函数n 用于UNIX系统V4.0“可执行格式”( Executable and Linking Format，即ELF )int ELFhash(char* key) unsigned long h = 0; while(*key) h = (h << 4) + *key+;unsig

38、ned long g = h & 0xF0000000L; if (g) h = g >> 24;h &= g;return h % M;信息学院张铭 编写Ó 所有， 或Page 6713桶式散列的磁盘性能分析n 一个查找平均访外次数等于桶内页块数k 的一半n 调桶目录表进入内存(假定目录表不在内存)n 为了寻找要求的必须逐个检查一个桶内各页块n 实际上是(k+1)/2n 对于修改、删除等运算尚需另一次访外，用于重新写回外存信息学院张铭 编写Ó 所有， 或Page 78桶式散列文件组织n 右图表示了一个具有B0个桶的散列文件1b1b2组织n 如果

39、B很小，桶目录表可放在内存b3n 如果B较大，要存放好 多页块，则桶目B-1录表就放到外存上b4b5b6桶目录表信息学院张铭 编写Ó 所有， 或Page 772. 桶式散列n 适合于磁盘的散列表n 基本思想:n 把一个文件的分为若干桶， 每个桶包含一个或多个页块n 一个桶内的各页块用指针连接起来，每个页块包含若干n 散列函数h(K)表示具有关键码值K的所在的桶号信息学院张铭 编写Ó 所有， 或Page 76溢出区静态链信息学院张铭 编写Ó 所有， 或Page 75拉链法不适于外存检索n 如果整个散列表在内存中，开散列方法比较容易实现n 如果散列表在磁盘中，用开散列

40、不太合适n 一个同义词表中的元素可能在不同的磁盘页中n 这就会导致在检索一个特定关键码值时引起多次磁盘，从而增加了检索时间n 桶式散列信息学院张铭 编写Ó 所有， 或Page 74拉链法性能分析n 给定一个大小为Mn个的表n 散列函数(在理想情况下)将把在表中M个位置平均放置，使得平均每一个链表中有n/M个n M>n 时，散列方法的平均代价就是(1)信息学院张铭 编写Ó 所有， 或Page 7314检索过程n 检索时也要像时一样遵循同样的策略n 重复解决过程n 找出在基位置没有找到的信息学院张铭 编写Ó 所有， 或Page 84闭散列表解决的基本思想（续）n

41、 当K时，若基地址上的结点已被别的数据元素占用n 则按上述地址序列依次探查，将找到的第一个开放的空闲位置di作为K的位置n 若所有后继散列地址都不空闲， 说明该闭散列表已满，报告溢出信息学院张铭 编写Ó 所有， 或Page 83闭散列表解决的基本思想n 当发生时，使用某种方法为关键码K生成一个散列地址序列d0，d1，d2，. di ，.dm-1n 其中d0=h（K）称为K的基地址地置n 所有di(0<i<m)是后继散列地址n 形成探查的方法不同，所得到的解决冲突的方法也不同信息学院张铭 编写Ó 所有， 或Page 829.3.3 闭散列方法n 把所有直接在散列表

42、中。n 每个关键码有一个基位置即h(key)，即由散列函数计算出来的地址n 如果要一个关键码，而另一个记录已经占据了R的基位置(发生碰撞)，n 那么就把R在表中的其它地址内，由解决策略确定是哪个地址信息学院张铭 编写Ó 所有， 或Page 81桶式散列的问题n 理想状况很难实现n 尤其当文件不断增长时，桶内的页块数也随之增多n 由于分布不均匀，有些桶内页块数可能过多，严重影响检索效率n 必要时需对文件进行重新组织n 改变散列函数n 增加桶目录表的大小信息学院张铭 编写Ó 所有， 或Page 80桶式散列的磁盘性能分析(续)n 最理想状况:n 每个桶仅由一个页块组成，假设目录

43、在外存n 这样只需访外二次(对检索)或三次(对其他运算)n 要求n 桶的个数大致等于存放所需的页块数n 散列函数值分布均匀信息学院张铭 编写Ó 所有， 或Page 791. 线性探查n 基本思想：n 如果的基位置位置被占用，那么就在表中下移，直到找到一个空位置。n 依次探查下述地址单元：d+1，d+2，M-1，0，1，.，d-1n 用于简单线性探查的探查函数是：p(K，i) = in 线性探查的优点n 表中所有的的候选位置位置都可以作为新信息学院张铭 编写ÓPage 87所有，或15改进线性探查n 每次跳过常数c个而不是1个槽n 探查序列中的第i个槽是(h(K) +ic)

44、mod Mn 基位置相邻的就进入同一个探查序列了n 探查函数是p(K，i) = i*cn 必须使常数c与M互素信息学院张铭 编写Ó 所有， 或Page 90散列表示例n M = 15, h(key) = key%13n 在理想情况下，表中的每个空槽都应该有相同的机会接收下一个要的n 下一条放在第11个槽中的概率是2/15n 放到第7个槽中的概率是11/信息学院张铭 编写Ó 所有， 或Page 899101213142625411251可能产生的问题n “”（clustering，或称为“堆积”）n 散列地址不同的结点，争夺同一后继散列地址n 小的可能汇大的n 导致很长的探查

45、序列信息学院张铭 编写Ó 所有， 或Page 88几种常见的闭散列方法1. 线性探查n 2. 二次探查n 3. 伪随机数序列探查4. 双散列探查法信息学院张铭 编写Ó 所有， 或Page 86探查序列n 和检索函数都假定每个关键码的探查序列中至少有一个 位置是空的n 否则可能会进入一个无限循环中n 也可以限制探查序列长度信息学院张铭 编写 Ó 所有， 或Page 8516例：伪随机数序列探查n 例：考虑一个大小为M = 13的表，perm0 = 2，perm1 = 3，perm2 = 7。n 假定两个关键码k1和k2，h(k1)=4，h(k2)=2n 探查序列n

46、k1的探查序列是4、6、7、11 、.n k2的探查序列是2、4、5、9 、.n 尽管k2会把k1的基位置作为第2个选择来探查，但是这两个关键码的探查序列此后就立即 了信息学院张铭 编写 Ó 所有， 或Page 96产生n个数的伪随机排列n void permute(int *array, int n) for (int i = 1; i <= n; i +)swap(arrayi-1, arrayRandom(i);信息学院张铭 编写Ó 所有， 或Page 953. 伪随机数序列探查n 探查函数p(K，i) = permi - 1n 这里perm是一个长度为M -

47、1的数组n 包含值从1到M - 1的随机序列信息学院张铭 编写Ó 所有， 或Page 94例：二次探查n 例：使用一个大小M = 13的表假定对于关键码k1和k2，h(k1)=3，h(k2)=2n 探查序列n k1的探查序列是3、4、2、7 、.n k2的探查序列是2、3、1、6 、.n 尽管k2会把k1的基位置作为第2个选择来探查，但是这两个关键码的探查序列此后就立即 了信息学院张铭 编写Ó 所有， 或Page 932. 二次探查n 探查序列依次为：12，-12，22 ，- 22，.，即探查地址是d2i-1 = (d +i2) % Md2i = (d i2) % Mn 用

48、于简单线性探查的探查函数是p(K，2i-1) = i*i p(K，2i) = - i*i信息学院张铭 编写Ó 所有， 或Page 92例：改进线性探查n 例如，c = 2，要关键码k1和k2，h(k1) = 3，h(k2) = 5n 探查序列n k1的探查序列是3、5、7、9、.n k2的探查序列就是5、7、9、.n k1和k2的探查序列还是纠缠在一起，从而导致了信息学院张铭 编写Ó 所有， 或Page 9117M和h2(k)选择方法n 方法1：选择M为一个素数，h2返回的值在1h2(K)M 1范围之间n 方法2：设置M = 2m，让h2返回一个1到2m之间的奇数值n 方法3：若M是素数，h1(K)=K mod Mn h2 (K) = K mod(M-2) + 1n 或者h2(K) = K / M mod(M-2) + 1n 方法4：若M是任意数，h1(K)=K mod p，(p是小于M的