(2)散列在实际应用中的性能分析。 5.授课提示 开展硏究型教学,挖掘知识背后的内容,通过提出问题、探讨方法、研究思想、比较性 能,培养学生的创新意识、创新能力。 下面是检索的重点和难点内容的讲授注意事项 (1)基于线性表的检索算法 基于线性表的顺序检索、二分检索和分块检索这三种不同实现方法各有优缺点。其中, 顺序检索效率最低但限制最少,二分检索效率最高但限制多,而分块检索则介于上述二者之 间。应注意对三种检索算法的效率进行分析 在实际应用中,可根据表的具体情况进行选择,需要综合考虑检索效率、插入删除频率 (2)散列函数的设计 采用散列技术需要考虑的两个首要问题是,如何构造使结点“分布均匀”的散列函数, 以及一旦发生冲突用什么方法解决。此外,还需考虑散列表本身的组织方法。 常用的散列函数,包括除余法、乘余取整法、平方取中法、数字分析法、基数转换法 折叠法、 ELFhash字符串散列函数。讲授中着重介绍这些散列函数的基本思想以及各自的特 点,使同学们在实际使用中能够根据应用条件选取合适的散列函数。 3)散列表冲突解决策略 冲突解决技术可分为两大类,即开散列方法和闭散列方法。两者的不同之处在于:开散 列法把发生冲突的关键码存储在散列表主表之外,而闭散列把发生冲突的关键码存储在表中 另一个槽内。闭散列方法中有以下几种常见的形成探査的方法,即线性探查法、二次探查法。 讲授中应使学生理解冲突解决方法的基本原理,引导其思考其各自的效率、特点和适用 的条件。注意分析开散列方法(包括拉链法和桶式散列)和闭散列方法的空间需求和平均检 索长度,注意分析负载因子对检索效率的影响。开散列方法非常简单、易于实现,删除也极 为方便;经过精心设计的闭散列效率比开散列稳定。开散列方法的效率最好,实际系统中大 多使用开散列方法 (4)闭散列方法、散列探查方法 闭散列方法中,一旦发生冲突,发生冲突的关键码存储在散列表中的另一个槽内。根据 发生冲突时形成探查的方法不同,所得到的解决冲突的方法也不同。 本章介绍了几种常见的闭散列方法,包括线性探査、二次探査、伪随机数序列探査、爽 散列探査法。讲授中介绍各种散列方法的基本思想,注重分析各种方法的优缺点 本章还介绍了闭散列方法的不同实现方式,还介绍了闭散列的插入、检索和删除算法的 实现,分析了使用“墓碑”带给闭散列插入和删除算法性能上的改进。 6.课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向,设计验证型、探索型、综合 应用型的习题和上级题,帮助学生更好地掌握检索算法的基本原理,训练学生的创新思维能 力训练、工程实践能力。 检索可以安排46道书面作业,1道综合上机实习题 通过书面练习检査学生对各种散列方法、散列函数和散列探査方法的理解。设计与学科（2）散列在实际应用中的性能分析。 5．授课提示 开展研究型教学，挖掘知识背后的内容，通过提出问题、探讨方法、研究思想、比较性 能，培养学生的创新意识、创新能力。 下面是检索的重点和难点内容的讲授注意事项。 （1）基于线性表的检索算法 基于线性表的顺序检索、二分检索和分块检索这三种不同实现方法各有优缺点。其中， 顺序检索效率最低但限制最少，二分检索效率最高但限制多，而分块检索则介于上述二者之 间。应注意对三种检索算法的效率进行分析。 在实际应用中，可根据表的具体情况进行选择，需要综合考虑检索效率、插入删除频率 等。 （2）散列函数的设计 采用散列技术需要考虑的两个首要问题是，如何构造使结点“分布均匀”的散列函数， 以及一旦发生冲突用什么方法解决。此外，还需考虑散列表本身的组织方法。 常用的散列函数，包括除余法、乘余取整法、平方取中法、数字分析法、基数转换法、 折叠法、ELFhash 字符串散列函数。讲授中着重介绍这些散列函数的基本思想以及各自的特 点，使同学们在实际使用中能够根据应用条件选取合适的散列函数。 （3）散列表冲突解决策略 冲突解决技术可分为两大类，即开散列方法和闭散列方法。两者的不同之处在于：开散 列法把发生冲突的关键码存储在散列表主表之外，而闭散列把发生冲突的关键码存储在表中 另一个槽内。闭散列方法中有以下几种常见的形成探查的方法，即线性探查法、二次探查法。 讲授中应使学生理解冲突解决方法的基本原理，引导其思考其各自的效率、特点和适用 的条件。注意分析开散列方法（包括拉链法和桶式散列）和闭散列方法的空间需求和平均检 索长度，注意分析负载因子对检索效率的影响。开散列方法非常简单、易于实现，删除也极 为方便；经过精心设计的闭散列效率比开散列稳定。开散列方法的效率最好，实际系统中大 多使用开散列方法。 （4）闭散列方法、散列探查方法 闭散列方法中，一旦发生冲突，发生冲突的关键码存储在散列表中的另一个槽内。根据 发生冲突时形成探查的方法不同，所得到的解决冲突的方法也不同。 本章介绍了几种常见的闭散列方法，包括线性探查、二次探查、伪随机数序列探查、爽 散列探查法。讲授中介绍各种散列方法的基本思想，注重分析各种方法的优缺点。 本章还介绍了闭散列方法的不同实现方式，还介绍了闭散列的插入、检索和删除算法的 实现，分析了使用“墓碑”带给闭散列插入和删除算法性能上的改进。 6．课后练习和实习 融合经典的理论教学内容与学科的前沿新技术和发展方向，设计验证型、探索型、综合 应用型的习题和上级题，帮助学生更好地掌握检索算法的基本原理，训练学生的创新思维能 力训练、工程实践能力。 检索可以安排 4-6 道书面作业，1 道综合上机实习题。 通过书面练习检查学生对各种散列方法、散列函数和散列探查方法的理解。设计与学科