第九章检索PPT课件

1、 第九章第九章 检索检索任课教员：张任课教员：张 铭铭http:/ 版版权所有，转载或翻印必究权所有，转载或翻印必究北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 2n9.1 基本概念基本概念n9.2 线性表的检索线性表的检索n9.3 散列表的检索散列表的检索北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 3基本概念基本概念n检索：检索：在一组记录集合中找到关键码在一组记录集合中找到关键码值等于给定值的某个记录，或者找到值等于给定值的某个记录，或者找到关键码值符合特定条件的某些记录的关键码值符合特定条件

2、的某些记录的过程过程n检索的检索的效率效率非常重要非常重要n尤其对于大数据量尤其对于大数据量n需要对数据进行需要对数据进行特殊的存储处理特殊的存储处理北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4基本概念（续基本概念（续）n预排序预排序n排序算法本身比较费时排序算法本身比较费时n只是预处理（在检索之前已经完成）只是预处理（在检索之前已经完成）n建立索引建立索引n检索时充分利用辅助索引信息检索时充分利用辅助索引信息n牺牲一定的空间牺牲一定的空间n从而提高检索效率从而提高检索效率北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转

3、载或翻印必究 Page 5基本概念（续基本概念（续）n散列技术散列技术n把数据组织到一个表中把数据组织到一个表中n根据关键码的值来确定表中每个记录的位置根据关键码的值来确定表中每个记录的位置n缺点：缺点：n不适合进行范围查询不适合进行范围查询n一般也不允许出现重复关键码一般也不允许出现重复关键码n当散列方法不适合于基于磁盘的应用程当散列方法不适合于基于磁盘的应用程序时，我们可以选择序时，我们可以选择B树方法树方法北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 6平均检索长度平均检索长度(ASL) n关键码的比较关键码的比较n检索运算的主要操作检索运

4、算的主要操作n平均检索长度平均检索长度(Average Search Length)n检索过程中对关键码需要执行的平均检索过程中对关键码需要执行的平均比较次数比较次数n是衡量检索算法优劣的时间标准是衡量检索算法优劣的时间标准北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 7平均检索长度平均检索长度nASL是存储结构中对象总数是存储结构中对象总数n的函的函数，其定义为：数，其定义为： nPi 为检索第为检索第i个元素的个元素的概率概率nCi 为找到第为找到第i个元素所需的关键码值与给定值的个元素所需的关键码值与给定值的比较次比较次数数1niiiA S

5、 LP C北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 8 平均检索长度平均检索长度n假设线性表为（假设线性表为（a, b, c）检索）检索a、b、c的概率分别为的概率分别为0.4、0.1、0.5n顺序检索算法的平均检索长度为顺序检索算法的平均检索长度为0.41+0.12+0.53 = 2.1n即平均需要即平均需要2.1次给定值与表中关键次给定值与表中关键码值的比较才能找到待查元素码值的比较才能找到待查元素北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 9n衡量一个检索算法还需要考虑衡量一个检索算法还

6、需要考虑n算法所需的存储量算法所需的存储量n算法的复杂性算法的复杂性n.北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 109.1 基于线性表的检索基于线性表的检索n9.1.1 顺序检索顺序检索n9.1.2 二分检索二分检索n9.1.3 分块检索分块检索北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 11n针对线性表里的所有记录，逐个进针对线性表里的所有记录，逐个进行关键码和给定值的比较行关键码和给定值的比较 。n若某个记录的关键码和给定值比较相若某个记录的关键码和给定值比较相等，则检索成功等，则检索成

7、功 ；n否则检索失败否则检索失败( (找遍了仍找不到找遍了仍找不到) )。n存储：可以顺序、链接存储：可以顺序、链接n排序要求：无排序要求：无北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 12顺序检索算法顺序检索算法n/代码代码9-1 顺序检索的存储结构类型定义顺序检索的存储结构类型定义 template class Item public: Item(Type value):key(value) Type getKey() return key; /获取关键码值获取关键码值; void setKey(Type k) key=k; /设置关键码设

