数据结构-查找.ppt

第9章查找,查找是指在某种数据结构中找出满足给定条件的结点。若找到满足给定条件的结点则查找成功，否则查找失败。查找是数据结构中常用的基本运算。而查找的对象查找表。其典型的结构有线性表、树表和哈希表等。,何谓查找表？,查找表是由同一类型的数据元素(或记录)构成的集合。,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,对查找表经常进行的操作:,1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。,仅作查询和检索操作的查找表。,静态查找表,有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。,动态查找表,查找表可分为两类:,是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。,关键字,若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。,若此关键字能识别若干记录，则称之谓“次关键字”。,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。,查找,若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。,由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。,如何进行查找？,查找的方法取决于查找表的结构。,如何评估查找方法的优劣？,明确：查找的过程就是将给定的K值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为平均查找长度ASL。,AverageSearchLength,如何评估查找方法的优劣？,其中：n是文件记录个数；Pi是查找第i个记录的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i个记录时所经历的比较次数。,统计意义上的数学期望值,物理意义：假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为ASL。,显然，ASL值越小，时间效率越高。,9.1静态查找表,9.2动态查找表,9.3哈希表,9.1静态查找表,数据对象D：,数据关系R：,D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。,数据元素同属一个集合。,ADTStaticSearchTable,Create(,Destroy(,Search(ST,key);,Traverse(ST,Visit();,基本操作P：,ADTStaticSearchTable,构造一个含n个数据元素的静态查找表ST。,Create(,操作结果：,销毁表ST。,Destroy(,初始条件：操作结果：,静态查找表ST存在；,若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。,Search(ST,key);,初始条件：操作结果：,静态查找表ST存在，key为和查找表中元素的关键字类型相同的给定值；,按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。,Traverse(ST,Visit();,初始条件：操作结果：,静态查找表ST存在，Visit是对元素操作的应用函数；,静态查找表可以有不同的表示方法，在不同的表示方法中，实现查找操作的方法也不同,typedefstruct/数据元素存储空间基址，建表时/按实际长度分配，0号单元留空intlength;/表的长度SSTable;,静态查找表的顺序存储结构为,ElemType*elem;,数据元素类型的定义为:,typedefstructkeyTypekey;/关键字域/其它属性域ElemType;,TElemType;,一、顺序查找表（线性查找）,二、有序查找表（二分或对分查找）,三、索引顺序表（分块查找）,以顺序表或线性链表表示静态查找表,一、顺序查找表(线性查找）,基本思想,从表中最后一个元素开始，顺序用各元素的关键字与给定值x进行比较，若找到与其值相等的元素，则查找成功，给出该元素在表中的位置；否则，若直到第一个记录仍未找到关键字与x相等的对象，则查找失败。,ST.elem,回顾顺序表的查找过程：,假设给定值e=64,要求ST.elemk=e,问:k=?,k,k,intlocation(SqListL,ElemType/location,ST.elem,i,ST.elem,i,60,i,key=64,key=60,i,64,intSearch_Seq(SSTableST,KeyTypekey)/在顺序表ST中顺序查找其关键字等于/key的数据元素。若找到，则函数值为/该元素在表中的位置，否则为0。ST.elem0.key=key;/“哨兵”for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找returni;/找不到时，i为0/Search_Seq,衡量一个查找算法的时间效率的标准是：在查找过程中关键字的平均比较次数或平均读写磁盘次数(只适合于外部查找)，这个标准也称为平均查找长度ASL(AverageSearchLength)，通常它是查找结构中对象总数n或文件结构中物理块总数n的函数。另外衡量一个查找算法还要考虑算法所需要的存储量和算法的复杂性等问题。,在静态查找表中，数据对象存放于数组中，利用数组元素的下标作为数据对象的存放地址。查找算法根据给定值x，在数组中进行查找。直到找到x在数组中的存放位置或可确定在数组中找不到x为止。,定义：查找算法的平均查找长度(AverageSearchLength)为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值其中:n为表长Pi为查找表中查找第i个记录的概率，且，Ci为找到该记录时，曾和给定值比较过的关键字的个数。,分析顺序查找的时间性能,从顺序查找的过程可见，Ci取决于所查记录在表中的位置。如：查找表中最后一个记录时，仅需比较一次；而查找表最后一个记录时，则需比较n次。,对顺序表而言，Ci=n-i+1,在等概率查找的情况下，顺序表查找的平均查找长度为：,ASL=nP1+(n-1)P2+2Pn-1+Pn,假设n=ST.length,则顺序查找的平均长度为：,若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。,在不等概率查找的情况下，ASLss在PnPn-1P2P1时取极小值,优点：算法简单，且对顺序结构或链表结构均适用。缺点：ASL太大，时间效率太低。,顺序查找的特点：,如何改进？,上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。,二、有序查找表,若以有序表表示静态查找表，则查找过程可以基于“折半”进行。,若表中所有记录的关键字满足下列关系ST.elemi.keyx，把查找区间缩小到表的前半部分，再继续进行对分查找；Elementmid.getKey()key，则置high=mid-1如果ST.elemmid.keyhigh时，表明查找不成功，查找结束。,ST.elem,ST.length,例如:key=64的查找过程如下：,low,high,mid,low,mid,high,mid,low指示查找区间的下界high指示查找区间的上界mid=(low+high)/2,intSearch_Bin(SSTableST,KeyTypekey)low=1;high=ST.length;/置区间初值while(low50时，可得近似结果,一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。,可见，折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构（对线性链表无法有效地进行折半查找）。,分块查找（索引顺序查找）,思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后一块中的数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。,讨论：对顺序查找除了折半改进法外，还有无其他改进算法？有，例如分块查找法。,例：,特点：块间有序，块内无序,分块查找过程举例：,索引表,块内最大关键字,各块起始地址,第1块,第2块,第3块,特点：块间有序，块内无序,查找步骤分两步进行：,对索引表使用折半查找法（因为索引表是有序表）；确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；,查找：块间折半，块内线性,索引顺序表的查找过程：,1）由索引确定记录所在区间；,2）在顺序表的某个区间内进行查找。,注意：索引可以根据查找表的特点来构造。,可见，索引顺序查找的过程也是一个“缩小区间”的查找过程。,索引顺序查找的平均查找长度=查找“索引”的平均查找长度+查找“顺序表”的平均查找长度,9.2动态查找表,动态查找表的特点是，表结构本身是在查找过程中动态生成的，即对于给定值key,若表中存在其关键字等于key的记录，则查找成功返回，否则插入关键字等于key的记录。,ADTDynamicSearchTable,抽象数据类型动态查找表的定义如下：,数据对象D：数据关系R：,数据元素同属一个集合。,D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。,InitDSTable(,InsertDSTable(,DeleteDSTable(,TraverseDSTable(DT,Visit();,ADTDynamicSearchTable,操作结果：,构造一个空的动态查找表DT。,InitDSTable(,销毁动态查找表DT。,DestroyDSTable(,初始条件：操作结果：,动态查找表DT存在；,若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。,SearchDSTable(DT,key);,初始条件：操作结果：,动态查找表DT存在，key为和关键字类型相同的给定值；,动态查找表DT存在，e为待插入的数据元素；,InsertDSTable(,初始条件：操作结果：,若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。,动态查找表DT存在，key为和关键字类型相同的给定值；,DeleteDSTable(,初始条件：操作结果：,若DT中存在其关键字等于key的数据元素，则删除之。,动态查找表DT存在，Visit是对结点操作的应用函数；,TraverseDSTable(DT,Visit();,初始条件：操作结果：,按某种次序对DT的每个结点调用函数Visit()一次且至多一次。一旦Visit()失败，则操作失败。,9.2.1动态查找树表,一、二叉排序树（二叉查找树）,二、平衡二叉树,一、二叉排序树（二叉查找树）,1定义,2查找算法,3插入算法,4删除算法,5查找性能的分析,（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；,1定义：,二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：,（3）它的左、右子树也都分别是二叉排序树。,（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；,50,30,80,20,90,10,85,40,35,25,23,88,例如:,是二叉排序树。,66,不,（a）,（b）,例：下列2种图形中，哪个不是二叉排序树？,想一想：对它中序遍历之后是什么效果？,通常，取二叉链表作为二叉排序树的存储结构,typedefstructBiTNode/结点结构structBiTNode*lchild,*rchild;/左右孩子指针BiTNode,*BiTree;,TElemTypedata;,2二叉排序树的查找算法：,1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。,否则，,若二叉排序树为空，则查找不成功；,50,30,80,20,90,85,40,35,88,32,例如:,二叉排序树,查找关键字,=50,50,50,35,50,30,40,35,50,90,50,80,90,95,从上述查找过程可见，,在查找过程中，生成了一条查找路径：,从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,算法描述如下：,StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree/SearchBST,否则表明查找不成功，返回/指针p指向查找路径上访问的最后一个结点，/并返回函数值为FALSE,指针f指向当前访问/的结点的双亲，其初始调用值为NULL,if(!T)elseif(EQ(key,T-data.key)elseif(LT(key,T-data.key)else,p=f;returnFALSE;/查找不成功,p=T;returnTRUE;/查找成功,SearchBST(T-lchild,key,T,p);/在左子树中继续查找,SearchBST(T-rchild,key,T,p);/在右子树中继续查找,30,20,10,40,35,25,23,f,T,设key=48,f,T,f,T,22,p,f,T,f,T,T,T,T,f,f,f,p,根据动态查找表的定义，“插入”操作在查找不成功时才进行；,3二叉排序树的插入算法,若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。,StatusInsertBST(BiTree/InsertBST,s=(BiTree)malloc(sizeof(BiTNode);/为新结点分配空间s-data=e;s-lchild=s-rchild=NULL;,if(!p)T=s;/插入s为新的根结点,elseif(LT(e.key,p-data.key)p-lchild=s;/插入*s为*p的左孩子elsep-rchild=s;/插入*s为*p的右孩子,returnTRUE;/插入成功,若从空树出发，经过一系列的查找插入操作之后，可生成一颗二叉树。设查找的关键字序列为45,24,53,45,12,24,90,则生成的二叉排序树如下图：,可以看出，中序遍历二叉排序树可得到一个关键字的有序序列，即一个无序序列可以通过构造一颗二叉排序树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。而且每次插入的新结点都是二叉排序树上新的叶子结点，在进行插入操作时不必移动其他结点，仅需改动某个结点的指针，由空变为非空即可。故，二叉排序树既拥有类似折半查找的特性，又采用了链表做为存储结构，是动态查找表的一种适宜表示。,（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。,4二叉排序树的删除算法,可分三种情况讨论：,和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。,如何删除一个结点？假设：*p表示被删结点的指针；PL和PR分别表示*P的左、右孩子指针；*f表示*p的双亲结点指针；并假定*p是*f的左孩子；则可能有三种情况：,*p为叶子：删除此结点时，直接修改*f指针域即可；*p只有一棵子树（或左或右）：令PL或PR为*f的左孩子即可；*p有两棵子树：情况最复杂,f,p,f,f,p,p,50,30,80,20,90,85,40,35,88,32,（1）被删除的结点是叶子结点,例如:,被删关键字=20,88,其双亲结点中相应指针域的值改为“空”,50,30,80,20,90,85,40,35,88,32,（2）被删除的结点只有左子树或者只有右子树,其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。,被删关键字=40,80,50,30,80,20,90,85,40,35,88,32,（3）被删除的结点既有左子树，也有右子树,40,40,以其前驱替代之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字=50,StatusDeleteBST(BiTree/不存在关键字等于key的数据元素else/DeleteBST,算法描述如下：,if(EQ(key,T-data.key)/找到关键字等于key的数据元素elseif(LT(key,T-data.key)else,Delete(T);returnTRUE;,DeleteBST(T-lchild,key);/继续在左子树中进行查找,DeleteBST(T-rchild,key);/继续在右子树中进行查找,voidDelete(BiTreep=p-lchild;free(q);,p,p,/左子树为空树只需重接它的右子树,q=p;p=p-rchild;free(q);,p,p,q=p;s=p-lchild;while(!s-rchild)q=s;s=s-rchild;/s指向被删结点的前驱,/左右子树均不空,p-data=s-data;if(q!=p)q-rchild=s-lchild;elseq-lchild=s-lchild;/重接*q的左子树free(s);,p,q,s,5查找性能的分析,对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。,45,如果改变输入顺序为（24，53，45，45，12，24，90），,例：输入待查找的关键字序列=（45，24，53，45，12，24，90）,查找不成功则插入树中,则生成的二叉排序树形态不同,24,二叉排序树的插入与删除,这种既查找又插入的过程称为动态查找,由关键字序列3，1，2，5，4构造而得的二叉排序树，,由关键字序列1，2，3，4，5构造而得的二叉排序树，,例如：,2,1,3,4,5,3,5,4,1,2,ASL=（1+2+3+4+5）/5=3,ASL=（1+2+3+2+3）/5=2.2,下面讨论平均情况:,不失一般性，假设长度为n的序列中有k个关键字小于第一个关键字，则必有n-k-1个关键字大于第一个关键字,由它构造的二叉排序树：,n-k-1,k,的平均查找长度是n和k的函数,P(n,k)(0kn-1)。,假设n个关键字可能出现的n!种排列的可能性相同，则含n个关键字的二叉排序树的平均查找长度：,在等概率查找的情况下，,由此,可类似于解差分方程，此递归方程有解：,二、二叉平衡树,何谓“二叉平衡树”？,二叉平衡树是二叉查找树的另一种形式，其特点为：,树中每个结点的左、右子树深度之差的绝对值不大于1。,例如:,5,4,8,2,5,4,8,2,1,是平衡树,不是平衡树,平衡因子：,二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则二叉树就是不平衡的。,构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。,例如:依次插入的关键字为5,4,2,8,6,9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转一次,先向右旋转再向左旋转,4,2,6,5,8,9,6,4,2,8,9,5,向左旋转一次,继续插入关键字9,如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。,现分别介绍这四种平衡旋转。,平衡旋转可以归纳为四类：LL平衡旋转RR平衡旋转LR平衡旋转RL平衡旋转,若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行一次顺时针旋转。,若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。,2）RR平衡旋转：,1）LL平衡旋转：,以B为旋转轴,以B为旋转轴,若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。,4）RL平衡旋转：,若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。,3）LR平衡旋转：,这种调整规则可以保证二叉排序树的次序不变,以插入的结点C为旋转轴,以插入的结点C为旋转轴,例：请将下面序列构成一棵平衡二叉排序树：（13，24，37，90，53）,013,-113,-124,-213,需要RR平衡旋转(绕B逆转,B为根）,-124,-137,190,-237,需要RL平衡旋转(绕C先顺后逆）,-224,-124,一、哈希表是什么？,二、哈希函数的构造方法,三、处理冲突的方法,四、哈希表的查找,9.3哈希表,以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，,一、哈希表是什么？,查找的过程为给定值依次和关键字集合中各个关键字进行比较，,查找的效率取决于和给定值进行比较的关键字个数。,用这类方法表示的查找表，其平均查找长度都不为零。,不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。,只有一个办法：预先知道所查关键字在表中的位置，,对于频繁使用的查找表，希望ASL=0。,即，要求：记录在表中位置和其关键字之间存在一种确定的关系。,例：若将学生信息按如下方式存入计算机，如：将2001011810201的所有信息存入V01单元；将2001011810202的所有信息存入V02单元；将2001011810231的所有信息存入V31单元。,欲查找学号为2001011810216的信息，便可直接访问V16！,若以下标为000999的顺序表表示之。,例如：为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000xx999(前两位为年份)。,则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。,哈希表：即散列存储结构。散列法存储的基本思想：建立关键字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。优点：查找速度极快（O(1)）,查找效率与元素个数n无关！,对于动态查找表而言，,因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。,1)表长不确定；,2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。,例：,有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）k，请画出存储结构图。,解：根据散列函数H（k）k，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，对应散列存储表（哈希表）如下：,14,11,9,23,25,39,H(k)称为哈希函数,讨论：如何进行散列查找？根据存储时用到的散列函数H(k)表达式，即可查到结果！例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功；若查不到，应当设法返回一个特殊值，例如空指针或空记录。,明显缺点：空间效率低,如何解决？,Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei,例如：对于如下9个关键字,设哈希函数f(key)=(Ord(第一个字母)-Ord(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dei,问题:若添加关键字Zhou,怎么办？,能否找到另一个哈希函数？,1)哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；,从这个例子可见：,从这个例子可见：,2)由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1key2，而f(key1)=f(key2)。,3)很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。,有6个元素的关键码分别为：（14，23，39，9，25，11）。选取关键码与元素位置间的函数为H(k)=kmod7,通过哈希函数对6个元素建立哈希表：,25,39,23,9,14,冲突现象举例：,6个元素用7个地址应该足够!,H(14)=14%7=0,11,H(25)=25%7=4H(11)=11%7=4,有冲突！,因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。,哈希表的定义：,根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。,选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算地址，将k与地址中内容进行比较，确定查找是否成功。,通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。,Hash查找法,哈希方法(杂凑法)哈希函数(杂凑函数)哈希表(杂凑表)冲突,哈希方法中使用的转换函数称为哈希函数(杂凑函数),按上述思想构造的表称为哈希表(杂凑表),若干术语,所以，哈希方法必须解决以下两个问题：,1）构造好的哈希函数（a）所选函数尽可能简单，以便提高转换速度；（b）所选函数对关键码计算出的地址，应在哈希地址内集中并大致均匀分布，以减少空间浪费。,2）制定一个好的解决冲突的方案查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。,在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。,二、哈希函数的构造方法,常用的哈希函数构造方法有：,直接定址法除留余数法数字分析法平方取中法折叠法随机数法,要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。,哈希函数为关键字的线性函数H(key)=key或者H(key)=akey+b,1.直接定址法,此法仅适合于：地址集合的大小=关键字集合的大小,优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突.缺点：要占用连续地址空间，空间效率低。,例：关键码集合为100，300，500，700，800，900，选取哈希函数为Hash(key)=key/100，则存储结构（哈希表）如下：,1.直接定址法,Hash(key)=keymodp(p是一个整数)特点：以关键码除以p的余数作为哈希地址。关键：如何选取合适的p？技巧：若设计的哈希表长为m，则一般取pm且为质数,2.除留余数法,此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。,3.数字分析法,假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。,选用原则应当是：各种符号在该位上出现的频率大致相同。,34705243491487348269634852703486305349805834796713473919,例：有一组（例如80个）关键码，其样式如下：,讨论：第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。,位号：,若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。,3.数字分析法,以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。,4.平方取中法,此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。,4.平方取中法,特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。理由：因为中间几位与数据的每一位都相关。例：2589的平方值为6702921，可以取中间的029为地址。,将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。,5.折叠法,5.折叠法,法1：移位法将各部分的最后一位对齐相加。法2：间界叠加法从一端向另一端沿分割界来回折叠后，最后一位对齐相加。例：元素42751896,用法1：42751896=1041用法2：42751896427+815+96=1338特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。适用于：每一位上各符号出现概率大致相同的情况。,Hash(key)=random(key)(random为伪随机函数)适用于：关键字长度不等的情况。造表和查找都很方便。,执行速度（即计算哈希函数所需时间）；关键字的长度；哈希表的大小；关键字的分布情况；查找频率。,小结：构造哈希函数的原则：,6.随机数法,三、处理冲突的方法,“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。,1.开放定址法,2.链地址法,设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。,1.开放定址法,为产生冲突的地址H(key)求得一个地址序列：H0,H1,H2,Hs1sm-1其中：H0=H(key)Hi=(H(key)+di)MODmi=1,2,s,1.开放定址法,对增量di有三种取法：,1)线性探测再散列di=ci最简单的情况c=12)平方探测再散列di=12,-12,22,-22,3)随机探测再散列di是一组伪随机数列或者di=iH2(key)(又称双散列函数探测),线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。,讨论：,例如:关键字集合19,01,2