《数据结构-查找.ppt》由会员分享，可在线阅读，更多相关《数据结构-查找.ppt（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、CH9 查找n查找的基本概念查找的基本概念n9.1 静态查找表静态查找表u9.1.1 顺序查找顺序查找u9.1.2 有序表的查找有序表的查找u9.1.3 索引顺序表的查找索引顺序表的查找n9.2 动态查找表动态查找表u9.2.1 二叉排序树和平衡二叉树二叉排序树和平衡二叉树u9.2.2 B和和B树树u小结小结n9.3 哈希表哈希表n本章总结本章总结查找的基本概念n1.查找表查找表n2.查找查找u关键字关键字l主关键字主关键字l次关键字次关键字u查找：根据某个给定的值，在表中确定一个其关键字等查找：根据某个给定的值，在表中确定一个其关键字等于给定值于给定值 的记录或数据元素。的记录或数据元素。l
2、查找成功查找成功l查找失败查找失败查找的基本概念n3.查找表的分类查找表的分类u静态查找表静态查找表u动态查找表动态查找表n4.衡量查找算法效率的标准衡量查找算法效率的标准u平均查找长度平均查找长度ASL (Average Search Length)u查找成功时的平均查找长度查找成功时的平均查找长度查找的基本概念n5.本章数据元素类型与比较运算的符号约定本章数据元素类型与比较运算的符号约定u数据类型定义数据类型定义 typedef struct KeyType key;ElemTypeu关键字比较的符号约定关键字比较的符号约定EQ(a,b)LT(a,b)LQ(a,b)查找的基本概念n6.查找
3、的基本方法查找的基本方法比较式查找法比较式查找法计算式查找法计算式查找法基于线性表的查找法基于线性表的查找法（静态查找）（静态查找）基于树的查找法基于树的查找法（动态查找）（动态查找）HASH查找法查找法顺序查找法顺序查找法折半查找法折半查找法分块查找法分块查找法二叉排序树二叉排序树平衡二叉树平衡二叉树B树树B树树 9.1 静态查找表n静态查找表主要有三种结构：静态查找表主要有三种结构：u 顺序表顺序表u 有序顺序表有序顺序表u 索引顺序表索引顺序表n针对静态查找表的查找算法主要有：针对静态查找表的查找算法主要有：u顺序查找（线性查找）顺序查找（线性查找）u折半查找（二分查找）折半查找（二分查
4、找）u分块查找（索引顺序查找）分块查找（索引顺序查找）9.1.1 顺序查找法n1.顺序表上的顺序查找的基本思想顺序表上的顺序查找的基本思想u从顺序表的一端开始，用给定数据元素的关键字逐个与从顺序表的一端开始，用给定数据元素的关键字逐个与顺序表中各数据元素的关键字比较，顺序表中各数据元素的关键字比较，l若在顺序表中查找到要查找的数据元素，则查找成功，若在顺序表中查找到要查找的数据元素，则查找成功，函数返回该数据元素在顺序表中的位置；函数返回该数据元素在顺序表中的位置；l否则查找失败，函数返回否则查找失败，函数返回0。n2.顺序表的机内存储结构顺序表的机内存储结构typedef structEle
5、mType*elem;int length;SSTable;xa1a2a3an-2an-1anint Search_Seq(SSTable ST,KeyType key)ST.elem0.key=key;for(i=ST.length;!EQ(ST.elemi.key,key);-i);return i;9.1.1 顺序查找法n顺序查找过程顺序查找过程9.1.1 顺序查找法n3.顺序查找操作的性能分析顺序查找操作的性能分析 （设（设nST.length）u（1）查找成功时的平均查找长度）查找成功时的平均查找长度lxi查找成功的比较次数为查找成功的比较次数为ni1（1in）l等概率情况下查找成功
6、的平均查找长度：等概率情况下查找成功的平均查找长度：u（2）任意关键字查找不成功的比较次数为）任意关键字查找不成功的比较次数为n19.1.1 顺序查找法n顺序查找法的特点：顺序查找法的特点：u优点：优点：l算法简单、算法简单、适用面广（适用面广（对顺序结构或链式结构均适用）对顺序结构或链式结构均适用）u缺点：缺点：lASL 太大，时间效率太低。太大，时间效率太低。n思考题：思考题：u对单链表如何线性查找？对单链表如何线性查找？u对非线性（树结构）如何查找对非线性（树结构）如何查找?u有序顺序表上的查找算法有序顺序表上的查找算法?9.1.2 有序表的查找n有序顺序表上的查找算法有序顺序表上的查找
7、算法u（1）顺序查找法）顺序查找法l有序顺序表上顺序查找算法类同顺序表上的顺序查找有序顺序表上顺序查找算法类同顺序表上的顺序查找算法算法u（2）二分查找法（又称折半查找法）二分查找法（又称折半查找法）l前提条件：前提条件：1）表中的记录按关键字有序（设递增有序）表中的记录按关键字有序（设递增有序）2）查找表采用顺序存储结构）查找表采用顺序存储结构l查找过程查找过程折半查找过程示例折半查找过程示例1)查找关键字等于查找关键字等于21的记录的记录1234567891011513192137566475808892ST.elemmid.key21513192137566475808892ST.ele
8、mmid.key21513192137566475808892ST.elemmid.key=21(查找成功）查找成功）2)查找关键字等于查找关键字等于85的记录的记录1234567891011513192137566475808892ST.elemmid.key85513192137566475808892ST.elemmid.key85513192137566475808892失败失败9.1.2 有序表的查找n算法描述算法描述int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;while(lowdata.key)return
9、T;else if (LT(key,T-data.key)return SearchBST(T-lchild,key);else return SearchBST(T-rchild,key);2.二叉排序树的查找过程及算法n（2）非递归算法）非递归算法BiTree SearchBST(BiTree T,KeyType key)BiTree p=T;while (p&!(EQ(key,p-data.key)if LT(key,p-data.key)p=p-lchild;else p=p-rchild;return p;/SearchBST3.二叉排序树的插入n思路：思路：u查找不成功，生成一个新
10、结点（如查找不成功，生成一个新结点（如s），并将其插入到二），并将其插入到二叉排序树中；叉排序树中；u查找成功则返回。查找成功则返回。4.二叉排序树结点的删除n二叉排序树结点的删除二叉排序树结点的删除u对于二叉排序树，删除树上一个结点相当于删除有序序对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，要求删除后仍需保持二叉排序树的特列中的一个记录，要求删除后仍需保持二叉排序树的特性。性。n问题：问题：u如何删除二叉排序树的一个结点？如何删除二叉排序树的一个结点？n分析：分析：u设待删结点指针为设待删结点指针为p，p的双亲结点指针为的双亲结点指针为f，不失一般性，不失一般性，设设p为
11、为f的左子女（若为右子女，类似）的左子女（若为右子女，类似）4.二叉排序树结点的删除n情况情况1：p为叶结点为叶结点f-lchild=NULL；free(p);FfPp pf-lchild=p-lchild；free(p);FfPpPLFfPpPRFfPLFfPRf-lchild=p-rchild；free(p);4.二叉排序树结点的删除n情况情况2：P只有左子树只有左子树PL或只有右子树或只有右子树PRFf fPp pPRPL1.PR作为作为s的右子女的右子女:s-rchild=p-rchild;2.c作为作为f的左子女：的左子女：f-lchild=p-lchild;3.删除删除p:free
12、(p);方方法法FfCCLQQLSSLPRqscqsPRFfPpCCLQQLSSLcn情况情况3：PL，PR均非空均非空4.二叉排序树结点的删除方方法法qsPRFfPpCCLQQLSSLcFfCCLQQLSSLPRqpc1.以以S代替代替P,然后删除然后删除s:p-data=s-data;2.SL作为作为Q的右子女的右子女:q-rchild=s-lchild;3.释放结点释放结点s:free(s);4.二叉排序树结点的删除n情况情况3：PL，PR均非空均非空5.二叉排序树的查找分析：n查找过程及查找性能分析查找过程及查找性能分析:u含有含有n个结点的二叉树的平均查找长度和树的形状有关。个结点的
13、二叉树的平均查找长度和树的形状有关。ASL(a)1/6(1+2+2+3+3+3)14/6 ASL(b)1/6(1+2+3+4+5+6)21/6452453123793(a)122437459353(b)5.二叉排序树的查找分析n一般地：一般地：u1)二叉排序树上查找某关键字等于结点值的过程，其实二叉排序树上查找某关键字等于结点值的过程，其实就是走了一条从根到该结点的路径。就是走了一条从根到该结点的路径。l比较的关键字次数此结点的层次数比较的关键字次数此结点的层次数;l最多的比较次数树的深度（或高度）；最多的比较次数树的深度（或高度）；u2)一棵二叉排序树的平均查找长度为：一棵二叉排序树的平均查
14、找长度为：5.二叉排序树的查找分析u最好的情况最好的情况l二叉排序树的形态同折半查找的判定树二叉排序树的形态同折半查找的判定树（即形态比较（即形态比较均衡）均衡）l ASLlog 2(n1)1；u最坏的情况最坏的情况l插入的插入的n个元素从一开始就有序，个元素从一开始就有序，二叉排序树的形态二叉排序树的形态为一棵单支树为一棵单支树 l ASL1/n(123n)(n1)/2u一般的情况一般的情况l ASLO(n)5.二叉排序树的查找分析n思考：思考：u如何提高二叉排序树的查找效率？如何提高二叉排序树的查找效率？n解决方法解决方法u尽量让二叉树的形状尽量让二叉树的形状均衡均衡！平衡二叉树平衡二叉树
15、二、平衡二叉树n定义定义u1.结点的平衡因子（结点的平衡因子（BF）u2.平衡二叉树（平衡二叉树（AVL树）树）l或者是一棵空树，或者是具有如下性质的二叉树：或者是一棵空树，或者是具有如下性质的二叉树：它的左子树和右子树深度之差的绝对值不超过它的左子树和右子树深度之差的绝对值不超过1 左子树和右子树都是左子树和右子树都是AVL树。树。u3.平衡的二叉排序树平衡的二叉排序树abecdf452453123793二、平衡二叉树n问题：问题：u如何使构造的二叉排序树成为如何使构造的二叉排序树成为AVL树？树？n答：答：u如果在一棵如果在一棵AVL树中插入一个新结点，就有可能造成失树中插入一个新结点，就
16、有可能造成失衡，此时必须衡，此时必须重新调整树的结构重新调整树的结构，使之恢复平衡。我们，使之恢复平衡。我们称调整平衡过程为称调整平衡过程为平衡旋转平衡旋转。u平衡旋转可以归纳为四类：平衡旋转可以归纳为四类：lRR平衡旋转（单向右旋平衡处理）平衡旋转（单向右旋平衡处理）lLL平衡旋转（单向左旋平衡处理）平衡旋转（单向左旋平衡处理）lLR平衡旋转（双向平衡旋转（双向先左后右先左后右旋平衡处理）旋平衡处理）l RL平衡旋转（双向平衡旋转（双向先右后左先右后左旋平衡处理）旋平衡处理）ABDCE右单旋右单旋1.ABDCEh二、平衡二叉树二、平衡二叉树ACDBEACEDB左单旋左单旋2.ABDCFEGA
17、EBDCFG左单旋左单旋右单旋右单旋ABDCFEhh-1G3.二、平衡二叉树3.右单旋右单旋左单旋左单旋4.DACBEFhh-1GACBEFGDACBEFGD二、平衡二叉树9.2.2 B_树和B+树n一、一、B树及其查找树及其查找u1.定义：一棵定义：一棵m阶的阶的B树，或为一棵空树，或为满足下树，或为一棵空树，或为满足下列条件的列条件的m叉树：叉树：l树中每个结点至多树中每个结点至多m棵子树；棵子树；l若根结点不是叶结点，则至少若根结点不是叶结点，则至少2棵子树；棵子树；l除根以外的所有非终端结点至少有除根以外的所有非终端结点至少有m/2 棵子树；棵子树；l所有非终端结点中包含下列信息数据：
18、所有非终端结点中包含下列信息数据：（A0,K1,A1,K2,A2,Kn,An)l叶结点位于同一层次（外部结点叶结点位于同一层次（外部结点/失败点）失败点）2.示例示例（一棵（一棵4阶阶B树及查找过程）树及查找过程）351181784321112713916447533991FFFFFFFFFFFFabcdefghT查找时间取决因素查找时间取决因素（1）等于给定值的关键字所在结点的层次；等于给定值的关键字所在结点的层次；（2）结点中结点中关键字的个数。关键字的个数。3.查找过程查找过程：顺指针查找结点和在结点的关键字中顺序查找交叉进行的顺指针查找结点和在结点的关键字中顺序查找交叉进行的过程。具体
19、方法：过程。具体方法：从根结点开始，将从根结点开始，将key与根结点中的各个关键字与根结点中的各个关键字k1,k2,，kj进行比较，由于该关键字序列有序，可采用顺序进行比较，由于该关键字序列有序，可采用顺序/二分查二分查找方法。找方法。1)若若keyki,(1ij),则查找成功；则查找成功；2)若若key k1,则沿指针则沿指针A0所指的子树中继续查找；所指的子树中继续查找；3)若若kikeyki+1,则沿指针则沿指针Ai所指的子树中继续查找；所指的子树中继续查找；4)若若keykj,则沿指针则沿指针Aj所指的子树中继续查找。所指的子树中继续查找。在自上向下的查找过程中，若直到叶结点也没有找到
20、值为在自上向下的查找过程中，若直到叶结点也没有找到值为key的关键字，则查找失败。的关键字，则查找失败。9.2.2 B_树和B+树n二、二、B树（树（B的变型树）的变型树）u1.定义：一棵定义：一棵m阶的阶的B 树与树与B树的区别在于：树的区别在于：l有有n棵子树的结点中含有棵子树的结点中含有n个关键字；个关键字；l所有的叶结点包含了全部关键字的信息，及指向这些所有的叶结点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶结点本身依关键字从小到大关键字记录的指针，且叶结点本身依关键字从小到大排列。排列。l所有的非终端结点可看成是索引部分，结点中仅含有所有的非终端结点可看成是索引部分，结点
21、中仅含有其子树中根结点的最大其子树中根结点的最大/最小关键字。最小关键字。2.示例示例（一棵（一棵3阶阶B树及查找过程）树及查找过程）59 9715 44 5972 9710 1521 37 4451 5962 7285 91 97rootsqtn小结：小结：比较式查找法比较式查找法计算式查找法计算式查找法基于线性表的查找法基于线性表的查找法（静态查找）（静态查找）基于树的查找法基于树的查找法（动态查找）（动态查找）HASH查找法查找法顺序查找法顺序查找法折半查找法折半查找法分块查找法分块查找法二叉排序树二叉排序树平衡二叉树平衡二叉树B树树B树树9.3 哈希表u9.3.1 什么是哈希表什么是哈
22、希表 u9.3.2 哈希函数的构造方法哈希函数的构造方法u9.3.3 处理冲突的方法处理冲突的方法u9.3.4 哈希表的查找及其分析哈希表的查找及其分析 9.3.1 什么是哈希表nHASH查找法查找法u又称散列法、杂凑法或关键字地址计算法等；又称散列法、杂凑法或关键字地址计算法等；u相应的表称为哈希表。相应的表称为哈希表。n1.基本思想基本思想 H(key)关键字集合关键字集合地址集合地址集合(0.m1)Hkey9.3.1 什么是哈希表n2.哈希函数哈希函数 u哈希函数是一个映像；哈希函数是一个映像；u设置一个长为设置一个长为m的表的表A，用函数用函数H把数据集合中的把数据集合中的n个记录个记
23、录的关键字的关键字尽可能唯一尽可能唯一地转换成地转换成0m1范围的数值，即范围的数值，即对集合中的任意关键字对集合中的任意关键字key有有0H(key)m1。9.3.1 什么是哈希表n例例1：u若将学生信息按如下方式存入计算机，如：若将学生信息按如下方式存入计算机，如：l将将2001011810201的所有信息存入的所有信息存入A01单元；单元；l将将2001011810202的所有信息存入的所有信息存入A02单元；单元；l将将2001011810231的所有信息存入的所有信息存入A31单元。单元。n则：则：u欲查找学号为欲查找学号为2001011810216的信息，的信息，l便可直接访问便可
24、直接访问A16！9.3.1 什么是哈希表n例例2：u有有6个元素的关键码分别为：个元素的关键码分别为：（14，23，39，9，25，11）。）。u(1)若规定每个元素若规定每个元素k的存储地址的存储地址H（k）k，请画出存储，请画出存储结构图。结构图。地址地址911 14 23 242539内容内容9111423242539明显缺点：明显缺点：空间效率低空间效率低如何解决？如何解决？9.3.1 什么是哈希表u(2)选取关键码与元素位置间的函数为选取关键码与元素位置间的函数为H(k)=k%7l关键字集合：（关键字集合：（14，23，39，9，25，11）l通过哈希函数对通过哈希函数对6个元素建立
25、哈希表：个元素建立哈希表：2596个元素用个元素用7个个地址应该足够地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有冲突！有冲突！地址地址01234567内容内容1423399.3.1 什么是哈希表n3.哈希冲突哈希冲突u通常情况下，关键字的取值范围远远超过哈希表的地址，通常情况下，关键字的取值范围远远超过哈希表的地址，因而可能出现不同的关键字得到相同的哈希函数值，即：因而可能出现不同的关键字得到相同的哈希函数值，即：key1key2，而，而H(key1)H(key2)，这种现象称为，这种现象称为哈希冲突哈希冲突。u对于哈希表来说，最理想的情况是没有
26、冲突，但一般情对于哈希表来说，最理想的情况是没有冲突，但一般情况下，哈希函数是一个压缩映射，故冲突不可完全避免。况下，哈希函数是一个压缩映射，故冲突不可完全避免。9.3.1 什么是哈希表n综上所述，综上所述，u哈希表的设计主要包括如下三个方向的内容：哈希表的设计主要包括如下三个方向的内容：l（1）确定）确定哈希表的空间范围哈希表的空间范围，即确定哈希函数的值，即确定哈希函数的值域；域；l（2）构造好的）构造好的哈希函数哈希函数；所选函数尽可能所选函数尽可能简单简单，以便提高转换速度；，以便提高转换速度；所选函数对关键码计算出的地址，应在哈希地址所选函数对关键码计算出的地址，应在哈希地址内集中并
27、大致内集中并大致均匀均匀分布，以减少空间浪费。分布，以减少空间浪费。l（3）制定一个好的）制定一个好的解决冲突解决冲突的方案。的方案。9.3.2 哈希函数的构造方法u一、一、直接定址法直接定址法 u二、二、数字分析法数字分析法u三、三、平方取中法平方取中法u四、四、折叠法折叠法u五、五、随机函数法随机函数法u六、六、除留余数法除留余数法 一、直接定址法n1.定义：定义：u所谓直接定址法是指取关键字或关键字的某个线性函数所谓直接定址法是指取关键字或关键字的某个线性函数值为哈希地址。即：值为哈希地址。即：H(key)akeyb（其中其中a,b为常数）为常数）n2.特点：特点：u优点：优点：以关键码
28、以关键码key的某个线性函数值为哈希地址，不会的某个线性函数值为哈希地址，不会产生冲突。产生冲突。u缺点：缺点：要占用连续地址空间，空间效率低。要占用连续地址空间，空间效率低。二、数字分析法n定义定义u选用关键字的某几位组合成哈希地址，选用原则应当是：选用关键字的某几位组合成哈希地址，选用原则应当是：各种符号在该位上出现的频率大致相同。各种符号在该位上出现的频率大致相同。n例：例：有一组（有一组（80个）关键码，其样式如下：个）关键码，其样式如下：34705243491487348269634852703486305349805834796713473919位号：位号：二、数字分析法n特点：特
29、点：u该法需要事先知道所有关键字或大多数关键字的值，该法需要事先知道所有关键字或大多数关键字的值，u对关键字的各位进行分析，丢掉分布不均匀的位值，留对关键字的各位进行分析，丢掉分布不均匀的位值，留下分布较下分布较均匀均匀的位值构造其哈希函数。的位值构造其哈希函数。三、平方取中法n定义：定义：u取关键字平方后的中间几位为哈希函数地址。即：取关键字平方后的中间几位为哈希函数地址。即：H(key)“key2的中间几位的中间几位”u如：如：四、折叠法n定义定义u根据哈希表长将关键字分成尽可能等长的根据哈希表长将关键字分成尽可能等长的若干段若干段（最后（最后一部分位数可以短些），然后将这几段的值相加，并
30、将一部分位数可以短些），然后将这几段的值相加，并将高位的进位舍掉，所得结果为其哈希地址。高位的进位舍掉，所得结果为其哈希地址。n分段叠加方法分段叠加方法u法法1：移位叠加移位叠加 将各部分的最后一位对齐相加。将各部分的最后一位对齐相加。u法法2：折叠叠加折叠叠加 从一端向另一端沿分割界来回折叠后，从一端向另一端沿分割界来回折叠后，最后一位对齐相加。最后一位对齐相加。n适用于：适用于：u关键字位数较多且关键字中每一位上数字分布大致均匀关键字位数较多且关键字中每一位上数字分布大致均匀的情况。的情况。四、折叠法n例如：例如：1236032471122020+)1105123306247211020+
31、)907(a)移位叠加移位叠加(b)折叠叠加折叠叠加五、随机函数法n采用一个伪随机函数作哈希函数，即采用一个伪随机函数作哈希函数，即H(key)random(key)n适用于：适用于：u关键字长度不等的情况，造表和查找都很方便。关键字长度不等的情况，造表和查找都很方便。六、除留余数法 H(key)key%p(0pm)n该法产生的哈希函数的好坏取决于该法产生的哈希函数的好坏取决于p的选取。的选取。n讨论：讨论：up取某个整数取某个整数d的的i次幂次幂l用用p对关键字取余，只留下关键字最低的对关键字取余，只留下关键字最低的i位位d进制数，进制数，等于将关键字的高位去掉，于是高位不同而低等于将关键字
32、的高位去掉，于是高位不同而低i位相位相同的关键字均为同义词，故发生冲突的可能性大。同的关键字均为同义词，故发生冲突的可能性大。up为偶数为偶数l则所有的奇关键字被映射到奇地址，而所有的偶关键则所有的奇关键字被映射到奇地址，而所有的偶关键字被映射到偶地址，故很可能不均匀。字被映射到偶地址，故很可能不均匀。key33304548422439H(key)30031299六、除留余数法u若若p为奇数并有质因子，即为奇数并有质因子，即pqf，l那么所有含有那么所有含有q或或f因子的关键字的哈希地址均为因子的关键字的哈希地址均为q或或f的倍数。的倍数。l如如p15,则含有因子则含有因子3的关键字对的关键字
33、对15取模的哈希地址取模的哈希地址均为均为3的倍数。的倍数。六、除留余数法n实践证明：实践证明：up取取不超过不超过哈希表长的最大哈希表长的最大质数；质数；或是不包含小于或是不包含小于20的质的质因子的合数，这样可以减少冲突出现的可能性。因子的合数，这样可以减少冲突出现的可能性。六、除留余数法n例：例：u设有如下关键字集合：设有如下关键字集合：19,14,23,01,68,20,84,27,55,11,10,79，u若哈希表长为若哈希表长为15，则采用除留余数法构造哈希函数为：，则采用除留余数法构造哈希函数为：H(key)key%13key191423016820842755111079H(k
34、ey)6110137613111019.3.3 哈希冲突的解决方法u一、一、开放定址法开放定址法u二、二、再哈希法再哈希法u三、三、链地址法链地址法u四、四、建立一个公共溢出区建立一个公共溢出区一、开放定址法n设计思路设计思路：u有冲突时就去寻找下一个空的哈希地址，只要哈希表足有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。够大，空的哈希地址总能找到，并将数据元素存入。n即：即：Hi（H(key)di）%m u其中：其中：li1,2,k(km1)l（d1,d2,dm1）为增量序列）为增量序列lm为哈希表长度为哈希表长度一、开放定址法n具体实现的几种
35、方案具体实现的几种方案u线性探测再散列线性探测再散列 di1,2,3,m1u二次探测再散列二次探测再散列 di12,12,22,22,，k2u伪随机探测再散列伪随机探测再散列 di伪随机探测再散列伪随机探测再散列key191423016820842755111079H(key)611013761311101一、开放定址法n例例1：u关键字集合为：关键字集合为：19,14,23,01,68,20,84,27,55,11,10,79，u设：设：l哈希表表长为哈希表表长为m15；l哈希函数为哈希函数为Hash(key)key 13；l则：关键字的直接哈希地址为：则：关键字的直接哈希地址为：一、开放定
36、址法u（1）拟用）拟用线性探测再散列线性探测再散列处理冲突：处理冲突：0123456789101112131401234567891011121314140168275519208479231110u哈希表建立如下：哈希表建立如下：key191423016820842755111079H(key)611013761311101一、开放定址法n讨论：讨论：u线性探测法的优点：线性探测法的优点：l只要哈希表未被填满，保证能找到一个空地址单元存只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；放有冲突的元素；u线性探测法的缺点：线性探测法的缺点：l可能出现二次可能出现二次“聚集聚集”，降
37、低查找效率。，降低查找效率。n解决方案：解决方案：u可采用二次探测法或伪随机探测法，以改善可采用二次探测法或伪随机探测法，以改善“二次聚集二次聚集”问题。问题。一、开放定址法u（2）拟用）拟用二次探测再散列二次探测再散列处理冲突：处理冲突：0123456789101112131401234567891011121314271401685584192010231179u哈希表建立如下：哈希表建立如下：key191423016820842755111079H(key)611013761311101一、开放定址法u（3）伪随机探测再散列）伪随机探测再散列l 若若di伪随机序列，就称为伪随机探测再散列
38、。伪随机序列，就称为伪随机探测再散列。二、再哈希法HiRHi(key)i1,2,kn注：注：uRHi均是不同的哈希函数，当产生冲突时就计算另一个哈均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。希函数，直到冲突不再发生。n优点：优点：u不易产生不易产生“聚集聚集”；n缺点：缺点：u需要定义多个不同的哈希函数，并且增加了计算的时间。需要定义多个不同的哈希函数，并且增加了计算的时间。三、链地址法n基本思想：基本思想：u将具有相同哈希地址的记录链成一个单链表，将具有相同哈希地址的记录链成一个单链表，p个哈希个哈希地址就设地址就设p个单链表个单链表，然后用一个数组将，然后用一个
39、数组将m个单链表的表个单链表的表头指针存储起来，形成一个动态的结构。头指针存储起来，形成一个动态的结构。n定义：定义：LinkList ChainHashp;n例：例：u关键字集合为：关键字集合为：19,14,23,01,68,20,84,27,55,11,10,79，u设：设：l哈希表表长为哈希表表长为m15；l哈希函数为哈希函数为Hash(key)key 13；u则：拟采用链地址法解决冲突所构造的哈希表如下：则：拟采用链地址法解决冲突所构造的哈希表如下：三、链地址法四、建立一个公共溢出区n基本思路：基本思路：u除设计哈希基本表以外，除设计哈希基本表以外，另外设立一个溢出向量表，另外设立一个
40、溢出向量表，u将所有关键字和基本表中关键字为同义词的记录，不管将所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。填入溢出表。9.3.4 哈希表的查找过程及分析u一、一、哈希表的查找过程及示例哈希表的查找过程及示例u二、二、哈希查找的应用哈希查找的应用TAi为空？为空？i=H（key)Ai.key=key?i根据冲突解决根据冲突解决方法获得下一个地址方法获得下一个地址失败失败成功成功TFF一、哈希表的查找过程及示例n查找过程的流程图查找过程的流程图一、哈希表的查找过程及示例n查找效率的度量标
41、准查找效率的度量标准u哈希查找法是一种哈希查找法是一种基于计算基于计算的查找方法，但是由于冲的查找方法，但是由于冲突的产生，使得哈希表的查找过程仍然要进行比较，突的产生，使得哈希表的查找过程仍然要进行比较，因此：仍然要以因此：仍然要以平均查找长度平均查找长度ASL来衡量。来衡量。u查找过程的比较次数取决于：查找过程的比较次数取决于：l哈希函数哈希函数l处理冲突的方法处理冲突的方法l哈希表的装填因子哈希表的装填因子。key191423016820842755111079H(key)611013761311101一、哈希表的查找过程及示例n例例1：u哈希函数为哈希函数为Hash(key)key 1
42、3；u若采用线性探测再散列构造哈希表：若采用线性探测再散列构造哈希表：01234567891011121314140168275519208479231110u在等概率情况下，查找成功时的平均查找长度：在等概率情况下，查找成功时的平均查找长度：ASL112（1+1+1+2+1+1+3+4+3+1+3+9）2.5key191423016820842755111079H(key)611013761311101一、哈希表的查找过程及示例n例例2：u哈希函数为哈希函数为Hash(key)key 13；u若采用若采用二次探测二次探测再散列构造哈希表：再散列构造哈希表：012345678910111213
43、14271401685584192010231179u在等概率情况下，查找成功时的平均查找长度：在等概率情况下，查找成功时的平均查找长度：ASL112（1+1+1+2+1+1+3+3+2+1+3+5）2key191423016820842755111079H(key)611013761311101一、哈希表的查找过程及示例n例例3：u哈希函数为哈希函数为Hash(key)key 13；u若采用链地址法解决冲突构造哈希表：若采用链地址法解决冲突构造哈希表：在等概率情况下在等概率情况下，查找成功时的平均查找长度：查找成功时的平均查找长度：ASL112（61421314）1.75一、哈希表的查找过程
44、及示例二、哈希查找法的应用n分析：分析：u哈希查找是一种基于计算的查找方法，但由于冲突的存哈希查找是一种基于计算的查找方法，但由于冲突的存在，仍然需要进行比较的过程。在，仍然需要进行比较的过程。u“冲突冲突”是不是特别讨厌？是不是特别讨厌？l不一定！不一定！正因为有冲突，使得文件加密后无法破译！（单正因为有冲突，使得文件加密后无法破译！（单向散列函数不可逆，常用于向散列函数不可逆，常用于数字签名数字签名和和间接加密间接加密）。）。n哈希表的应用：哈希表的应用：l利用哈希表性质，源文件稍稍改动，会导致哈希表变利用哈希表性质，源文件稍稍改动，会导致哈希表变动很大。动很大。典型应用：典型应用：md5
45、散列算法散列算法补充：散列在密码学中的应用n散列散列(Hash)函数函数u散列函数散列函数(又称杂凑函数又称杂凑函数)是对不定长的输入产生定长输出的一种特是对不定长的输入产生定长输出的一种特殊函数：殊函数：h=H(M)l其中其中M是变长的消息是变长的消息lh=H(M)是定长的散列值或称为消息摘要。是定长的散列值或称为消息摘要。u散列函数散列函数H是公开的，散列值在信源处被附加在消息上，接收方通是公开的，散列值在信源处被附加在消息上，接收方通过重新计算散列值来保证消息未被篡改。过重新计算散列值来保证消息未被篡改。u由于函数本身公开，传送过程中对散列值需要另外的加密保护由于函数本身公开，传送过程中
46、对散列值需要另外的加密保护(如果如果没有对散列值的保护，篡改者可以在修改消息的同时修改散列值，没有对散列值的保护，篡改者可以在修改消息的同时修改散列值，从而使散列值的认证功能失效从而使散列值的认证功能失效)。n三种常用的三种常用的HASH算法算法uMD5uSHA-1uHMACnMD5算法算法u该算法以一个任意长度的报文作为输入，产生一个该算法以一个任意长度的报文作为输入，产生一个128bit的报文摘要作为输出。的报文摘要作为输出。u输入是按输入是按512bit的分组进行处理的。的分组进行处理的。本章总结比较式查找法比较式查找法计算式查找法计算式查找法基于线性表的查找法基于线性表的查找法（静态查找）（静态查找）基于树的查找法基于树的查找法（动态查找）（动态查找）（HASH查找法）查找法）顺序查找法顺序查找法折半查找法折半查找法分块查找法分块查找法二叉排序树二叉排序树平衡二叉树平衡二叉树B树树B树树哈希函数构造方法哈希函数构造方法哈希冲突解决方法哈希冲突解决方法哈希查找过程及性能分析哈希查找过程及性能分析直接定址法直接定址法数字分析法数字分析法平方取中法平方取中法除留余数法除留余数法折叠法折叠法开放定址法开放定址法再哈希法再哈希法链地址法链地址法公共溢出区公共溢出区