8、置关键码private:Type key; /关键码域关键码域string other; /其它域其它域; vectorItem* dataList;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 13“监视哨监视哨”顺序检索算法顺序检索算法n位置位置0用来做监视哨用来做监视哨,位置位置1到到length用来存储实际元素用来存储实际元素n检索成功时返回元素位置，检索失败时统一返回检索成功时返回元素位置，检索失败时统一返回0;/代码代码9-2 顺序检索算法顺序检索算法 template int SeqSearch(vectorItem*& d

9、ataList,int length, Type k) int i=length; /将第将第0个元素设为待检索值个元素设为待检索值 / 保证保证while循环一定终止循环一定终止 dataList0-setKey (k); /从后往前逐个比较从后往前逐个比较 while(dataListi-getKey()!=k) i-; return i; /返回元素位置返回元素位置北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 14顺序检索性能分析顺序检索性能分析n检索成功检索成功假设检索每个关键码是等概率的，假设检索每个关键码是等概率的，Pi = 1/nP

10、i = 1/nn检索失败检索失败假设检索失败时都需要比较假设检索失败时都需要比较n+1n+1次（设置了一个监视次（设置了一个监视哨哨）Piniinnniininin()()01101121北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 15顺序检索性能分析（续）顺序检索性能分析（续）n平均检索长度平均检索长度假设检索成功的概率为假设检索成功的概率为p p，检索失败的概率为检索失败的概率为q=(1-p)q=(1-p)，则平均检索长度为则平均检索长度为n（n+1)/2 ASL (n+1)n+1)/2 ASL K，说明待查元素若在表中，且一定排在，说明待

11、查元素若在表中，且一定排在dataListi之前之前 （3） Key K，说明待查元素若在表中，且一定排在，说明待查元素若在表中，且一定排在dataListi之后之后n因此，在一次比较之后，若没有找到待查元素（即情因此，在一次比较之后，若没有找到待查元素（即情况况1未出现），则可根据比较结果缩小进一步检索的未出现），则可根据比较结果缩小进一步检索的区间区间北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 18二分法检索算法二分法检索算法n/代码代码9-3 二分检索算法二分检索算法 template int BinSearch (vectorItem*

12、& dataList,int length,Type k) /low, high分别记录数组首尾位置分别记录数组首尾位置 int low=1, high=length, mid; while (low=high) mid=(low+high)/2; if (kgetKey() high = mid-1; /右缩检索区间右缩检索区间 else if (kdataListmid-getKey() low = mid+1; /左缩检索区间左缩检索区间 else return mid; /检索成功，返回元素位置检索成功，返回元素位置 return 0; /检索失败，返回检索失败，返回0 北京大

13、学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 19 检索关键码检索关键码1818。low=1; high=9; K=18low=1; high=9; K=18第一次：第一次：mid=5; array5=3518mid=5; array5=3518 high=4; (low=1) high=4; (low=1)第二次：第二次：mid=2; array2=1718mid=2; array2=17 50)n 50)n优缺点优缺点n优点：平均检索长度与最大检索长度相近，检索速度快优点：平均检索长度与最大检索长度相近，检索速度快n缺点：要排序、顺序存储，不易更新

14、缺点：要排序、顺序存储，不易更新( (插插/ /删删) )11ASL(2)11log(1)12log(1)12jiininnnn北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 229.1.3 分块检索n顺序与二分法的折衷顺序与二分法的折衷n既有较快的检索既有较快的检索n又有较灵活的更改又有较灵活的更改北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 23分块检索思想分块检索思想n“按块有序按块有序”n设线性表中共有设线性表中共有n个数据元素，将表分个数据元素，将表分成成b块块n不需要均匀不需要均匀n每一块

15、可能不满每一块可能不满n每一块中的关键码不一定有序每一块中的关键码不一定有序n但前一块中的最大关键码必须小于后但前一块中的最大关键码必须小于后一块中的最小关键码一块中的最小关键码北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 24n索引表索引表n各块中的最大关键码各块中的最大关键码n及各块起始位置及各块起始位置n可能还需要块中元素个数（每一块可可能还需要块中元素个数（每一块可能不满）能不满）n索引表是一个递增有序表索引表是一个递增有序表n由于表是分块有序的由于表是分块有序的北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻

16、印必究 Page 25分块检索分两个阶段分块检索分两个阶段n（1）确定待查元素所在的块）确定待查元素所在的块 n（2）在块内检索待查的元素）在块内检索待查的元素 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 26分块检索分块检索索引顺序结构索引顺序结构n索引表中每个索引表中每个索引项索引项有两个域有两个域n块内最大关键码块内最大关键码n块起始位置块起始位置北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 27分块检索性能分析分块检索性能分析n分块检索为两级检索分块检索为两级检索n先在索引表中先在索引表中

