北京大学：《数据结构与算法》课程教学资源（实验班讲义）第九章 检索

分块检索的优缺点 92集合的检索 优点: 用位向量来表示集合 插入、删除相对较易 对于密集型集合(数据范围小,而 没有大量记录移动 集合中有效元素个数比较多) ■缺点: 增加一个辅助数组的存储空间 初始线性表分块排序 00110100001 当大量插入/删除时,或结点分布不均 匀时,速度下降 叔新有,盘 张 例:计算0到15之间所有的奇素数 实际实现用无符合长整数数组 奇数:012345678910112131415 全集元素个数N=40的集合,集 010f0d10101o1o 合{359753,1}表示为 000000000000000000000000 00 000 o00000000000000000000010 奇素数: 不够一个 signed long,左补0 订恤 张铝 权新有,种 张帖 93散列检索 9.3.0散列中的基本问题 9.3.0散列中的基本问题 基于关键码比较的检索 9.31散列函数 二分法、树型 令碰撞的处理 检索是直接面向用户的操作 上述检索的时间效率可 △9.32开散列方法 能使得用户无法 .33闭散列方法 最理想的情况 Q9.34闭散列表的算法实现 根据关健码值,直接找到记录的存储地址 待查关键码与候选记录集合的某些记录进 △935散列方法的效率分析 学恤息 权新有,种

6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 分块检索的优缺点 „ 优点： „ 插入、删除相对较易 „ 没有大量记录移动 „ 缺点： „ 增加一个辅助数组的存储空间 „ 初始线性表分块排序 „ 当大量插入/删除时，或结点分布不均 匀时，速度下降 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 9.2 集合的检索 „ 用位向量来表示集合 „ 对于密集型集合（数据范围小，而 集合中有效元素个数比较多） 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 例：计算0到15之间所有的奇素数 奇数： 素数： 奇素数： 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 1 0 0 0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15 0 4 6 8 10 12 14 1 9 15 2 3 5 7 11 13 0 2 4 6 8 10 12 14 1 9 15 3 5 7 11 13 1 3 5 7 9 11 13 15 2 3 5 7 11 13 3 5 7 11 13 & = 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 实际实现用无符合长整数数组 „ 全集元素个数N=40的集合，集 合{35, 9, 7, 5, 3, 1}表示为 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0010 1010 1010 不够一个usigned long, 左补0 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 9.3 散列检索 „ 9.3.0 散列中的基本问题 „ 9.3.1 散列函数 „ 碰撞的处理 „ 9.3.2 开散列方法 „ 9.3.3 闭散列方法 „ 9.3.4 闭散列表的算法实现 „ 9.3.5 散列方法的效率分析 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 9.3.0 散列中的基本问题 „ 基于关键码比较的检索 „ 顺序检索，==, != „ 二分法、树型 >, == , < „ 检索是直接面向用户的操作 „ 当问题规模n很大时，上述检索的时间效率可 能使得用户无法忍受 „ 最理想的情况 „ 根据关键码值，直接找到记录的存储地址 „ 不需要把待查关键码与候选记录集合的某些记录进 行逐个比较

