(7.4.1)--(22)《数据结构》教案.pdf

1 第第7章章 查找查找(共共 6 时，包括实训内容时，包括实训内容)课题课题 7.4 散列表 理论理论课时课时 1 学时 实实训训课时课时 1 学时 教学内容教学内容 散列表的定义、散列函数的构造方法、处理冲突的方法、散列表的查找与分析 教学目标教学目标 理解散列表的定义、掌握散列函数的构造方法、处理冲突的方法、散列表的查找与分析 教学重点教学重点 散列表的定义、散列函数的构造方法、处理冲突的方法 教学难点教学难点 散列函数的构造方法、处理冲突的方法 教学教学活动及主要活动及主要内容内容 学生活动学生活动 一、创设一、创设情境情境，导入新课（，导入新课（2 分钟）（分钟）（直接导入法直接导入法）导入：前面讨论的查找表，在查找时需通过给定值和记录关键字进行比较来实现，查找的效率主要取决于和给定值进行比较的关键字个数。对于频繁使用的查找表，我们希望平均查找长度为零或尽量接近零，即不经过任何比较，可直接存取所查记录。这就必须知道所查关键字在表中的位置。也就是说，记录在表中位置和其关键字之间存在一种确定的关系。计算机如何实现这种查找结构？下面我们来学习一下 二、新课二、新课讲解讲解（共共计计 16 分分钟）（讲解法、提问法、钟）（讲解法、提问法、演示演示法）法）7.4 散列表散列表 7.4.1 散列表的定义散列表的定义 在一般情况下需要在关键字集和地址集之间建立一个映射关系，以 H(key)作为关键字为 key 的记录在表中的位置，通常称这个函数 H(key)为散列函数或哈希函数。例如，设散列函数为 H(key)2/)1)()(AASCASC 第一字母，为图7.17(a)中的关键字序列构造表长为 13 的散列表，结果如图 7.17(b)所示。激 发 学 生学习 散 列 表的兴趣。学 生 要 理解散 列 表 的相关概念 2 图 7.17 关键字序列及其构造的散列表 散列函数是一个映象，即将关键字的集合映射到某个地址集合上，它很容易产生冲突。即21keykey，而)2()1(keyHkeyH。通常把这种具有不同关键字而具有相同散列地址的对象称作同义词同义词，由同义词引起的冲突称为同义词冲突同义词冲突。散列表存储的基本思想是：设要存储的对象个数为 n，设置一个长度为m(mn)的连续内存单元，以线性表中每个对象的关键字 key 为自变量，通过散列函数，把每个 key 值映射为内存单元的地址(或称数组下标)，即 H(key)的值，并把该对象存储在这个内存单元中。H(key)的值称为散列地址散列地址或哈希地址哈希地址。把这样构造的表存储结构称为散列表或哈希表。(hash table)。7.4.2 散列函数的构造方法散列函数的构造方法 1.直接定址法直接定址法 散列函数为关键字的线性函数6)(keyakeyH。直接定址所得地址集合与关键字集合的大小相同。对于不同的关键字不会发生冲突。但实际中能使用这种散列函数的可能性很少。2数字分析法数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成(k1，k2，kn)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。一般用于能预先估计出所有关键字的每一位上各种数字出现的频度的情况。3.平方取中法平方取中法 若关键字的每一位都有某些数字重复出现频度很高的现象，则先求关键字的平方值，以通过“平方”扩大差别，一个数平方后的中间几位受到整个关键字中各个数位的影响，可增加随机性。4.折叠法折叠法 若关键字的位数特别多，则可将其分割成几部分，然后取它们的叠加和为散列地址。叠加法有移位叠加和间界叠加两种处理方法。移位叠加是将关键字分割后的几个部分按最低位右对齐进行叠加，结果作为地址。间界叠加是按照每组的个数来回周折进行折叠，结果作为地址。叠加后要舍弃进位。5.随机数法随机数法 通过随机函数对每个关键字产生一个随机数作为散列地址：学 生 应 掌握散 列 函 数常见 的 构 造方法 3 6.除留余数法除留余数法 用关键字 key 除以一个小于或等于散列表长度 m 的整数 p 后得到的余数作为散列地址：pkeykeyH%)()(mp 一般的，p 为不大于 m 的质数或为不含 20 以下的两个质因数的乘积。7.4.3 处理冲突的方法处理冲突的方法 1.开放地址法开放地址法 所谓开放地址开放地址就是散列表中尚未被占用的地址。开放地址法就是为产生冲突的关键字所对应的记录求得一个地址序列：HsHHH,210 ),10(是表长mms H0,H1,H2,Hs（0sm-1，m 是表长）其中)是散列函数)()(0keyHkeyHH)s21i()%)(，是增量，iiidmdkeyHH 按此序列不断探测，直到找到空闲地址为止。增量 di有 3 种取法：（1）线性探测再散列：,4,3,2,1diiid即 （2）二次探测再散列，也称平方探测再散列：22222,2,2,11iiidd di=i2 即 di=12，-12，22，-22，（3）随机探测再散列，di是一组伪随机数列。【例例 78】关键字集合 key=12,39,18,24,33,21，散列函数为除留余数法，p=9，设表长为 9，则采用开放地址法中线性探测再散列（di=i）作为解决冲突的方法，得到的散列表表 7.3 所示。H(12)=3。H(39)=3，冲突，取 H1=(H(39)+1)%9=4。H(18)=0。H(24)=6。H(33)=6，冲突，取 H1=(H(33)+1)%9=7。H(21)=3，冲突，H1=(H(21)+1)%9=4，仍冲突，取 H2=(H(21)+2)%9=5。表 7.3 例 7.8 记录序列的散列地址表（线性探测再散列）地址 0 1 2 3 4 5 6 7 8 关键字 18 12 39 21 24 33 探查次数 1 1 2 3 1 2 若采用开放地址法中二次线性探测再散列作为冲突的解决办法，得到的散列表如表 7.4 所示。H(12)=3。学 生 应 掌握以下3种处理冲 突 的 方法并动手练习 4 H(39)=3，冲突，取 H1=(H(12)+12)%9=4。H(18)=0。H(24)=6。H(33)=6,冲突，取 H1=(H(33)+12)%9=7。H(21)=3,冲突，取 H1=(H(21)+12)%9=4，仍冲突，再取 H2=(H(21)-12)%9=2。表 7.4 例 7.8 记录序列的散列地址表（二次探测再散列）地址 0 1 2 3 4 5 6 7 8 关键字 18 21 12 39 24 33 探查次数 1 3 1 2 1 2 2.链地址法链地址法 链地址法链地址法，又称拉链法和外部链接法，是将所有散列地址相同的记录都链接在同一链表中。因此，在这种方法中，散列表的每个元素中存放的不再是对象，而是相应同义词单链表的头指针。与开放地址法相比，它有几个优点：(1)链地址肯定不会产生二次聚集，平均查找长度较短。(2)各链表上的记录空间动态申请，比较适合用于造表前无法确定表长的情况。(3)开放地址法为了避免冲突，有时需要增大表的长度，造成空间的浪费，而链地址法中只增加了结点的指针域，可忽略不计，因此节省空间。(4)链地址法中增加或删除一个结点时操作易于实现。【例例 79】对关键字集合 key=12，39，18，24，33，21，若散列函数为除留余数法，p=9，设表长为 9，则用拉链法解决冲突所得散列表如图 7.19 所示。图 7.19 例 7.9 数据产生的散列表 3建立公共溢出区建立公共溢出区 为了解决冲突，可另外创建一个线性表，将所有与散列表中的关键字发生冲突的记录都加入到该表中。这样的线性表就称为公共溢出区公共溢出区。*7.4.4 散列表的查找与分析散列表的查找与分析 散列表的查找过程和造表过程一致。假设采用开放地址法处理冲突，散列表为 rm(m 为散列表的表长)，则查找过程如下：对于给定值 key，计算散列地址；iH(key)。若 ri为空标记，则查找不成功；若 ri,key=key 则查找成功。否则，求下一地址 Hi，直至 rH为空标记或已搜索了表中的所有单元(查找不成功)，或 rHiKey=key(查找成功)为止。课堂思政：课堂思政：学习学习散列表散列表，要要善于善于发现发现事物事物之间之间的的映射映射关系关系，总结总结事物发展规律事物发展规律。三三、归纳总结，再度提升归纳总结，再度提升（1 分钟）（讲解法）分钟）（讲解法）1.散列表的定义 学 生 要 理解散 列 表 的查找 与 分 析方法 5 2.散列函数的构造方法 3.处理冲突的方法 4.散列表的查找与分析 四四、作业作业，预习任务预习任务（1 分钟）（激趣法）分钟）（激趣法）课后习题P213，散列表相关习题。预习：8.1-8.2 排序的基本概念和插入排序 6 板 书 设 计 7.4 7.4 散列表散列表 7.4.1 散列表的定义散列表的定义 7.4.2 散列函数的构造方法散列函数的构造方法 1.直接定址法直接定址法 2.数字分析法数字分析法 3.平方取中法平方取中法 4.折叠法折叠法 5.随机数法随机数法 6.除留余数法除留余数法 7.4.3 处理冲突的方法处理冲突的方法 1.开放地址法开放地址法 2.2.链地址法链地址法 3.建立公共溢出区建立公共溢出区 7.4.4 散列表的查找与分析散列表的查找与分析