17、确定待查元素所在确定待查元素所在的块；的块； n设在索引表中确定块号的时间开销是设在索引表中确定块号的时间开销是ASLASLb bn然后然后在块内检索待查的元素。在块内检索待查的元素。 n在块中查找记录的时间开销为在块中查找记录的时间开销为ASLASLw wnASL(n) = ASL(n) = ASLASLb b + + ASLASLw w北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 28分块检索性能分析分块检索性能分析( (续续1)1)块内最大关键码块内最大关键码北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究

18、 Page 29分块检索性能分析分块检索性能分析( (续续2)2)n假设在索引表中用顺序检索，在块内假设在索引表中用顺序检索，在块内也用顺序检索也用顺序检索 n当当s= s= 时，时，ASLASL取最小值，取最小值， ASL = +1 ASL = +1 1ASL2bbnnn1ASL2sw211ASL122212bsbsnss北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 30分块检索性能分析分块检索性能分析( (续续3)3)n当当n=10,000n=10,000时时n顺序检索顺序检索5,0005,000次次n二分法检索二分法检索1414次次n分块检

19、索分块检索100100次次n如果数据块（子表）存放在外存时，还如果数据块（子表）存放在外存时，还会受到页块大小的制约会受到页块大小的制约n此时往往以外存一个此时往往以外存一个/ /读取的数据（一读取的数据（一页）作为一块页）作为一块北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 31分块检索性能分析分块检索性能分析( (续续4)4)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 32 分块检索的优缺点分块检索的优缺点n优点：优点：n插入、删除相对较易插入、删除相对较易n没有大量记录移动没有大量记录移动n

20、缺点：缺点：n增加一个辅助数组的存储空间增加一个辅助数组的存储空间n初始线性表分块排序初始线性表分块排序n当大量插入当大量插入/ /删除时，或结点分布不均删除时，或结点分布不均匀时，速度下降匀时，速度下降北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 339.2 散列检索散列检索n基于关键码比较的检索基于关键码比较的检索 n顺序检索，顺序检索，=, !=, !=n二分法、树型二分法、树型 , = , , = , n检索是检索是直接面向用户的操作直接面向用户的操作n当问题规模当问题规模n很大时，上述检索的时间效率可能使得用很大时，上述检索的时间效率可

21、能使得用户无法忍受户无法忍受n最理想的情况最理想的情况n根据关键码值，直接找到记录的存储地址根据关键码值，直接找到记录的存储地址n不需要把待查关键码与候选记录集合的某些记录进行逐个比不需要把待查关键码与候选记录集合的某些记录进行逐个比较较北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 34n例如，读取指定下标的数组元素例如，读取指定下标的数组元素n根据数组的起始存储地址、以及数组下标值根据数组的起始存储地址、以及数组下标值而直接计算出来的，所花费的时间是而直接计算出来的，所花费的时间是O(1)n与数组元素个数的规模与数组元素个数的规模n无关无关n受

22、此启发，计算机科学家发明了散列方受此启发，计算机科学家发明了散列方法法n散列是一种重要的存储方法散列是一种重要的存储方法n也是一种常见的检索方法也是一种常见的检索方法北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 35散列基本思想散列基本思想n一个确定的函数关系一个确定的函数关系h hn以结点的关键码以结点的关键码K K为自变量为自变量n函数值函数值h(K)h(K)作为结点的存储地址作为结点的存储地址n检索时也是根据这个函数计算其存储位置检索时也是根据这个函数计算其存储位置n通常散列表的存储空间是一个一维数组通常散列表的存储空间是一个一维数组n散列

23、地址是数组的下标散列地址是数组的下标北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 36例例9.19.1：已知线性表关键码集合为：已知线性表关键码集合为：S = and, begin, do, end, for, go, if, repeat, S = and, begin, do, end, for, go, if, repeat, then,then, until, while until, while可设散列表为：可设散列表为：char HT2268;char HT2268;散列函数散列函数H(key)H(key)的值，取为关键码的值，取为关

