数据结构JAVA语言描述习题答案[刘小晶等主编]第8章查找[Java版].pptVIP

基本思想是：除基本的存储区(称为基本表)之外，另建一个公共溢出区(称为溢出表)，当不发生冲突时，数据元素可存入基本表中；当发生冲突时，不管哈希地址是什么，数据元素都存入溢出表。查找时，对给定值K通过哈希函数计算出哈希地址i，先与基本表对应的存储单元相比较，若相等，则查找成功；否则，再到溢出表中进行查找。 主要思想是：当发生冲突时，再用另一个哈希函数来得到一个新的哈希地址，若再发生冲突，则再使用另一个函数，直至不发生冲突为止。 预先需要设置一个哈希函数的序列： Hi=RHi(key) (i=1,2,…,k)。 作业 作业 作业 将所有哈希地址相同的记录 都链接在同一链表中。 0 1 2 3 4 5 6 14 01 36 19 82 23 11 68 55 ? ? ? ? ? ? ? ASL成功=(1 × 6 +2×2+3)/9=13/9 例如:同前例的关键字，哈希函数设为 H(key)=key MOD 7 ASL不成功=(1×4 +2 + 3)/7=9/7 8.4.2 处理冲突的方法-链地址法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 8.4.2 处理冲突的方法-公共溢出法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 8.4.2 处理冲突的方法-再哈希法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 例如:以关键字5，4，2，8，6，9构造一 棵平衡二叉树。 5 4 2 4 2 5 8 6 6 5 8 4 2 向右旋转 一次 先向右旋转 再向左旋转 8.3.2 平衡二叉树-构造 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 4 2 6 5 8 9 6 4 2 8 9 5 向左旋转一次 继续插入关键字 9 8.3.2 平衡二叉树-构造 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。 8.3.2 平衡二叉树-查找性能分析 在二叉平衡树上进行查找时， 查找过程中和给定值进行比较的关键字的个数和 log2(n) 相当。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 一、哈希表的定义 二、常用的哈希函数 三、处理冲突的方法 四、哈希表的查找和性能分析 8.4 哈希表查找 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 以上两节讨论的表示查找表的各种结构的共同特点： 查找的过程: 查找的效率: 为给定值按某种顺序和记录集合中各个关键字进行比较的一个过程 记录在表中的位置和它的关键字之间不存在一个确定的关系 取决于和给定值进行比较的关键字个数。 8.4.1 哈希表的定义 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile . Copyright 2004-2011 Aspose Pty Ltd. 用这类方法表示的查找表，其平均查找长度都不为零。 不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。 8.4.1 哈希表的定义 Evaluation only