前面我们学习了三种基本数据结构前面我们学习了三种基本数据结构:一般线性表一般线性表（数据元素、关系、操作无限制）（数据元素、关系、操作无限制）栈和队列栈和队列（操作有限制）（操作有限制）字符串字符串（数据元素有限制）（数据元素有限制）广义表和数组广义表和数组（参与关系有限制）（参与关系有限制）树和二叉树结构树和二叉树结构图结构图结构ADT的定义：的定义：数据结构的逻辑特性；数据结构的逻辑特性；数据结构上定义的操作；数据结构上定义的操作；ADT的虚拟实现：的虚拟实现：逻辑结构的虚拟实现（存储结构）逻辑结构的虚拟实现（存储结构）操作的虚拟实现（算法）；操作的虚拟实现（算法）；ADT应用举例：应用举例：讲授的方法讲授的方法:前面学习的每一种数据结构都定义了一前面学习的每一种数据结构都定义了一些常用的操作，如：初始化、访问某数些常用的操作，如：初始化、访问某数据元素等等，因此，研究操作的实现（据元素等等，因此，研究操作的实现（不是操作的定义）即算法也是数据结构不是操作的定义）即算法也是数据结构的范畴有两个操作在每个数据结构上、在计算有两个操作在每个数据结构上、在计算机应用中是非常重要的：机应用中是非常重要的：其一，确定元素的位置其一，确定元素的位置查找；查找；其二，将元素按某种顺序排列其二，将元素按某种顺序排列分类分类后面两章我们分别学习这两类操作的算后面两章我们分别学习这两类操作的算法（思想、效率、优缺点等等）；法（思想、效率、优缺点等等）；本章学习各种查找算法，了解算法的思想、本章学习各种查找算法，了解算法的思想、效率、优缺点、适用范围等等。
效率、优缺点、适用范围等等预备知识1、查找：在某一数据集合中查找数据元素是否存、查找：在某一数据集合中查找数据元素是否存 在，若存在，返回其位置，否则，返回在，若存在，返回其位置，否则，返回 失败信息失败信息2、查找表：被查找数据元素的集合（一般都是一、查找表：被查找数据元素的集合（一般都是一 种数据结构，元素的位置是指在该数种数据结构，元素的位置是指在该数 据结构中的逻辑位置，但是查找方法据结构中的逻辑位置，但是查找方法 还依赖与元素的存储，即与存储结构还依赖与元素的存储，即与存储结构 有关），一般是虚拟实现了的逻辑结有关），一般是虚拟实现了的逻辑结 构（数据结构构（数据结构+存储结构）存储结构）3、查找表的种类：、查找表的种类：静态查找表：数据集合在查找前后不变；静态查找表：数据集合在查找前后不变；动态查找表：数据集合在查找后会改变；动态查找表：数据集合在查找后会改变；注意：注意：查找表一般可以描述为：查找表一般可以描述为：数据对象数据对象D0：D0是具有相同特性的数据元素的是具有相同特性的数据元素的 集合每个数据元素含有类型相集合每个数据元素含有类型相 同的关键字，可唯一标识数据元同的关键字，可唯一标识数据元 素。
素数据关系数据关系R：数据元素同属一个集合（关系描述）：数据元素同属一个集合（关系描述）4、查找方法：、查找方法：查找表不同，查找方法就会不同有很多不同查找表不同，查找方法就会不同有很多不同的查找方法的查找方法5、查找算法的评价：、查找算法的评价：空间：占用的辅助空间少；空间：占用的辅助空间少；时间：时间少查找的基本操作是比较，因此时间：时间少查找的基本操作是比较，因此 时间主要体现为比较次数时间主要体现为比较次数查找成功：查找成功：最大比较次数最大比较次数MSL 平均比较次数平均比较次数ASL 查找失败：查找失败：最大比较次数最大比较次数MSL 平均比较次数平均比较次数ASL9.1 静态查找表的查找 静态查找表有很多种，查找方法也不一样，静态查找表有很多种，查找方法也不一样，下面介绍几种常见的静态查找表的查找方法下面介绍几种常见的静态查找表的查找方法一、静态查找表是顺序或链式存储的线性表一、静态查找表是顺序或链式存储的线性表 顺序查找顺序查找1、查找表的要求：线性表、查找表的要求：线性表2、查找方法：略、查找方法：略1、查找表的要求：、查找表的要求：3、特点：、特点：思想简单，对查找表要求少，适应面广；思想简单，对查找表要求少，适应面广；比较次数较大比较次数较大O(n)；（考虑查找概率不相等时应该如何处理？）（考虑查找概率不相等时应该如何处理？）二、静态查找表是二、静态查找表是顺序存储的、有序的顺序存储的、有序的线性表线性表 折半查找（折半查找（Fibonacci查找、插值查找）查找、插值查找）1、查找表的要求：顺序存储、有序的线性表、查找表的要求：顺序存储、有序的线性表2、查找方法：、查找方法：lowhigmid=(low+hig)/2x=Rmid OK!xRmid mid+1higR3、特点：、特点：对查找表要求多；对查找表要求多；比较次数较少比较次数较少O(log2n)；折半查找的过程可以用一棵二叉树表示，称之为折半查找的过程可以用一棵二叉树表示，称之为“折半查找的判定树折半查找的判定树”。
构造方法自己总结，构造方法自己总结，该树是唯一的吗？）该树是唯一的吗？）例如例如:折半查找在折半查找在n=11 时的判定树如下：时的判定树如下：一般情况下，表长为一般情况下，表长为n的折半查找的判定树的深度和的折半查找的判定树的深度和含有含有n个结点的完全二叉树的深度相同个结点的完全二叉树的深度相同假设假设 n=2h-1 并且查找概率相等则：并且查找概率相等则：在在n50时，可得近似结果：时，可得近似结果：三、静态查找表是树三、静态查找表是树 静态树查找静态树查找1、查找表的要求：二叉分类树、查找表的要求：二叉分类树2、查找方法：、查找方法：X与根比较：与根比较：相等：相等：OK！X根：根：在右子树上找在右子树上找 3、特点：、特点：类似折半，最大是树的深度；类似折半，最大是树的深度；等概率时，折半查找的判定树是最好的；等概率时，折半查找的判定树是最好的；不等概率时，概率高的应该靠近根不等概率时，概率高的应该靠近根四、静态查找表是分块索引表四、静态查找表是分块索引表 分块查找分块查找1、查找表的要求：顺序存储、分块有序、查找表的要求：顺序存储、分块有序2、查找方法：、查找方法：折半方法确定可能在的块；折半方法确定可能在的块；顺序查找确定元素；顺序查找确定元素；3、特点：、特点：要建立索引表；要建立索引表；效率介于折半和顺序之间；效率介于折半和顺序之间；9.2 动态查找表的查找动态查找表的查找 动态二叉分类树的查找动态二叉分类树的查找1、查找表的要求：二叉分类树、查找表的要求：二叉分类树2、查找方法：、查找方法：若二叉排序树为空，则查找不成功；否则若二叉排序树为空，则查找不成功；否则1）若给定值等于根结点的关键字，则查找成功；）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左）若给定值小于根结点的关键字，则继续在左 子树上进行查找；子树上进行查找；3）若给定值大于根结点的关键字，则继续在右）若给定值大于根结点的关键字，则继续在右 子树上进行查找。
子树上进行查找Btreenode *find(Btreenode *BST,elentype x)/在以在以BST为根指针的二叉排队为根指针的二叉排队 树中查找值为树中查找值为x的结点的结点 if(BST=NULL)return NULL;/查找失败查找失败 else if (BST-data=x)/查找成功查找成功 return BST;else if(BST-datax)/进入左子树查找进入左子树查找 return find(BST-left,x);else /进入右子树查找进入右子树查找 return find(BST-right,x);3、特点：、特点：与树的深度有关；与树的深度有关；对于每一棵特定的二叉排序树，均可按照平均对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的查找长度的定义来求它的ASL值，显然，由值值，显然，由值相同的相同的n个关键字构造所得的，不同形态的各棵个关键字构造所得的，不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可二叉排序树的平均查找长度的值不同，甚至可能差别很大，例如：能差别很大，例如：由关键字序列由关键字序列1，2，3，4，5构造而得的二叉构造而得的二叉排序树，排序树，ASL=（1+2+3+4+5）/5=3由关键字序列由关键字序列3，1，2，5，4构造而得的二叉构造而得的二叉排序树，排序树，ASL=（1+2+3+2+3）/5=2.2一般情况下，考虑含有一般情况下，考虑含有n个关键字可能出现的个关键字可能出现的n!种种序列出现的可能性相等。
序列出现的可能性相等不失一般性，假设某个序列中有不失一般性，假设某个序列中有k个关键字小于第个关键字小于第一个关键字，即有一个关键字，即有n-k-1个关键字大于第一个关键个关键字大于第一个关键字，由它构造的二叉排序树的平均查找长度是字，由它构造的二叉排序树的平均查找长度是n和和k的函数：的函数：P(n,k)(0kn-1)则含则含n个关键字的二叉排序树的平均查找长度：个关键字的二叉排序树的平均查找长度：而在等概率的情况下，而在等概率的情况下，由此：由此：可类似于解差分方程，此递归方程有解：可类似于解差分方程，此递归方程有解：从查找的角度看，希望由任意序列生成的二叉从查找的角度看，希望由任意序列生成的二叉排序树，其左、右子树的深度近似相等，但实际排序树，其左、右子树的深度近似相等，但实际上有上有47%的情况生成的二叉排序树非如此的情况生成的二叉排序树非如此那么，如何构造高度比较低的二叉分类树呢？那么，如何构造高度比较低的二叉分类树呢？9.3 平衡二叉树平衡二叉树一、平衡二叉树的定义一、平衡二叉树的定义1、定义：一棵分类二叉树是平衡的，当且仅当每个结点、定义：一棵分类二叉树是平衡的，当且仅当每个结点的左右子树的高度至多相差为的左右子树的高度至多相差为1。
由由G.M.Adelson_Velskii和和E.M.Landis给出的定义给出的定义AVL树递归定义：递归定义：（）空树是二叉分类树；（）空树是二叉分类树；（）它的左右子树都是二叉分类树，且左右子树（）它的左右子树都是二叉分类树，且左右子树的高度最多相差为；的高度最多相差为；、平衡因子：、平衡因子：左子树的高度右子树的高度，即左子树的高度右子树的高度，即 BF(t)=Hl-Hr 平衡二叉树中，对任意结点：平衡二叉树中，对任意结点：BF=、平衡二叉树的特点：、平衡二叉树的特点：其深度和其深度和log2n同数量级，即树的平均查找长度同数量级，即树的平均查找长度为为O(log2n);4、AVL树的构造和调整过程：树的构造和调整过程：（）基本原则：（）基本原则：按照二叉分类树的构造方法，构造过程中判断是否按照二叉分类树的构造方法，构造过程中判断是否为平衡二叉树（平衡因子），是，则继续构造；否则，为平衡二叉树（平衡因子），是，则继续构造；否则，按一定的原则（保持是二叉分类和平衡）将其调整为平按一定的原则（保持是二叉分类和平衡）将其调整为平衡，然后继续衡，然后继续插入过程中的调整原则：（）插入过程中的调整原则：二叉分类树在插入前平衡，插入一个结点后如果失去二叉分类树在插入前平衡，插入一个结点后如果失去平衡，则至少有一个结点的平衡因子变为或。
平衡，则至少有一个结点的平衡因子变为或若平衡因子，则左分支高于右分支；若平衡因子，则左分支高于右分支；若平衡因子，则右分支高于左分支；若平衡因子，则右分支高于左分支；失去平衡的四种情况：失去平衡的四种情况：型：左分支的左子树上插入，使之失去平衡因子型：左分支的左子树上插入，使之失去平衡因子平衡因子；平衡因子；BF=1BF=0BF=2BF=1BF=0插入插入BF=BF=BF=0特殊地：特殊地：BlBrAr h-1h-1BF=1BF=0BlBrAr h-1h-1BF=BF=插入插入BlBrAr h-1h-1BF=hBF=0型：右分支的右子树上插入，使之失去平衡因子型：右分支的右子树上插入，使之失去平衡因子平衡因子；平衡因子；BF=-1BF=0插入插入CABF=BF=BF=0特殊地：特殊地：BF=-2BF=0BF=-1BlBrAlh-1h-1BF=-1BF=0插入插入BlBrAlh-1h-1BF=-2BF=-1BrAlBlhh-1BF=h-1BF=0型：左分支的右子树上插入，使之失去平衡因子型：左分支的右子树上插入，使之失去平衡因子平衡因子；平衡因子；BF=1BF=0BF=2BF=1BF=0插入插入BF=BF=BF=0特殊地：特殊地：BF=2BF=1BF=0插入插入BlClAr h-1h-2BF=1BF=0CrBlClAr h-1h-1BF=2BF=0CrBlClAr h-1h-1BF=0BF=0CrBF=-1BlClAr h-1h-1BF=2BF=1Crh-1L型：右分支的左子树上插入，使之失去平衡因子型：右分支的左子树上插入，使之失去平衡因子平衡因子；平衡因子；BF=-1BF=0插入插入BCABF=BF=BF=0特殊地：特殊地：BF=-2BF=0BF=BF=-2BF=0BF=-1插入插入BrClAlh-1h-2BF=1BF=0Crh-1BF=0BrClAlh-1h-1BF=-2BF=1Crh-1BF=1BrClAlh-1h-1BF=-2BF=-1Crh-1BF=-1BrClAlh-1h-1BF=0BF=-1Crh-1BF=0略（参见教材略（参见教材236-238）5、算法：、算法：6、举例：有下列元素，构造平衡二叉树、举例：有下列元素，构造平衡二叉树 13,24,37,90,53132437RR型型24133713,24,37,90,532413379053RL型24133753905337909.3 平衡二叉树平衡二叉树二、平衡二叉树的查找二、平衡二叉树的查找1、查找过程：同二叉分类树一样！、查找过程：同二叉分类树一样！、效率分析：、效率分析：查找过程中和给定值进行比较的关键字的个数不查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。
超过平衡树的深度假设深度为假设深度为h的二叉平衡树上所含结点数的最小值的二叉平衡树上所含结点数的最小值为为Nh，则显然，则显然 Nh=Nh-1+Nh-2+1由此可以推导出：由此可以推导出：hlog（n）因此，在平衡树上进行查找的时间复杂度为因此，在平衡树上进行查找的时间复杂度为O(log(n)9.4 哈希查找哈希查找一、哈希技术介绍一、哈希技术介绍1、哈希技术的提出背景：、哈希技术的提出背景：一般的线性表，树中，记录在结构中的相对位置一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的因此，在结构中查找记录时需进行一系列和关键字的比较这一类查找方法建立在比较这一类查找方法建立在“比较比较“的基础上，查的基础上，查找的效率依赖于查找过程中所进行的比较次数找的效率依赖于查找过程中所进行的比较次数哈希哈希”是英文是英文HASH的音译，又翻译作的音译，又翻译作“散列散列”、“杂凑杂凑”等那么，有没有不用比较的查找方法？那么，有没有不用比较的查找方法？9.4 哈希查找哈希查找 理想的情况是能直接找到需要的记录，因此必须理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的在记录的存储位置和它的关键字之间建立一个确定的对应关系对应关系f，使每个关键字和结构中一个唯一的存储，使每个关键字和结构中一个唯一的存储位置相对应。
位置相对应因此，如果有一个函数，它能够根据要查找的关键因此，如果有一个函数，它能够根据要查找的关键字直接计算出要查找记录的地址，该地址的内容为空，字直接计算出要查找记录的地址，该地址的内容为空，则查找的元素不存在，否则，查找成功显然，这样的则查找的元素不存在，否则，查找成功显然，这样的查找不需要比较！查找不需要比较！基于这种思想的技术就是基于这种思想的技术就是HASH技术；技术；9.4 哈希查找哈希查找 哈希表最常见的例子是哈希表最常见的例子是以学生学号为关键字以学生学号为关键字的成的成绩表，号学生的记录位置在第一条，绩表，号学生的记录位置在第一条，2号学生的记号学生的记录位置在第二条，录位置在第二条，号学生的记录位置在第号学生的记录位置在第条条.如果我们以学生姓名为关键字，如何建立查找表，如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相应记录呢？使得根据姓名可以直接找到相应记录呢？其次，我们取姓名各个字的拼音字头字母的编号和为该其次，我们取姓名各个字的拼音字头字母的编号和为该记录的存储位置，例如吴军，记录的存储位置，例如吴军，wj=33，存储位置，存储位置33；吴晓燕，吴晓燕，wxy=72,存储位置为存储位置为72；a1b2c3d4e5f6g7h8i9j10k11l12m13n14o15p16q17r18s19t20u21v22w23x24y25z26首先，我们规定每个字母的编号：首先，我们规定每个字母的编号：9.4 哈希查找哈希查找显然存储地址从显然存储地址从378。
如果如果76个学生的姓名的拼音个学生的姓名的拼音字头字母都互不相同，则我们可以按这种方式存储这字头字母都互不相同，则我们可以按这种方式存储这些学生的信息，而且很容易的查找一个学生的信息些学生的信息，而且很容易的查找一个学生的信息例如：要查吴晓燕的信息，则计算例如：要查吴晓燕的信息，则计算wxy=72，第，第72个位个位置存储的就是该学生的信息置存储的就是该学生的信息如果我们有如果我们有m个空间，个空间，n个数据元素，个数据元素，n=m，且每个，且每个数据元素能按某种映射关系得到唯一的空间地址，则数据元素能按某种映射关系得到唯一的空间地址，则我们很容易的实现查找！我们很容易的实现查找！但是，千万不要忘了我们假设的前提：但是，千万不要忘了我们假设的前提：互不相同！互不相同！例如，如果学生中还有一个学生姓名为王新云，例如，如果学生中还有一个学生姓名为王新云，wxy=72怎么办？怎么办？9.4 哈希查找一、哈希技术介绍一、哈希技术介绍2、什么情况下使用、什么情况下使用HASH技术？技术？如果问题的数据元素已知，很容易地建立数据元素如果问题的数据元素已知，很容易地建立数据元素和存储地址之间的一一映射函数关系，和存储地址之间的一一映射函数关系，HASH技术是很技术是很简单的，简单的，HASH技术也就失去了意义，实际上技术也就失去了意义，实际上HSAH技技术是针对下类问题的：术是针对下类问题的：问题的数据元素的可用集合很大，而一个问题的问题的数据元素的可用集合很大，而一个问题的具体数据元素是取自该可用集合的一个很小的任意一具体数据元素是取自该可用集合的一个很小的任意一个集合，因此，解决问题时需要的空间大小是根据小个集合，因此，解决问题时需要的空间大小是根据小集合大小确定的，但是，如果要建立函数映射，函数集合大小确定的，但是，如果要建立函数映射，函数的定义域应该是大集合，而值域是由小集合确定的，的定义域应该是大集合，而值域是由小集合确定的，因此建立这样的一一映射是很困难的，所以才有了因此建立这样的一一映射是很困难的，所以才有了HASH技术。
技术9.4 哈希查找一、哈希技术介绍3、HASH类问题的描述：类问题的描述：假设问题可能用到的关键字集合为假设问题可能用到的关键字集合为U，|U|=n0，即该集合，即该集合的元素个数为的元素个数为n0，而一个问题实际用到的关键字集合为，而一个问题实际用到的关键字集合为S，|S|=n，nn0，且，且S是取自是取自U的任意一个子集合，表示的任意一个子集合，表示为为R1,R2,R3,.Rn，其关键字集合为，其关键字集合为K1,K2,.,Kn；T是解决问题需要的连续空间，它由是解决问题需要的连续空间，它由m个存储单元组成，个存储单元组成，表示为表示为T0.m-1，m n有一个函数有一个函数H，其定义域是，其定义域是key U，值域是，值域是i 0.m-1，它将关键字映射到存储空间地址上；它将关键字映射到存储空间地址上；H(key)=i key U,i 0.m-19.4 哈希查找哈希查找一、哈希技术介绍一、哈希技术介绍12nnn0H9.4 哈希查找哈希查找一、哈希技术介绍一、哈希技术介绍4、有关基本概念：、有关基本概念：（1）HASH函数：将关键字映射到存储空间地址的函数，函数：将关键字映射到存储空间地址的函数，记作：记作：H(key)（2）HASH地址：由地址：由HSAH函数计算出的关键字地址；函数计算出的关键字地址；（3）HASH表：存储记录的连续地址空间表：存储记录的连续地址空间T；（4）HASH造表：利用造表：利用HASH函数将记录存储到函数将记录存储到HASH表表 中的过程；中的过程；（5）HASH表的填充度（装填因子）：表的填充度（装填因子）：表中填入的记录数表中填入的记录数 =HASH表的长度表的长度9.4 哈希查找哈希查找一、哈希技术介绍一、哈希技术介绍（6）冲突：由于）冲突：由于HASH函数的定义域是函数的定义域是U，而，而S是是U的任的任 意一个小子集，映射地址空间是由意一个小子集，映射地址空间是由S的大小的大小 确定的，因此，对于不同的关键字可能得到确定的，因此，对于不同的关键字可能得到 相同的相同的HASH地址，即：地址，即：若若 key1 key2,而而 H(key1)=H(key2)，则称为，则称为 冲突。
冲突7）同义词：）同义词：若若 H(key1)=H(key2)，则，则key1和和key2互称互称 为同义词为同义词5、HASH技术的关键：技术的关键：HASH函数的构造函数的构造 解决冲突的方法解决冲突的方法9.4 哈希查找哈希查找一、哈希技术介绍一、哈希技术介绍5、HASH问题举例：问题举例：我们写程序时，可以用的标识符是一个很大集合（我们写程序时，可以用的标识符是一个很大集合（U）因为凡是符合语言词法定义的都是合法、可用的标因为凡是符合语言词法定义的都是合法、可用的标识符，但是对于你写的每一个程序，真正使用到的识符，但是对于你写的每一个程序，真正使用到的标识符却是一个很小的子集（标识符却是一个很小的子集（S），编译程序存储和），编译程序存储和处理程序时只要能存储和处理任意的小子集处理程序时只要能存储和处理任意的小子集S即可，即可，但是，要注意但是，要注意S的特点！的特点！例如：标准例如：标准PASCAL的标识符为字母开头的的标识符为字母开头的8个长度的个长度的字母数字串，则字母数字串，则|U|=C(26,1)*C(36,1)*7=1.09388 1012，而而一个程序中可能出现的标识符不会太多，一个程序中可能出现的标识符不会太多，1000足矣！即足矣！即|S|=1000。
9.4 哈希查找哈希查找二、哈希函数的构造方法二、哈希函数的构造方法1、直接定址法：、直接定址法：H(key)=key 或或 H(key)=a*key+b a,b为常数为常数特点：特点：*关键字必须是整数；关键字必须是整数；*地址集合和关键字集合大小相同，没有冲突；地址集合和关键字集合大小相同，没有冲突；*空间浪费大；空间浪费大；2、数字分析法：、数字分析法：H(key)=关键字的某进制的若干位组成关键字的某进制的若干位组成特点：特点：*要求关键字已知；要求关键字已知；*取几位，哪几位的原则是尽量避免冲突，取几位，哪几位的原则是尽量避免冲突，均匀性好；均匀性好；9.4 哈希查找哈希查找3、平方取中法：、平方取中法：H(key)=关键字平方后的中间几位关键字平方后的中间几位4、折叠法：、折叠法：H(key)=将关键字分割成位数相同的几部分，然后取将关键字分割成位数相同的几部分，然后取 这几部分的叠加和（舍去进位）这几部分的叠加和（舍去进位）特点：这是一种较常用的方法特点：这是一种较常用的方法关键字不一定全部知道；关键字不一定全部知道；*由于一个数平方后的中间几位和数的每一位相关，由于一个数平方后的中间几位和数的每一位相关，均匀性较好，取的位数与表长有关；均匀性较好，取的位数与表长有关；*乘和截取的代价较高；乘和截取的代价较高；特点：特点：*关键字位数很多，而且关键字中每一位上数字关键字位数很多，而且关键字中每一位上数字 分布大致均匀时，均匀性很好；分布大致均匀时，均匀性很好；9.4 哈希查找哈希查找5、除留余法：、除留余法：H(key)=key MOD P P是不大于是不大于m的素数，的素数，m是是 HASH表的长度；表的长度；6、随机数法：、随机数法：H(key)=Random(key)；Random位随机函数位随机函数特点：这是一种最简单、最常用的方法。
特点：这是一种最简单、最常用的方法P的选择很重要，选择不好会产生同义词；的选择很重要，选择不好会产生同义词；*P一般取位素数或不包含小于一般取位素数或不包含小于20的质数的合数；的质数的合数；HASH函数考虑的因素：函数考虑的因素：（1）计算）计算HASH函数的时间；函数的时间；（2）关键字的长度；）关键字的长度；（3）HASH表的长度；表的长度；（4）关键字的分布情况；）关键字的分布情况；（5）记录的查找频率；）记录的查找频率；9.4 哈希查找三、冲突的解决方法三、冲突的解决方法1、开放定址法：（闭散列）、开放定址法：（闭散列）发生冲突后，按一定的原则寻找新的地址：发生冲突后，按一定的原则寻找新的地址：Hi=(H(key)+di)MOD m i=1,2,.,k di为增量，为增量，m为为HASH表的长度；表的长度；di的取法：的取法：线性探测：线性探测：di=1,2,3,.,m-1 二次探测：二次探测：di=12,-12,22,-22,.,k2 解决冲突的策略分为两类：解决冲突的策略分为两类：(1)闭散列方法闭散列方法(Closed Hashing):同义词放在同义词放在HASH表表 的其他位置；的其他位置；(Open addressing,又称为开地址法又称为开地址法)(2)闭散列方法闭散列方法(Open Hashing):同义词放在同义词放在HASH表表 之外的空间中；之外的空间中；(Separate chaining,又称为拉链法又称为拉链法)9.4 哈希查找三、冲突的解决方法三、冲突的解决方法2、再造、再造HASH法：（闭散列）法：（闭散列）Hi=RHi(key)用一系列用一系列HASH函数计算地址函数计算地址 3、链地址法：（开散列）、链地址法：（开散列）将同义词存放在同一个链将同义词存放在同一个链表中；表中；012m-19.4 哈希查找4、建立公共溢出区法：、建立公共溢出区法：除了除了HASH表外，开辟一个公共溢出区，一旦冲表外，开辟一个公共溢出区，一旦冲突，将同义词放入公共溢出区；突，将同义词放入公共溢出区；HASH表表:0 1 2 m-10 1 2 v溢出表溢出表:9.4 哈希查找四、哈希查找四、哈希查找1、哈希查找的方法、哈希查找的方法给定关键字给定关键字 k：（1）用给定的）用给定的HASH函数计算出函数计算出k的的HASH地址；地址；i=H(key)（2）若该地址为空，则查找失败；）若该地址为空，则查找失败；否则，若否则，若 Ti=k,则查找成功，返回地址；则查找成功，返回地址；否则，按否则，按HASH造表时解决冲突时的造表时解决冲突时的 方法计算出新的地址；方法计算出新的地址；（3）重复（）重复（2）直到查找成功或失败。
直到查找成功或失败9.4 哈希查找哈希查找、哈希查找的算法、哈希查找的算法 参见教材参见教材259页页9.4 哈希查找3、举例：、举例：已知有一组元素：已知有一组元素：19,14,23,01,68,20,84,27,55,11,10,79HASH函数为：函数为：H(key)=key MOD 13，HASH表长度表长度为为16，构造，构造HASH表表（1）线性探测法解决冲突）线性探测法解决冲突 Hi=(H(key)+di)MOD 15 di=1,2,3,.,m-1关键字：关键字：19 14 23 01 68 20 84 27 55 1110 79地地 址：址：611013761311101 012345678910 11 12 13 14 1519HASH表：表：14230101 682084 848427 27 272755 55551110 101079 79 79 79 79 79 79 79799.4 哈希查找（2）二次探测法解决冲突）二次探测法解决冲突 Hi=(H(key)+di)MOD 15 di=12,-12,22,-22,.,k2 (k m/2)关键字：关键字：19 14 23 01 68 20 84 27 55 1110 79地地 址：址：611013761311101 012345678910 11 12 13 14 1519HASH表：表：142301 682084111084842727555510107979797979012779 79799.4 哈希查找（3）链地址法解决冲突）链地址法解决冲突关键字：关键字：19 14 23 01 68 20 84 27 55 1110 79地地 址：址：611013761311101 012345678910 11 12 13 14 15HASH表：表：1914231401682084275568111023799.4 哈希查找4、性能分析：、性能分析：若没有冲突：若没有冲突：O(1);有冲突，性能与下列因素有关：有冲突，性能与下列因素有关：HASH函数函数 解决冲突的方法解决冲突的方法 装填因子装填因子。