24、键码keykey中的第一个字母中的第一个字母在字母表在字母表a, b, c, ., za, b, c, ., z中的序号，即：中的序号，即：H(key)=key0 aH(key)=key0 a北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 37 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 38 例例9.29.2：在集合：在集合S S中增加中增加4 4个关键码，集合个关键码，集合S1 = S S1 = S + else, array, with, up+ else, array, with, up要修

25、改散列函数：散列函数的值为要修改散列函数：散列函数的值为keykey中首尾字中首尾字母在字母表中序号的平均值，即：母在字母表中序号的平均值，即：intint H3(key) H3(key)char key;char key;intint i; i; i = 0; i = 0; while (i8) & (keyi!=0) i+; while (i8) & (keyi!=0) i+; return(key0 + key(i-1) 2 return(key0 + key(i-1) 2* *a) /2 )a) /2 ) 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所

26、有，转载或翻印必究 Page 39 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 40n负载因子负载因子=n/m=n/mn散列表的空间大小为散列表的空间大小为m mn填入表中的结点数为填入表中的结点数为n nn冲突冲突n某个散列函数对于不相等的关键码计算出了相同的某个散列函数对于不相等的关键码计算出了相同的散列地址散列地址n在实际应用中，不产生冲突的散列函数极少存在在实际应用中，不产生冲突的散列函数极少存在n同义词同义词n发生冲突的两个关键码发生冲突的两个关键码北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 P

27、age 41n采用散列技术时需要考虑的两个首采用散列技术时需要考虑的两个首要问题是：要问题是：n（1）如何构造）如何构造(选择选择)使结点使结点“分布均分布均匀匀”的散列函数？的散列函数？n（2）一旦发生冲突，用什么方法来解）一旦发生冲突，用什么方法来解决决？n还需考虑散列表本身的组织方法还需考虑散列表本身的组织方法 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 42 9.2.1 9.2.1 散列函数散列函数n散列函数：把关键码值映射到存储散列函数：把关键码值映射到存储位置的函数，通常用位置的函数，通常用h h来表示来表示北京大学信息学院北京大学

28、信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 43散列函数的选取原则散列函数的选取原则n运算尽可能简单运算尽可能简单n函数的值域必须在表长的范围内函数的值域必须在表长的范围内n尽可能使得关键码不同时，其散列尽可能使得关键码不同时，其散列函数值亦不相同函数值亦不相同北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 44需要考虑各种因素需要考虑各种因素n关键码长度关键码长度n散列表大小散列表大小n关键码分布情况关键码分布情况n记录的检索频率记录的检索频率n 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或

29、翻印必究 Page 45常用散列函数选取方法常用散列函数选取方法n除余法除余法n乘余取整法乘余取整法n平方取中法平方取中法n数字分析法数字分析法n基数转换法基数转换法n折叠法折叠法nELFhash字符串散列函数字符串散列函数北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 4 除余法除余法n除余法除余法：用关键码用关键码x除以除以M(往往取散列表长往往取散列表长度度)，并取余数作为散列地址。散列函数为：，并取余数作为散列地址。散列函数为： h(x) x mod Mn通常选择一个通常选择一个质数质数作为作为M值值n函数值

30、依赖于自变量函数值依赖于自变量x的所有位，而不仅仅的所有位，而不仅仅是最右边是最右边k个低位个低位n增大了均匀分布的可能性增大了均匀分布的可能性北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 47n若把若把M设置为偶数设置为偶数nx是偶数是偶数，h(x)也是偶数也是偶数nx是奇数，是奇数，h(x)也是奇数也是奇数n缺点缺点：分布不均匀分布不均匀n如果偶数关键码比奇数关键码出现的概率大如果偶数关键码比奇数关键码出现的概率大，那么函数值就不能均匀分布那么函数值就不能均匀分布n反之亦然反之亦然北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权

31、所有，转载或翻印必究 Page 48n若把若把M设置为设置为2的幂的幂n那么，那么，h(x)x mod 2k 仅仅是仅仅是x(用二进制用二进制表示表示)最右边的最右边的k个位个位(bit)n若把若把M设置为设置为10的幂的幂n那么，那么，h(x)x mod 10k 仅仅是仅仅是x(用十进用十进制表示制表示)最右边的最右边的k个十进制位个十进制位(digital)n缺点缺点：散列值不依赖于散列值不依赖于x的全部比特位的全部比特位北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 49n除余法的潜在除余法的潜在缺点缺点n连续的关键码映射成连续的散列值连续的