由数组的直接寻址想到的 散列基本思想 例如,读取指定下标的数组元 一个确定的函数关系h 以结点的关键码K为自变量 函数值h(K作为结点的存储地址 与数组元囊个数的规模n无关 ■检索时也是根据这个函数计算其存储位 猫经楼 通常散列表的存储空间是一个一维数组 种重要的存储方法 散列地址是数组的下标 也是一种常见的检索方法 叔新有,盘 张 列盐类膏 散列地她类萄码 例子1 例91:已知线性表关健码集合为 S=iand, begin, do, end, for, go, if, repeat, then, until, while 可设散列表为 char HT2 26I8I 散列函数H(key)的值,取为关健码key中的 个字母在字母表{a,b,c,….x}中的序 订恤 张铝 张帖 歡列地址关健码 歐列地址关管码 例子2 例92:在集合S中增加4个关健码,集合S1=S+ 要修改散列函数:散列函数的值为key中首尾字 母表中序号的平均值,即 学恤息 权新有,种

7 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 37 由数组的直接寻址想到的 „ 例如，读取指定下标的数组元 素 „ 根据数组的起始存储地址、以及 数组下标值而直接计算出来的， 所花费的时间是O(1) „ 与数组元素个数的规模n无关 „ 受此启发，计算机科学家发明 了散列方法（Hash, 有人称“哈 希”，还有称“杂凑”）散列是一 种重要的存储方法 „ 也是一种常见的检索方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 38 散列基本思想 „ 一个确定的函数关系h „ 以结点的关键码K为自变量 „ 函数值h(K)作为结点的存储地址 „ 检索时也是根据这个函数计算其存储位 置 „ 通常散列表的存储空间是一个一维数组 „ 散列地址是数组的下标 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 39 例子1 例9.1：已知线性表关键码集合为： S = { and, begin, do, end, for, go, if, repeat, then, until, while} 可设散列表为： char HT2[26][8]; 散列函数H(key)的值，取为关键码key中的第一 个字母在字母表{a, b, c, ..., z}中的序号，即： H(key)=key[0] – ‘a’ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 40 例 子 1表 散列地址 关键码 散列地址 关键码 0 and (array) 13 1 begin 14 2 15 3 do 16 4 end (else) 17 repeat 5 for 18 6 go 19 then 7 20 u ntil 8 if 21 9 22 w hile (w ith) 10 23 11 24 1 2 2 5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 41 例子2 例9.2：在集合S中增加4个关键码，集合S1 = S + { else, array, with, up} 要修改散列函数：散列函数的值为key中首尾字 母在字母表中序号的平均值，即： int H3(key) char key[]; int i; { i = 0; while ((i<8) && (key[i]!=‘\0’)) i++; return((key[0] + key(i-1) – 2*’a’) /2 ) } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 42 例 子 2表 散列地址 关键码 散列地址 关键码 0 13 w hile 1 and 14 w ith 2 15 until 3 end 16 then 4 else 17 5 18 repeat 6 if 19 7 begin 20 8 do 21 9 22 10 go 23 11 for 24 1 2 arra y 2 5

几个重要概念 散列技术的两个重要问题 负载因子a=n/ 散列表的空间大小为m 用散列技术时需要考虑的两个首 填入表中的结点数为 要问题是: 冲突 )如何构造选择)使结点“分布均 某个散列函数对于不相等的关健码计算出了相同的 匀”的散列函数? 在实际应用中,不产生冲突的散列函数极少存在 (2)一旦发生冲突,用什么方法来解 同义词 决 发生冲突的两个关健 还需考虑散列表本身的组织方法 叔新有,盘 张 9.3.1散列函数 散列函数的选取原则 散列函数:把关键码值映射到 ■运算尽可能简单 存储位置的函数,通常用h来表 ■函数的值域必须在表长的范围内 ■尽可能使得关键码不同时,其散列 Address Hash( key 函数值亦不相同 订恤 张铭趣 张帖 需要考虑各种因素 常用散列函数选取方法 关键码长度 令1.除余法 散列表大小 令2.乘余取整法 关键码分布情况 令3.平方取中法 记录的检索频率 Q4.数字分析法 5.基数转换法 6.折叠法 Q7. ELFhash字符串散列函数 权新有,种

8 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 43 几个重要概念 „ 负载因子α=n/m „ 散列表的空间大小为m „ 填入表中的结点数为n „ 冲突 „ 某个散列函数对于不相等的关键码计算出了相同的 散列地址 „ 在实际应用中，不产生冲突的散列函数极少存在 „ 同义词 „ 发生冲突的两个关键码 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 44 散列技术的两个重要问题 „ 采用散列技术时需要考虑的两个首 要问题是： „ （1）如何构造(选择)使结点“分布均 匀”的散列函数？ „ （2）一旦发生冲突，用什么方法来解 决？ „ 还需考虑散列表本身的组织方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 45 9.3.1 散列函数 „ 散列函数：把关键码值映射到 存储位置的函数，通常用h来表 示 Address ＝ Hash ( key ) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 46 散列函数的选取原则 „ 运算尽可能简单 „ 函数的值域必须在表长的范围内 „ 尽可能使得关键码不同时，其散列 函数值亦不相同 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 47 需要考虑各种因素 „ 关键码长度 „ 散列表大小 „ 关键码分布情况 „ 记录的检索频率 „ … 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 48 常用散列函数选取方法 „ 1. 除余法 „ 2. 乘余取整法 „ 3. 平方取中法 „ 4. 数字分析法 „ 5. 基数转换法 „ 6. 折叠法 „ 7. ELFhash字符串散列函数