《数据结构》算法实现及解析- 数据结构09

2017/12/27,1,第9章 查找,本章主题：表的查找教学目的：掌握各种不同的查找表的查找算法和性能分析 教学重点：线性表的查找、树表的查找和哈希表的查找以及 各种查找的性能分析 教学难点：树表的查找,2017/12/27,2,本章学习导读,查找就是在数据集中找出一个“特定元素”。在软件设计中，通常是将待查找的数据元素集按照一定的存储结构存入计算机中，变为计算机可处理的数据结构，从而构成一种新的数据结构查找表。,9.1 基本概念,本章主要系统地讨论了各种查找方法。主要包括线性表的查找、树表的查找和哈希表的查找以及各种查找的性能分析等。通过本章学习，读者应该熟练掌握以下内容：了解查找及查找表的相关概念掌握各种不同的查找表的查找算法和性能分析 掌握哈希表的各种构造方法、冲突处理和性能分析,2017/12/27,3,查找表是记录的集合，每个记录至少包含一个关键字。所谓查找就是根据给定的关键字值，在查找表中找出一个记录，该记录的关键字值等于给定的值。 若在查找的同时对表做修改运算（如插入和删除），则相应的表称之为动态查找表，否则称之为静态查找表。由于查找表的范围和给定的关键字值的不同，查找有两种可能的结果：一种是找到了相应的记录，称为查找成功。通常要求返回该记录的存储位置，以便对该记录作进一步处理；一种是找不到相应的记录，称为查找失败。此时应返回一个能表示查找失败的值。采用何种查找方法，取决于使用哪种数据结构来表示“表”。即表中记录是按何种方式组织的，根据不同的数据结构采用不同的查找方法。,2017/12/27,4,查找算法中的基本运算是记录的关键字与给定值所进行的比较。其执行时间通常取决于关键字的比较次数，也称为平均查找长度。比较次数的多少就是相应算法的时间复杂度，它是衡量一个查找算法优劣的重要指标。平均查找长度ASL定义为： n 是查找表中记录的个数Pi 是查找第i个记录的概率Ci 是找到第i个记录所需进行的比较次数。,2017/12/27,5,9.2 顺序表的静态查找,定义被查找的顺序表类型定义如下：,#define MAXLEN typedef struct KeyType key; /KeyType为关键字的数据类型 infoType data; /其他数据 SeqList;,在顺序表中的查找，根据元素之间是否具有递增（减）特性又可分为三种情况：简单顺序查找、二分查找和分块有序查找。各种情况的查找方法及其性能存在较大差异。,2017/12/27,6,9.2.1 简单顺序查找,基本思想是：从表的一端开始，逐个把每条记录的关键字值与给定值k进行比较。若某个记录关键字值与给定值k相等，则查找成功，返回找到的记录位置。反之，若已查找到表的另一端，仍未找到关键字值与给定值相等的记录，则查找不成功，返回-1。,Typedef int KeyType;int SeqSearch(SeqList A,int n,KeyType k) int i; int find=0; for(i=0;in;i+) if(Ai.key=k) find=1;break; return (find?i:-1);,2017/12/27,7,算法分析,从顺序查找过程可见（不考虑越界比较），顺序查找不论给定值k为何，若第1个记录符合给定值，只要比较1次。若第n个记录符合给定值，要比较n次，即ci=i。若每个记录的查找概率相等，且每次查找都是成功的。则在等概率的情况下，顺序查找的平均查找长度为： 查找成功时的平均比较次数约为表长的一半。若k值不在表中，则须进行n+1次比较之后才能确定查找失败。顺序查找算法的时间复杂性为O(n)。,2017/12/27,8,9.2.2 二分查找,二分查找的基本思想是：首先确定待查记录所在的范围（区域）。假设用变量low和high分别表示当前查找区域的首尾下标。将待查关键字k和该区域的中间元素，其下标为mid=(low+high)2的关键字进行比较。比较的结果有如下三种情况：（1）k=Amid.key：查找成功，返回mid的值。（2）kAmid.key：说明元素只可能在右边区域（下标从mid+1到high）。因此应在此区域继续取中间位置记录的关键字进行比较。,2017/12/27,9,int BinSearch(SeqList A,int n,KeyType k) int low=0,high=n-1,mid; while(lowk) high=mid-1; else low=high+1; return -1; ,2017/12/27,10,有序表中关键字为（10,15,18,20,26,28,33,36,38,43,49），查找18的示意图。,2017/12/27,11,有序表中关键字为（10,15,18,20,26,28,33,36,38,43,49），查找39的示意图。,2017/12/27,12,算法分析,二分查找算法的计算复杂性可以用二叉树来进行分析。我们把当前查找区间的中间位置上的记录作为根。左子表和右子表中的记录分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树或比较树。,具有11个记录的有序表可用右图所示的判定树来表示。树中每个结点表示一个记录，结点的编号为该记录在表中的位置。找到一个记录的过程就是走了一条从根结点到与该记录结点的路径。和给定值进行比较的次数正好是该结点所在的层次数。,二分查找在查找成功时和给定值进行比较的关键字的个数至多为log2n+1。同理，查找不成功的过程也是走了一条从根结点到某一个终端结点的路径，其所用的比较次数等于树的深度。,2017/12/27,13,在查找概率相同的情况下，Pi=1/n。查找成功的平均查找长度为： 二分查找算法比顺序查找算法平均查找长度为 n/2的比较次数少，查找速度快。虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算，即使采用高效率的排序方法也要花费O(nlog2n)的时间。另外，二分查找只适用顺序存储结构，不适于线性链表结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的记录。 二分查找特别适用于那种一经建立就很少改动，而又经常需要查找的线性表。,2017/12/27,14,9.2.3 分块查找,基本思想是：首先把表长为n的线性表分成b块，前b-1块记录个数为s=n/b，第b块的记录个数小于等于s。在每一块中，结点的存放不一定有序，但块与块之间必须是分块有序的（假定按结点的关键字值递增有序）。即指后一个块中所有记录的关键字值都应比前一个块中所有记录的关键字值大。为实现分块检索，还需建立一个索引表。索引表的每个元素对应一个块，其中包括该块内最大关键字值和块中第一个记录位置的地址指针。显然这个索引顺序表是一个递增有序表。,2017/12/27,15,分块有序表的索引存储表示,2017/12/27,16,索引表结点的数据类型定义如下：,#define MaxIndex typedef struct KeyType key; int link; IdxType; 在这种结构下，查找过程要分为两步：首先查找索引表。因为索引表是有序表，所以可采用二分查找或顺序查找，以确定给定值所在的块。因为块中的记录可以是任意排列的，所以再在已确定的块中进行顺序查找。,2017/12/27,17,分块查找算法如下：,int IdxSerch(SeqList A,IdxType index,int b,KeyType k,int n) /分块查找关键字为k的记录，索引表为index0.b-1 int low=0,high=b-1,mid,i; int s=n/b; /每块记录个数 while(low=high) /在索引表中进行二分查找，找到的位置放在low中 mid=(low+high)/2; if(indexmid.keyk) low=mid+1 else high=mid-1; if(lowb) /在顺序表中顺序查找 for(i=indexlow.link;ikey=k) return; /树中已有k，无须插入 f=p; /f保存当前查找的记录 if(p-keyk) p=p-lchild; else p=p-rchild; p=(BsTree *)malloc(sizeof(BsTree); p-key=k;p-lchild=p-rchild=NULL; /创建一个新记录 if(*BST=NULL) *BST=p; /原树为空，新插入的记录为新的根 else if(kkey) f-lchild=p; /原树非空时将*p作为*f的左孩子插入 else f-rchild=p; ,2017/12/27,23,2二叉排序树的查找基本思想是：（1）当二叉树为空树时，检索失败。 （2）如果二叉排序树根结点的关键字等于待检索的关键字，则检索成功。 （3）如果二叉排序树根结点的关键字小于待检索的关键字，则在根结点的右子树中用相同的方法继续检索。 （4）如果二叉排序树根结点的关键字大于待检索的关键字，则在根结点的左子树中用相同的方法继续检索。,2017/12/27,24,非递归算法：,BsTree *BstSeareh(BsTree *BST,KeyType k ,BsTree *parent) BsTree *p=BST,*q=NULL; /p指向根结点，q指向*p的双亲结点 while(p!=NULL) if(k=p-key) /查找成功 *parent=q; return (p); q=p; if(kkey) p=p-lchild； /在左子树中查找 else p=p-rchild; /在右子树中查找 *parent=q; return (p); /查找失败，返回空 ,2017/12/27,25,3二叉排序树的删除 基本思想是：（1）若待删除的结点是叶结点，直接删去该结点。（2）若待删除的结点只有左子树而无右子树。根据二叉排序树的特点，可以直接将其左子树的根结点放在被删结点的位置。（3）若待删除的结点只有右子树而无左子树。与(2)情况类似，可以直接将其右子树的根结点放在被删结点的位置。（4）若待删除的结点同时有左子树和右子树。根据二叉排序树的特点，可以从其左子树中选择关键字最大的结点或右子树中选择关键字最小的结点放在被删去结点的位置上。假如选取右子树上关键字最小的结点，那么该结点一定是右子树的最左结点。,2017/12/27,26,2017/12/27,27,2017/12/27,28,void DelBstree(BsTree *BST,KeyType k) BsTree *p,*q,*s,*r; q=BstSearch(*BST,k, else if(q-rchild=NULL) /待删除结点的右子树为空,用C语言描述的在二叉排序树中删除结点的算法如下：,2017/12/27,29,if(p) if(p-lchild=q) p-lchild=q-lchild; else p-rchild=q-lchild; else *BST=q-lchild; else s=q; r=s-rchild; while(r-lchild!=NULL) /找右子树关键字值最小的结点 s=r; r=r-lchild; r-lchild=q-lchild; /把待删除结点的左子树做为*r的左子树 if(q!=s) s-lchild=r-rchild; /把*r的右子树做为其父结点*s的左子树 r-rchild=q-rchild; /把待删除结点的右子树做为*r的右子树 if(p) /待删除结点有父结点 if(p-lchild=q) p-lchild=r; else p-rchild=r; else *BST=r;free(q); ,2017/12/27,30,二叉排序树查找算法分析,在二叉排序树上查找其关键字等于给定值的结点的过程，恰是走了一条从根结点到该结点的路径的过程。和给定值比较的关键字次数等于路径长度加1（或结点所在层次数）。含有n个结点的二叉排序树并不唯一，其平均查找长度和树的形态有关。 例如，（a)图和(b)图是结点数为6的两棵二叉排序树。(a)图中树的深度为3，而(b)图树的深度为6。,2017/12/27,31,从平均查找长度分析，假设6个记录的查找概率相等，即为16。则图 (a)树的平均查找长度为： 而图 (b)树的平均查找长度为： 当表中记录按关键字有序时，构成的二叉排序树蜕变为歪斜树。树的深度为n，其平均查找长度为(n+1)/2（和顺序查找相同），这是最差的情况。显然，最好情况下平均查找长度和log2n成正比。为了避免出现歪斜树，在构造二叉排序树的过程中需要不断进行平衡处理，使其成为平衡二叉树。,2017/12/27,32,9.3.2 平衡二叉树,平衡二叉树或是一棵空树，或是具有下列性质的二叉排序树：（1）它的左子树和左子树的深度之差的绝对值不超过1。 （2）它的左、右子树都是平衡二叉树。,1.平衡二叉树和不平衡二叉树,2017/12/27,33,在算法中，通过平衡因子来具体实现上述平衡二叉树的定义。平衡二叉树中每个结点设有一个平衡因子域，其中存放的是该结点的左子树深度减去右子树深度的值，称为该结点的平衡因子。从平衡因子的角度可以说，若一棵二叉树中所有结点的平衡因子取值均为1、0或-l，则该二叉树称为平衡二叉树。,2017/12/27,34,2平衡二叉树的调整 若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。 失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。,2017/12/27,35,（1）LL型平衡旋转法 由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。,2017/12/27,36,（2）RR型平衡旋转法 由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。,2017/12/27,37,（3）LR型平衡旋转法 由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。,2017/12/27,38,（4）RL型平衡旋转法 由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A结点的右孩子C的左子树的根结点D向右上旋转提升到C结点的位置，然后再把该D结点向左上旋转提升到A结点的位置。即先使之成为RR型，再按RR型处理。,2017/12/27,39,例： 将一组记录的关键字按4，5，7，2，1，3，6次序进行插入，生成及调整成平衡二叉树的过程。结点旁的数字是该结点的平衡因子。,2017/12/27,40,2017/12/27,41,平衡二叉树上进行查找算法分析,在平衡二叉树上进行查找的过程与二叉排序树的查找算法相同。因此，在查找过程中和关键字进行比较的次数不超过树的深度。含有n个结点的平衡树的最大深度为：因此，在平衡树上进行查找的时间复杂性为O(logn)。,2017/12/27,42,9.3.3 B-树,B-树又称为多路平衡查找树。 B-树中所有结点的孩子结点最大值称为B-树的阶，通常用m表示。从查找效率考虑，一般要求m3。一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：（1）根结点或者为叶子，或者至少有两棵子树，至多有m棵子树。（2）除根结点外，所有非终端结点至少有棵子树，至多有m棵子树。（3）所有叶子结点都在树的同一层上。（4）每个结点的结构为： （n，A0，K1，A1，K2，A2， ，Kn，An）其中，Ki(1in)为关键字，且Kikey0=k; for(i=q-n;kkeyi;i-); if(i0 ,在B-树root中非递归查找关键字k。成功时函数返回找到的结点的地址,2017/12/27,46,2. B-树的插入插入的过程分两步完成： （1）利用前述的B-树的查找算法查找关键字的插入位置。若找到，则说明该关键字已经存在，直接返回。否则查找操作必失败于某个最低层的非终端结点上。 （2）判断该结点是否还有空位置。即判断该结点的关键字总数是否满足n ，说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需从该结点中直接删去关键字即可。 （2）如果被删关键字所在结点的关键字个数n等于 ，说明删去该关键字后该结点将不满足B-树的定义，需要调整。 调整过程为：如果其左右兄弟结点中有“多余”的关键字。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。,2017/12/27,50,（3）如果左右兄弟结点中没有“多余”的关键字，这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点。如果因此使双亲结点中关键字个数小于 ，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。,2017/12/27,51,在如图（a）所示的3阶B-树中删除75,52,55,30四个关键字,2017/12/27,52,9.4 哈希表查找,哈希表又称散列表。 哈希表存储的基本思想是：以数据表中的每个记录的关键字 k为自变量，通过一种函数H(k)计算出函数值。把这个值解释为一块连续存储空间（即数组空间）的单元地址（即下标），将该记录存储到这个单元中。在此称该函数H为哈希函数或散列函数。按这种方法建立的表称为哈希表或散列表。,2017/12/27,53,例如，要将关键字值序列（3，15，22，24），存储到编号为0到4的表长为5的哈希表中。 计算存储地址的哈希函数可取除5的取余数算法H(k)=k % 5。则构造好的哈希表如图所示。,2017/12/27,54,理想情况下，哈希函数在关键字和地址之间建立了一个一一对应关系，从而使得查找只需一次计算即可完成。由于关键字值的某种随机性，使得这种一一对应关系难以发现或构造。因而可能会出现不同的关键字对应一个存储地址。即k1k2，但H(k1)=H(k2)，这种现象称为冲突。 把这种具有不同关键字值而具有相同哈希地址的对象称“同义词”。 在大多数情况下，冲突是不能完全避免的。这是因为所有可能的关键字的集合可能比较大，而对应的地址数则可能比较少。 对于哈希技术，主要研究两个问题：（1）如何设计哈希函数以使冲突尽可能少地发生。（2）发生冲突后如何解决。,2017/12/27,55,构造好的哈希函数的方法，应能使冲突尽可能地少，因而应具有较好的随机性。这样可使一组关键字的散列地址均匀地分布在整个地址空间。根据关键字的结构和分布的不同，可构造出许多不同的哈希函数。 1直接定址法 直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。该哈希函数H(k)为： H(k)=k+c (c0) 这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可使用直接定址法的哈希函数。否则，若关键字分布不连续将造成内存单元的大量浪费。,9.4.2 哈希函数的构造方法,2017/12/27,56,例：统计某地区从1949年到1995年每年出生的人数，列在一张表中。年份为关键字，因共有47年，所以表中位置范围是147。设置H(k)=k-1948即可，其中k为年份数。 这样的哈希表示意如下：,若要查1970年的出生人数，则根据（1970-1948=22）计算，在表的第22个位置即可找到。,2017/12/27,57,2除留余数法 取关键字k除以哈希表长度m所得余数作为哈希函数地址的方法。即： H(k)=km 这是一种较简单、也是较常见的构造方法。这种方法的关键是选择好哈希表的长度m。使得数据集合中的每一个关键字通过该函数转化后映射到哈希表的任意地址上的概率相等。理论研究表明，在m取值为素数（质数）时，冲突可能性相对较少。,2017/12/27,58,3平方取中法 取关键字平方后的中间几位作为哈希函数地址（若超出范围时，可再取模）。 设有一组关键字ABC，BCD,CDE，DEF，其对应的机内码如表所示。假定地址空间的大小为1000，编号为0-999。现按平方取中法构造哈希函数，则可取关键字机内码平方后的中间三位作为存储位置。计算过程如下表所示：,2017/12/27,59,4折叠法 这种方法适合在关键字的位数较多，而地址区间较小的情况。 将关键字分隔成位数相同的几部分。然后将这几部分的叠加和作为哈希地址（若超出范围，可再取模）。 例如，假设关键字为某人身份证号码430104681015355，则可以用4位为一组进行叠加。即有5355+8101+1046+430=14932，舍去高位。则有H(430104681015355)=4932为该身份证关键字的哈希函数地址。,2017/12/27,60,5数值分析法 若事先知道所有可能的关键字的取值时，可通过对这些关键字进行分析，发现其变化规律，构造出相应的哈希函数。例：对如下一组关键字通过分析可知：每个关键字从左到右的第l，2，3位和第6位取值较集中，不宜作哈希地址。 剩余的第4，5，7和8位取值较分散，可根据实际需要取其中的若干位作为哈希地址。,2017/12/27,61,若取最后两位作为哈希地址，则哈希地址的集合为下表所示：,2017/12/27,62,9.4.3 冲突的解决方法,假设哈希表的地址范围为0m-l，当对给定的关键字k，由哈希函数H(k)算出的哈希地址为i（0im-1）的位置上已存有记录，这种情况就是冲突现象。 处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。即通过一个新的哈希函数得到一个新的哈希地址。如果仍然发生冲突，则再求下一个，依次类推。直至新的哈希地址不再发生冲突为止。 常用的处理冲突的方法有开放地址法、链地址法两大类,2017/12/27,63,1开放定址法 用开放定址法处理冲突就是当冲突发生时，形成一个地址序列。沿着这个序列逐个探测，直到找出一个“空”的开放地址。将发生冲突的关键字值存放到该地址中去。 如 Hi=(H(k)+d（i）) % m, i=1，2，k (km-1) 其中H(k)为哈希函数，m为哈希表长，d为增量函数，d(i)=dl，d2dn-l。 增量序列的取法不同，可得到不同的开放地址处理冲突探测方法。,2017/12/27,64,（1）线性探测法 线性探测法是从发生冲突的地址（设为d）开始，依次探查d+l，d+2，m-1（当达到表尾m-1时，又从0开始探查）等地址，直到找到一个空闲位置来存放冲突处的关键字。 若整个地址都找遍仍无空地址，则产生溢出。 线性探查法的数学递推描述公式为： d0=H(k) di=(di-1+1)% m (1im-1),2017/12/27,65,【例】已知哈希表地址区间为010，给定关键字序列（20，30，70，15，8，12，18，63，19）。哈希函数为H(k)=kll，采用线性探测法处理冲突，则将以上关键字依次存储到哈希表中。试构造出该哈希表，并求出等概率情况下的平均查找长度。 假设数组为A, 本题中各元素的存放过程如下： H(20)=9，可直接存放到A9中去。 H(30)=8，可直接存放到A8中去。 H(70)=4，可直接存放到A4中去。 H(15)=4，冲突； d0=4 d1=(4+1)%11=5，将15放入到A5中。 H(8)=8，冲突； d0=8 d1=(8+1)%11=9，仍冲突； d2=(8+2)%11=10，将8放入到A10中。,2017/12/27,66,H(12)=l，可直接存放到A1中去。H(18)=7，可直接存放到A7中去。H(63)=8，冲突； d0=8 d1=(8+1)%11=9，仍冲突; d2=(8+2)%11=10，仍冲突; d3=(8+3)%11=0，将63放入到A0中。H(19)=8，冲突； d0=8 d1=(8+1)%11=9，仍冲突; d2=(8+2)%11=10，仍冲突; d3=(8+3)%11=0，仍冲突; d4=(8+4)%11=1，仍冲突; d5=(8+5)%11=2，将19放入到A2中。,2017/12/27,67,由此得哈希表如图所示,在等概率情况下成功的平均查找长度为： （1*5+2+3+4+6）/9 =20/9 利用线性探查法处理冲突容易造成关键字的“堆积”问题。这是因为当连续n个单元被占用后，再散列到这些单元上的关键字和直接散列到后面一个空闲单元上的关键字都要占用这个空闲单元，致使该空闲单元很容易被占用，从而发生非同义冲突。造成平均查找长度的增加。 为了克服堆积现象的发生，可以用下面的方法替代线性探查法。,2017/12/27,68,（2）平方探查法 设发生冲突的地址为d，则平方探查法的探查序列为：d+12，d+22，直到找到一个空闲位置为止。平方探查法的数学描述公式为： d0=H(k) di=(d0+i2) % m (1im-1),2017/12/27,69,【例】已知哈希表地址区间为010，给定关键字序列（20，30，70，15，8，12，18，63，19）。哈希函数为H(k)=kll，采用平方探查法处理冲突。【解】 H(20)=9，可直接存放到A9中去。 H(30)=8，可直接存放到A8中去。 H(70)=4，可直接存放到A4中去。 H(15)=4，冲突； d0=4 d1=(4+12) % 11=5，放到A5中。,2017/12/27,70,H(8)=8，冲突； d0=8 d1=(8+12) % 11=9，仍冲突 d2=(8+22) % 11=1 放到A1中。H(12)=l，冲突； d0=1 d1=(1+12) % 11=2，放到A2中。H(18)=7，可直接存放到A7中去。,2017/12/27,71,H(63)=8，冲突； d0=8 d1=(8+12) % 11=9，仍冲突 d2=(8+22) % 11=1，仍冲突 d3=(8+32) % 11=6，放到A6中。H(19)=8，冲突； d0=8 d1=(8+12) % 11=9，仍冲突 d2=(8+22) % 11=1，仍冲突 d3=(8+32) % 11=6，仍冲突 d4=(8+42)% 11= 2，仍冲突 d5=(8+52) % 11=0，放到A0中,2017/12/27,72,建立的哈希表如图所示：,在等概率情况下成功的平均查找长度为：（1*4+2*2+3+4+6）/9 =21/9 平方探查法是一种较好的处理冲突的方法，可以避免出现堆积问题。它的缺点是不能探查到哈希表上的所有单元，但至少能探查到一半单元。 例如，若表长m=13，假设在第3个位置发生冲突，则后面探查的位置依次为4、7、12、6、2、0，即可以探查到一半单元。 若解决冲突时，探查到一半单元仍找不到一个空闲单元。则表明此哈希表太满，需重新建立哈希表。,2017/12/27,73,2链地址法 用链地址法解决冲突的方法是：把所有关键字为同义词的记录存储在一个线性链表中，这个链表称为同义词链表。并将这些链表的表头指针放在数组中（下标从0到m-1）。这类似于图中的邻接表和树中孩子链表的结构。,2017/12/27,74,链地址法查找分析,由于在各链表中的第一个元素的查找长度为l，第二个元素的查找长度为2，依此类推。因此，在等概率情况下成功的平均查找长度为： (1*5+2*2+3*l+4*1)9=169 虽然链地址法要多费一些存储空间，但是彻底解决了“堆积”问题，大大提高了查找效率。,2017/12/27,75,哈希法是利用关键字进行计算后直接求出存储地址的。当哈希函数能得到均匀的地址分布时，不需要进行任何比较就可以直接找到所要查的记录。但实际上不可能完全避免冲突，因此查找时还需要进行探测比较。在哈希表中，虽然冲突很难避免，但发生冲突的可能性却有大有小。这主要与三个因素有关。第一:与装填因子有关 所谓装填因子是指哈希表中己存入的元素个数n与哈希表的大小m的比值，即 =n/m。 当 越小时，发生冲突的可能性越小，越大（最大为1）时，发生冲突的可能性就越大。,9.4.4 哈希表的查找及性能分析,2017/12/27,76,第二:与所构造的哈希函数有关 若哈希函数选择得当，就可使哈希地址尽可能均匀地分布在哈希地址空间上，从而减少冲突的发生。否则，若哈希函数选择不当，就可能使哈希地址集中于某些区域，从而加大冲突的发生。第三:与解决冲突的哈希冲突函数有关 哈希冲突函数选择的好坏也将减少或增加发生冲突的可能性