32、关键码映射成连续的散列值n虽然能保证连续的关键码不发生冲突虽然能保证连续的关键码不发生冲突n但也意味着要占据连续的数组单元但也意味着要占据连续的数组单元n可能导致程序性能的降低可能导致程序性能的降低北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 50 乘余取整法乘余取整法hash ( key ) = n * ( A * key % 1 ) A * key % 1 = A * key - A * key 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 51乘余取整法示例乘余取

33、整法示例 ( 51)/2北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 52乘余取整法参数取值的考虑乘余取整法参数取值的考虑215 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 5 平方取中法平方取中法n此时可采用平方取中法：先通过求关键码的平此时可采用平方取中法：先通过求关键码的平方来扩大差别，再取其中的几位或其组合作为方来扩大差别，再取其中的几位或其组合作为散列地址散列地址n例如，例如，n一组二进制关键码：一组二进制关键码：(00000100(00000100，00

34、00000001100110，000000000101001010，000000000100101001，0000000000111)00111)n平方结果为：平方结果为：(00010000(00010000，0 001001000100100，0110001001100010，0 010100011010001，0 00110001) 0110001) n若表长为若表长为4 4个二进制位，则可取中间个二进制位，则可取中间四四位作为散列位作为散列地址：地址： (0100(0100，10011001，10001000，01000100，1100)1100)北京大学信息学院北京大学信息学院 版版权

35、所有，转载或翻印必究权所有，转载或翻印必究 Page 5 数字分析法数字分析法n设有设有 n 个个 d 位数，每一位可能有位数，每一位可能有 r 种不种不同的符号同的符号n这这 r 种不同的符号在各位上出现的频率种不同的符号在各位上出现的频率不一定相同不一定相同n可能在某些位上分布均匀些，每种符号出现可能在某些位上分布均匀些，每种符号出现的几率均等的几率均等n在某些位上分布不均匀，只有某几种符号经在某些位上分布不均匀，只有某几种符号经常出现常出现n可根据散列表的大小，选取其中各种符可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址号分布均匀的若干位作为散列地址北京

36、大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 55数字分析法（续数字分析法（续1 1）rikikrn12)/( ki北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 56北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 57数字分析法（续数字分析法（续3 3）北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 58数字分析法（续数字分析法（续4 4）北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或

37、翻印必究 Page 5 基数转换法基数转换法n把关键码看成是另一进制上的数后把关键码看成是另一进制上的数后n再把它转换成原来进制上的数再把它转换成原来进制上的数n取其中若干位作为散列地址取其中若干位作为散列地址n一般取大于原来基数的数作为转换一般取大于原来基数的数作为转换的基数，并且两个基数要互素的基数，并且两个基数要互素北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 60n例如，给定一个十进制数的关键码是例如，给定一个十进制数的关键码是(210485)(210485)1010，把它看成以，把它看成以1313为基数的

38、十三为基数的十三进制数进制数(210485)(210485)1313 ，再把它转换为十进，再把它转换为十进制制 (210485)13 = 2135 + 1134 + 4132 + 813 + 5 = (771932)10n假设散列表长度是假设散列表长度是1000010000，则可取低，则可取低4 4位位19321932作为散列地址作为散列地址北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 6 折叠法折叠法n关键码所含的位数很多，采用平方取中关键码所含的位数很多，采用平方取中法计算太复杂法计算太复杂n折叠法折叠法n将关

39、键码分割成位数相同的几部分（最后将关键码分割成位数相同的几部分（最后一部分的位数可以不同）一部分的位数可以不同）n然后取这几部分的叠加和（舍去进位）作然后取这几部分的叠加和（舍去进位）作为散列地址为散列地址北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 62n两种叠加方法：两种叠加方法：北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 63 n例例9.6 如果一本书的编号为如果一本书的编号为0-442-20586-4n 5 8 6 4 5 8 6 4 4 2 2 0 0 2 2 4 + 0 4 + 0 4

40、1 0 0 8 8 6 0 9 2h(key)=0088 h(key)=6092(a)移位叠加移位叠加 (b)分界叠加分界叠加 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 6 ELFhash字符串散列函数字符串散列函数n用于用于UNIX系统系统V4.0“可执行链接格可执行链接格式式”( Executable and Linking Format，即即ELF )int ELFhash(char* key) unsigned long h = 0; while(*key) h = (h 24; h &= g; return

41、h % M;北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 65n长字符串和短字符串都很有效长字符串和短字符串都很有效n字符串中每个字符都有同样的作字符串中每个字符都有同样的作用用n对于散列表中的位置不可能产生对于散列表中的位置不可能产生不平均的分布不平均的分布北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 66散列函数的应用散列函数的应用北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 67碰撞的处理碰撞的处理n开散列方法开散列方法( open hashin

42、g，也称为也称为拉链法拉链法，separate chaining )n把发生冲突的关键码存储在散列表主把发生冲突的关键码存储在散列表主表之外表之外n闭散列方法闭散列方法( closed hashing，也称为也称为开地址方法开地址方法，open addressing )n把发生冲突的关键码存储在表中另一把发生冲突的关键码存储在表中另一个槽内个槽内北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 68 9.2.2 9.2.2 开散列方法开散列方法n当碰撞发生时就拉出一条链，建立当碰撞发生时就拉出一条链，建立一个链表方式的同义词子表一个链表方式的同义词子

43、表 n动态申请同义词的空间，适合于动态申请同义词的空间，适合于内存操作内存操作n例：例： 77、7、110、95、14、75、62 h(Key) = Key % 11 h(Key) = Key % 11北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 6 拉链法拉链法n表中的空单元其实应该有特殊值标记出来，例如表中的空单元其实应该有特殊值标记出来，例如-1-1或或INFINITYINFINITYn或者使得散列表中的内容就是指针，空单元则内容为空指针。或者使得散列表中的内容就是指针，空单元则内容为空指针。n插入同义词时，

44、可以对同义词链排序插入插入同义词时，可以对同义词链排序插入北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 70n给定一个大小为给定一个大小为M M存储存储n n个记录的表个记录的表n散列函数散列函数( (在理想情况下在理想情况下) )将把记录在将把记录在表中表中M M个位置平均放置，使得平均每一个位置平均放置，使得平均每一个链表中有个链表中有n/Mn/M个记录个记录nMn Mn 时，散列方法的平均代价就是时，散列方法的平均代价就是(1)(1)北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 71n如果整个

45、散列表存储在内存中，开如果整个散列表存储在内存中，开散列方法比较容易实现散列方法比较容易实现n如果散列表存储在磁盘中，用开散如果散列表存储在磁盘中，用开散列不太合适列不太合适n一个同义词表中的元素可能存储在不一个同义词表中的元素可能存储在不同的磁盘页中同的磁盘页中n这就会导致在检索一个特定关键码值这就会导致在检索一个特定关键码值时引起多次磁盘访问，从而增加了检时引起多次磁盘访问，从而增加了检索时间索时间北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 72 桶式散列桶式散列 n适合于存储于磁盘的散列表适合于存储于磁盘的散列表n基本思想

46、基本思想:n把一个文件的记录分为若干存储桶，把一个文件的记录分为若干存储桶，每个存储桶包含一个或多个页块每个存储桶包含一个或多个页块n一个存储桶内的各页块用指针连接起一个存储桶内的各页块用指针连接起来，每个页块包含若干记录来，每个页块包含若干记录n散列函数散列函数h(K)表示具有关键码值表示具有关键码值K的的记录所在的存储桶号记录所在的存储桶号北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 73桶式散列桶式散列n下图表示了一个具有下图表示了一个具有B个存储桶的散列文个存储桶的散列文件组织件组织n如果如果B很小，存储桶目录表可放在内存很小，存储桶目录

47、表可放在内存n如果如果B较大，要存放好多页块，则存储桶目较大，要存放好多页块，则存储桶目录表就放到外存上录表就放到外存上北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 74 n计算关键码计算关键码K对应的散列函数值对应的散列函数值i= h(K)，得到得到存储桶号存储桶号i n调存储桶目录表中包含第调存储桶目录表中包含第i个存储桶目录的页个存储桶目录的页块进入内存块进入内存n得到第得到第i个存储桶的第一个页块的地址个存储桶的第一个页块的地址n根据这个地址把相应的页块调入内存根据这个地址把相应的页块调入内存n在这页块中顺序扫描每一个记录，检查有无关在这

48、页块中顺序扫描每一个记录，检查有无关键码值等于键码值等于K的记录，的记录，n若找到了就结束查找若找到了就结束查找n若找不到就在该页块的头上找到链指针，从而找出若找不到就在该页块的头上找到链指针，从而找出i号存储桶的下一个页块地址，把下一个页块调入号存储桶的下一个页块地址，把下一个页块调入内存，以同样的方式查找内存，以同样的方式查找n以此类推，直到找出关键码值等于以此类推，直到找出关键码值等于K的记录或断定的记录或断定不存在关键码值等于不存在关键码值等于K的记录的记录(即找完桶中所有页即找完桶中所有页块块)为止为止北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究

49、 Page 75桶式散列文件组织桶式散列文件组织 北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 76桶式散列文件的修改桶式散列文件的修改n假定我们要修改关键码值为假定我们要修改关键码值为K的记录的一的记录的一个或多个字段个或多个字段n若要修改的字段中有一些是关键码的一若要修改的字段中有一些是关键码的一部分，则这样的修改部分，则这样的修改相当于删除加插入相当于删除加插入n如果修改的字段不涉及关键码字段，则如果修改的字段不涉及关键码字段，则n首先查找这个记录，若找到就按要求进行修首先查找这个记录，若找到就按要求进行修改，并写回该修改后的记录改，并写回

50、该修改后的记录(即把包含该修即把包含该修改后记录的页块写回外存改后记录的页块写回外存)，n若找不到，则表示出错若找不到，则表示出错n因为修改一个不存在的记录是没有意义的因为修改一个不存在的记录是没有意义的北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 77桶式散列文件的插入桶式散列文件的插入n查找与要插入记录具有相同关键码值查找与要插入记录具有相同关键码值K的记录的记录n若找到，则表示出错若找到，则表示出错n如找不到这个记录，则在该存储桶如找不到这个记录，则在该存储桶(即即h(K)号号桶桶)的各页块中找一个空子块的各页块中找一个空子块，把要插入的记

51、把要插入的记录放进去录放进去n若找不到一个空子块若找不到一个空子块n则向文件系统申请一个新页块给此桶，新块头存入则向文件系统申请一个新页块给此桶，新块头存入一个空指针一个空指针n在该桶的最后一个页块的块头上存入指向新页块的在该桶的最后一个页块的块头上存入指向新页块的指针，把新页块链上指针，把新页块链上n把要插入的记录放在新页块的第一个子块中把要插入的记录放在新页块的第一个子块中北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 78桶式散列文件的删除桶式散列文件的删除n首先利用查找过程查找被删除的记录首先利用查找过程查找被删除的记录n若找不到，则表示出

52、错，因为要删除一个文若找不到，则表示出错，因为要删除一个文件中不存在的记录是没有意义的件中不存在的记录是没有意义的n若找到，则把该记录的删除标记置为若找到，则把该记录的删除标记置为0，表，表示该记录已被删除示该记录已被删除n该被删记录所占子块是否允许重新使用该被删记录所占子块是否允许重新使用?n这要看有否来自其他地方的指针指向该子块这要看有否来自其他地方的指针指向该子块n引用计数位引用计数位北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 79桶式散列文件的删除桶式散列文件的删除(续续)n如果文件中的记录不受其它条件约束如果文件中的记录不受其它条件约

53、束n当要被删除的记录不是桶中最后一个记当要被删除的记录不是桶中最后一个记录时录时n可以将桶内最后一个记录移入被删记录的子可以将桶内最后一个记录移入被删记录的子块块n这样既达到了删除的目的，又可以节省存储这样既达到了删除的目的，又可以节省存储n当桶内最后一个页块的记录被移空时，当桶内最后一个页块的记录被移空时，可将该页块交回给文件系统，以备后用可将该页块交回给文件系统，以备后用北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 80桶式散列的磁盘访问性能分析桶式散列的磁盘访问性能分析 n一个查找一个查找平均访外次数约为桶内页块数平均访外次数约为桶内页块数

54、k的一半的一半n调存储桶目录表进入内存调存储桶目录表进入内存(假定目录表不在假定目录表不在内存内存)n为了寻找要求的记录必须逐个检查一个桶内为了寻找要求的记录必须逐个检查一个桶内各页块各页块n实际上是实际上是(k+1)/2n对于修改、插入、删除等运算尚需对于修改、插入、删除等运算尚需另一另一次访外次访外，用于重新写回外存，用于重新写回外存北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 81桶式散列的磁盘访问性能分析桶式散列的磁盘访问性能分析(续续)n最理想状况最理想状况:n每个桶仅由一个页块组成，每个桶仅由一个页块组成，n这样只需访外二次这样只需访

55、外二次(对检索对检索)或三次或三次(对其他对其他运算运算)n要求要求n存储桶的个数大致等于记录存放所需的页存储桶的个数大致等于记录存放所需的页块数块数n散列函数值分布均匀散列函数值分布均匀北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 82n理想状况很难实现理想状况很难实现n尤其当文件不断增长时，桶内的页块数也随尤其当文件不断增长时，桶内的页块数也随之增多之增多n由于分布不均匀，有些桶内页块数可能过多，由于分布不均匀，有些桶内页块数可能过多，严重影响检索效率严重影响检索效率n必要时需对文件进行重新组织必要时需对文件进行重新组织n改变散列函数改变散列

56、函数n增加存储桶目录表的大小增加存储桶目录表的大小北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 839.2.3 9.2.3 闭散列方法闭散列方法n把所有记录直接存储在散列表中。把所有记录直接存储在散列表中。n每个记录关键码有一个基位置即每个记录关键码有一个基位置即h(key)h(key)，即由散列函数计算出来的地址即由散列函数计算出来的地址n如果要插入一个关键码如果要插入一个关键码，而另一个记录而另一个记录已经占据了已经占据了R R的基位置的基位置( (发生碰撞发生碰撞) )，n那么就把那么就把R R存储在表中的其它地址内，由冲存储在表中的其它地

57、址内，由冲突解决策略确定是哪个地址突解决策略确定是哪个地址北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 84闭散列表解决冲突的基本思想闭散列表解决冲突的基本思想n当冲突发生时，使用某种方法为关当冲突发生时，使用某种方法为关键码键码K生成一个散列地址序列生成一个散列地址序列 d0，d1，d2，. di ，.dm-1n其中其中d0=h（K）称为称为K的基地址地置的基地址地置n所有所有di(0im)是后继散列地址是后继散列地址n形成探查的方法不同，所得到的解决冲形成探查的方法不同，所得到的解决冲突的方法也不同突的方法也不同北京大学信息学院北京大学信息学

58、院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 85n当插入当插入K时，若基地址上的结点时，若基地址上的结点已被别的数据元素占用已被别的数据元素占用n则按上述地址序列依次探查，将则按上述地址序列依次探查，将找到的第一个开放的空闲位置找到的第一个开放的空闲位置di作作为为K的存储位置的存储位置n若所有后继散列地址都不空闲，若所有后继散列地址都不空闲，说明该闭散列表已满，报告溢出说明该闭散列表已满，报告溢出北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 86检索过程检索过程n检索时也要像插入时一样遵循同样检索时也要像插入时一样遵循同样的

59、策略的策略n重复冲突解决过程重复冲突解决过程n找出在基位置没有找到的记录找出在基位置没有找到的记录北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 87探查序列探查序列n插入和检索函数都假定每个关键码插入和检索函数都假定每个关键码的探查序列中至少有一个存储位置的探查序列中至少有一个存储位置是空的，否则它们就会进入一个无是空的，否则它们就会进入一个无限循环中限循环中北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 8 线性探查线性探查 n基本思想：基本思想：n如果记录的基位置存

60、储位置被占用，那么就如果记录的基位置存储位置被占用，那么就在表中下移，直到找到一个空存储位置。在表中下移，直到找到一个空存储位置。n依次探查下述地址单元：依次探查下述地址单元：d+1，d+2，.，M-1，0，1，.，d-1 n用于简单线性探查的探查函数是：用于简单线性探查的探查函数是： p(Kp(K，i) = ii) = in线性探查的优点线性探查的优点n表中所有的存储位置都可以作为插入新记录表中所有的存储位置都可以作为插入新记录的候选位置的候选位置北京大学信息学院北京大学信息学院 版版权所有，转载或翻印必究权所有，转载或翻印必究 Page 89线性探查示例线性探查示例n例例9.7：已知一组关键码为（：已知一组关键码为（26，3