数据结构于算法分析 第8章Hash法.ppt

《数据结构于算法分析 第8章Hash法.ppt》由会员分享，可在线阅读，更多相关《数据结构于算法分析 第8章Hash法.ppt（88页珍藏版）》请在三一办公上搜索。

1、第八章查找（Hash法）,本章要求熟练掌握顺序表和有序表的查找方法及其平均查找长度的计算方法；复习二叉排序树的构造和查找方法；熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。本章难点掌握哈希表的构造方法,第八章查找,查找的基本概念基于线性表的查找法 基于树的查找法 计算式查找法哈希法 要点小结,第八章查找,查找的基本概念基于线性表的查找法 基于树的查找法 计算式查找法哈希法 要点小结,Search Problem&Search Engine,Google Myth,Larry Page&Sergey Bri

2、n(Google Co-Founder)Originator of BackRub,Amit Singhal(Ph.D,India)(Google Fellow)Originator of PageRank,Google 查询的全过程,Search Engine Revolutionary,Ori Allon(Google Member)Originator of Orion,查找的基本概念,列表：由同一类型的数据元素（或记录）构成的集合，可利用任意数据结构实现。关键字：数据元素的某个数据项的值，用它可以标识列表中的一个或一组数据元素。如果一个关键字可以唯一标识列表中的一个数据元素，则称其为主

3、关键字，否则为次关键字。当数据元素仅有一个数据项时，数据元素的值就是关键字。,查找的基本概念,查找：根据给定的关键字值，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。若找到相应的数据元素，则称查找是成功的，否则称查找是失败的，此时应返回空地址及失败信息，并可根据要求插入这个不存在的数据元素。对于表的查找，一般有两种情况：静态查找：指在查找过程中只是对数据元素进行查找动态查找：指在实施查找的同时，插入找不到的元素，或从查找表中删除查到的某个元素，即允许元素变化。,查找的基本概念,显然，查找算法中涉及到三类参量：查找对象K（找什么）；查找范围L（在哪找）；K

4、在L中的位置（查找的结果）。其中、为输入参量，为输出参量，在函数中，输入参量必不可少，输出参量也可用函数返回值表示。平均查找长度：为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。,查找的基本概念,对于长度为n的列表，查找成功时的平均查找长度为：其中Pi为查找列表中第i个数据元素的概率，Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。由于查找算法的基本运算是关键字之间的比较操作，所以可用平均查找长度来衡量查找算法的性能。,查找的基本概念,查找的基本方法可以分为两大类：比较式查找法基于线性表的查找法基于树的查找法计算式查找

5、法也称为HASH（哈希）查找法,第八章查找,查找的基本概念基于线性表的查找法 顺序查找法折半查找法分块查找法基于树的查找法 计算式查找法哈希法 要点小结,顺序查找(Sequential Search),顺序查找法的特点是，用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构通常为顺序结构，也可为链式结构。,顺序查找(Sequential Search),顺序查找(Sequential Search),第八章查找,查找的基本概念基于线性表的查找法 顺序查找法折半查找法分块查找法基于树的查找法 计算式查找法哈希法 要点小结,折半查找(Binary Search),折半查找法又称为

6、二分法查找法，这种方法要求待查找的列表必须是按关键字大小有序排列的顺序表。其基本过程是：将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。,折半查找(Binary Search),折半查找(Binary Search),【算法分析】用平均查找长度(ASL)分析折半查找算法的性能。折半查找过程可用一个称为判定树的二叉树描述，判定树中每一结点对应表中一个记录，但结点

7、值不是记录的关键字，而是记录在表中的位置序号。根结点对应当前区间的中间记录，左子树对应前一子表，右子树对应后一子表。显然，找到有序表中任一记录的过程，对应判定树中从根结点到与该记录相应结点的路径，而所做比较的次数恰为该结点在判定树上的层次数。因此，折半查找成功时，关键字比较次数最多不超过判定树的深度。,折半查找(Binary Search),由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为+1。这样，折半查找成功时，关键字比较次数最多不超过+1。相应地，折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径，因此，折半查找成功

8、时，关键字比较次数最多也不超过判定树的深度+1。为便于讨论，假定表的长度n=2h-1，则相应判定树必为深度是h的满二叉树，h=log2(n+1)。又假设每个记录的查找概率相等，则折半查找成功时的平均查找长度为：,折半查找(Binary Search),含11个记录的有序表，其折半查找过程可用二叉判定树表示：,6,7,10,4,1,2,3,9,5,8,11,比较1次,比较2次,比较3次,比较4次,ASL=(1+2+2+3+3+3+3+4+4+4+4)/11=33/11=3,折半查找(Binary Search)演示,折半查找(Binary Search),折半查找方法的优点：查找速度快平均性能好

9、折半查找方法的缺点：要求待查表为有序表插入删除困难因此，折半查找方法适用于不经常变动而查找频繁的有序列表。,第八章查找,查找的基本概念基于线性表的查找法 顺序查找法折半查找法分块查找法基于树的查找法 计算式查找法哈希法 要点小结,分块查找法,分块查找法要求将列表组织成以下索引顺序结构：首先将列表分成若干个块（子表）。一般情况下，块的长度均匀，最后一块可以不满。每块中元素任意排列，即块内无序，但块与块之间有序。构造一个索引表。其中每个索引项对应一个块并记录每块的起始位置，以及每块中的最大关键字（或最小关键字）。索引表按关键字有序排列。,分块查找法,下图为一个索引顺序表。其中包括三个块，第一个块的

10、起始地址为0，块内最大关键字为25；第二个块的起始地址为5，块内最大关键字为58；第三个块的起始地址为10，块内最大关键字为88。,分块查找法,分块查找的基本过程如下：首先，将待查关键字K与索引表中的关键字进行比较，以确定待查记录所在的块。具体的可用顺序查找法或折半查找法进行。进一步用顺序查找法，在相应块内查找关键字为K的元素。例如，在上述索引顺序表中查找36。首先，将36与索引表中的关键字进行比较，因为253658，所以36在第二个块中，进一步在第二个块中顺序查找，最后在8号单元中找到36。,分块查找法,分块查找的平均查找长度由两部分构成，即查找索引表时的平均查找长度为LB，以及在相应块内进

11、行顺序查找的平均查找长度为LW：ASLbs=LB+LW假定将长度为n的表分成b块，且每块含s个元素，则b=n/s。又假定表中每个元素的查找概率相等，则每个索引项的查找概率为1/b，块中每个元素的查找概率为1/s。若用顺序查找法确定待查元素所在的块，则有,分块查找法演示,第八章查找,查找的基本概念基于线性表的查找法 基于树的查找法 二叉排序树平衡二叉排序树B_树计算式查找法哈希法 要点小结,二叉排序树,二叉树排序又称二叉查找树，它是一种特殊的树。其定义为：二叉树排序树或者是一棵空树，或者是具有如下性质的二叉树：若它的左子树非空，则左子树上所有结点的值均小于根结点的值；若它的右子树非空，则右子树上

12、所有结点的值均大于根结点的值；它的左右子树也分别为二叉排序树。这是一个递归的定义。注意：只要结点之间具有可比性即可。,二叉排序树,下图，(a)所示为数字值间的比较，(b)所示为单词字符的ASCII码间的比较。,二叉排序树的查找,二叉排序树的特性：根据二叉排序树的定义（左子树小于根结点，右子树大于根结点），根据二叉树的中序遍历的定义（先中序遍历左子树，访问根结点，再中序遍历右子树），因此，中序遍历一个二叉排序树，可以得到一个递增有序序列。中序遍历下面的二叉排序树，则可得到一个递增有序序列为：1,2,3,4,5,6,7,8,9。,二叉排序树的查找,因为二叉排序树可看作是一个有序表，所以在二叉排序树

13、上进行查找与折半查找类似，也是一个逐步缩小查找范围的过程。根据二叉排序树的特点，首先将待查关键字k与根结点关键字t进行比较，如果：(1)k=t，则返回根结点地址；(2)kt，则进一步查右子树。显然，这是一个递归过程。但可以用递归与非递归两种算法实现。,二叉排序树查找,显然，在二叉排序树上进行查找，若查找成功，则是从根结点出发走了一条从根到待查结点的路径。若不成功，则是从根结点出发走了一条从根到某个叶子结点的路径。因此，二叉排序树的查找与折半查找过程类似，在二叉排序树中查找一个记录时，其比较次数不超过树的深度。对长度为n的有序表而言，折半查找对应的判定树是唯一的，而含有n个结点的二叉排序树却是不

14、唯一的。因为对于同一个关键字集合，关键字插入的先后次序不同，所构成的二叉排序树的形态和深度也可能不同。,二叉排序树查找,二叉排序树的平均查找长度ASL与二叉排序树的形态有关，二叉排序树的各分支越均衡，树的深度浅，其平均查找长度ASL就越小。假设每个元素的查找概率相等，则它们的平均查找长度分别是：(a)ASL=1/6(1+2+2+3+3+3)=14/6(b)ASL=1/6(1+2+3+4+5+6)=21/6,二叉排序树查找,由此可见，二叉排序树的平均查找长度ASL与二叉排序树的形态有关。在最坏的情况下，二叉排序树是通过把一个有序表的n个结点一次插入生成的，由此得到的二叉排序树脱化为一棵深度为n的

15、单支树，它的平均查找长度和单链表上的顺序查找相同，也是(n+1)/2。在最好的情况下，二叉排序树在生成过程中，树的形态比较均匀，最终得到的是一棵形态与折半查找的判定树相似的二叉排序树，其平均查找长度大约是log2n。若考虑把n个结点按各种可能的次序插入到二叉排序树中，则有n!棵二叉排序树（其中有的形态相同），可以证明，对这些二叉排序树的查找长度求平均，其平均查找长度仍然是O(log2n)。,二叉排序树查找,就平均性能而言，二叉排序树上的查找和折半查找相差不大，并且二叉排序树上插入和删除结点十分方便，无需移动大量结点。因此，对于需要经常做插入、删除、查找运算的表，宜采用二叉排序树结构。这也就是人

16、们常常将二叉排序树称为二叉查找树的原因。,第八章查找,查找的基本概念基于线性表的查找法 基于树的查找法 计算式查找法哈希法哈希函数的构造方法处理冲突的方法哈希表的查找过程哈希法性能分析要点小结,哈希(Hash)法,哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表称为哈希表(Hash Tables)。基本思想是：首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p=H(k)，H称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=H(k)，从而达到按关键字直接存取元素的目的。,Ha

17、sh,Hans Peter Luhn(1896.7.11964.8.19)GermanyBusiness Intelligence,KWIC method of indexing,Hash function(1953),Hans Peter Luhn appears to have been the first to use the concept,and that Robert Morris used the term in a survey paper in CACM which elevated the term from technical jargon to formal termi

18、nology.,Robert Morris,Sr.UNIX,Former NSA Chief Scientist(his son Robert Tappan Morris,1988 Morris Worm),Hash Function,A typical hash function at work.Note that the hash sums are always the same size,no matter how short or long the input is.Also note that the hash sums look very different even when t

19、here are only slight differences in the input.,哈希法,当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1k2，但 H(k1)=H(k2)，这种现象称为冲突，此时称k1和k2 为同义词。实际中，冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。综上所述，哈希法主要包括以下两方面的内容：如何构造哈希函数如何处理冲突,哈希函数的构造方法,构造哈希函数的原则是：函数本身便于计算；计算出来的地址分布均匀，即对任一关键字key，H(key)对应不同地址的概率相等，目的是尽可能减少冲突。下面介绍构造哈希函数常用的五种方法：数字

20、分析法平方取中法分段叠加法除留余数法伪随机数法,数字分析法,如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。例如，有80个记录，关键字为8位十进制整数d1d2d3d7d8，如哈希表长取100，则哈希表的地址空间为：0099。假设经过分析，各关键字中d4和d7的取值分布较均匀，则哈希函数为：H(key)=H(d1d2d3d7d8)=d4d7。例如，H(81346532)=43，H(81301367)=06。相反，假设经过分析，各关键字中 d1和d8的取值分布极不均匀，d1 都等于5，d8 都等于2，此时，如果哈希函数为：H

21、(key)=H(d1d2d3d7d8)=d1d8，则所有关键字的地址码都是52，显然不可取。,平方取中法,当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。例：我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01,B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501，同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编

22、码。之后对关键字进行平方运算后，取出第7到第9位作为该关键字哈希地址，如下表所示。,平方取中法,平方取中法求得的哈希地址,分段叠加法,按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。移位法是将分割后的每部分低位对齐相加折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。例如：key，哈希表长度为1000，则应把关键字分成3位一段，在此舍去最低的两位65，分别进行移位叠加和折叠叠加，求得哈希地址为105和907，如下图所示。,分段叠加法,由叠加法求哈希地址,2 30 34 71

23、20 2 0,+),1 1 0 5,2 33 0 64 72 1 10 2 0,+),9 0 7,(a)移位叠加,(b)折叠叠加,除留余数法,假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为：h(key)=key%p，其中%为模p取余运算。例如，已知待散列元素为(18，75，60，43，54，90，46)，表长m=10，p=7，则有h(18)=18%7=4 h(75)=75%7=5 h(60)=60%7=4 h(43)=43%7=1 h(54)=54%7=5 h(90)=90%7=6 h(46)=46%7=4 此时冲突较多。,除留余数法,为减少冲突，可取较大的m值和p值，如m=p=13

24、，结果如下：h(18)=18%13=5 h(75)=75%13=10 h(60)=60%13=8 h(43)=43%13=4 h(54)=54%13=2 h(90)=90%13=12 h(46)=46%13=7 除留余数法求哈希地址,0 1 2 3 4 5 6 7 8 9 10 11 12,伪随机数法,采用一个伪随机函数作哈希函数，即H(key)=random(key)。在实际应用中，应根据具体情况，灵活采用不同的方法，并用实际数据测试它的性能，以便做出正确判定。通常应考虑以下五个因素：计算哈希函数所需的时间（简单）。关键字的长度。哈希表的大小。关键字的分布情况。记录查找的频率。,第八章查找,

25、查找的基本概念基于线性表的查找法 基于树的查找法 计算式查找法哈希法哈希函数的构造方法处理冲突的方法哈希表的查找过程哈希法性能分析要点小结,处理冲突的方法,通过构造性能良好的哈希函数，可以减少冲突，但一般不可能完全避免冲突，因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突，两种情况下解决冲突的方法应该一致。下面以创建哈希表为例，说明解决冲突的方法。常用的解决冲突方法有以下四种：开放定址法再哈希法链地址法建立公共溢出区,开放定址法,也称再散列法，其基本思想是：当关键字key的哈希地址h0=H(key)出现冲突时，以h0为基础，产生另一个哈希地址h1，如果h1仍然冲突，再以

26、h0为基础，产生另一个哈希地址h2，直到找出一个不冲突的哈希地址hi，将相应元素存入其中。这种方法有一个通用的再散列函数形式：或其中，H(key)为哈希函数，h0=H(key)，m为表长，di称为增量序列。,i=1，2，n,i=1，2，n,开放定址法,增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：线性探测再散列di=1，2，3，m-1特点：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。二次探测再散列 di=12，-12，22，-22，k2，-k2(km/2)特点：冲突发生时，在表的左右进行跳跃式探测，比较灵活。,开放定址法,伪随机探测再散列 di=伪随机数序

27、列。具体实现时，应建立一个伪随机数发生器，（如i=(i+p)%m），并给定一个随机数做起点。,开放定址法,例如，已知哈希表长度m=11，哈希函数为：H(key)=key%11，则H(47)=3，H(26)=4，H(60)=5，假设下一个关键字为69，则H(69)=3，与47冲突。如果用线性探测再散列处理冲突，下一个哈希地址为h1=(3+1)%11=4，仍然冲突，再找下一个哈希地址为h2=(3+2)%11=5，还是冲突，继续找下一个哈希地址为h3=(3+3)%11=6，此时不再冲突，将69填入6号单元，参见下图(a)。,开放定址法,已知哈希表长度m=11，哈希函数为：H(key)=key%11，

28、则H(47)=3，H(26)=4，H(60)=5，假设下一个关键字为69，则H(69)=3，与47冲突。如果用二次探测再散列处理冲突，下一个哈希地址为h1=(3+12)%11=4，仍然冲突，再找下一个哈希地址为h2=(3-12)%11=2，此时不再冲突，将69填入2号单元，参见下图(b)。,开放定址法,例如，已知哈希表长度m=11，哈希函数为：H(key)=key%11，则H(47)=3，H(26)=4，H(60)=5，假设下一个关键字为69，则H(69)=3，与47冲突。如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9则下一个哈希地址为h1=(3+2)%11=5，仍然冲突，再找下

29、一个哈希地址为h2=(3+5)%11=8，此时不再冲突，将69填入8号单元，参见下图(c)。,开放定址法,从上述例子可以看出，线性探测再散列容易产生“二次聚集”，即在处理同义词的冲突时又导致非同义词的冲突。例如，当表中i,i+1,i+2三个单元已满时，下一个哈希地址为i,或i+1,或i+2，或i+3的元素，都将填入i+3这同一个单元，而这四个元素并非同义词。线性探测再散列的优点是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定。,开放定址法建立散列表演示,再哈希法,同时构造多个不同的哈希函数：Hi=Rhi(key)，i=1，2，n 当哈希地址Hi=

30、Rh1(key)发生冲突时，再计算Hi=Rh2(key)直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。,链地址法,基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。例如，已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为13，哈希函数为：H(key)=key%13，则用链地址法处理冲突的结果如下图所示。本例的平均查找长度：ASL=(17+24+31)=1.5,链地址法处理冲突时的哈希表,链地址

31、法处理冲突时的哈希表,建立公共溢出区,基本思想是将哈希表分为基本表和溢出表两部分，凡是与基本表发生冲突的元素一律填入溢出表。,第七章查找,查找的基本概念基于线性表的查找法 基于树的查找法 计算式查找法哈希法哈希函数的构造方法处理冲突的方法哈希表的查找过程哈希法性能分析要点小结,哈希表的查找过程,哈希表的查找过程与哈希表的创建过程是一致的。所设要查找关键字为为key的元素，查找过程如下：首先计算h0=hash(key)。如果单元h0为空，则所查元素不存在；如果单元h0中元素的关键字为key，则找到所查元素；否则重复下述解决冲突的过程：按解决冲突的方法，找出下一个哈希地址hi;如果单元hi为空，则

32、所查元素不存在;如果单元hi中元素的关键字为key，则找到所查元素。,哈希表的查找算法,#define m#define NULLKEY typedef int KeyType;/*假设关键字为整型*/typedef struct KeyType key;/*记录中其它分量按需求确定*/RecordType;typedef RecordType HashTablem;int HashSearch(HashTable ht,KeyType K)h0=hash(K);,哈希表的查找算法,if(hth0.key=NULLKEY)return(-1);else if(hth0.key=K)return

33、(h0);else/*用线性探测再散列解决冲突*/for(i=1;i=m-1;i+)hi=(h0+i)%m;if(hthi.key=NULLKEY)return(-1);else if(hthi.key=K)return(hi);return(-1);,第八章查找,查找的基本概念基于线性表的查找法 基于树的查找法 计算式查找法哈希法哈希函数的构造方法处理冲突的方法哈希表的查找过程哈希法性能分析要点小结,哈希法性能分析,由于冲突的存在，哈希法仍需进行关键字比较，因此，仍需用平均查找长度来评价哈希法的查找性能。哈希法中影响关键字比较次数的因素有三个：哈希函数处理冲突的方法哈希表的装填因子哈希表的装

34、填因子的定义如下：=哈希表中元素个数/哈希表的长度可描述哈希表的装满程度。显然，越小，发生冲突的可能性越小，而越大，发生冲突的可能性也越大。,哈希法性能分析,假定哈希函数是均匀的，则影响平均查找长度的因素只剩下两个：处理冲突的方法哈希表的装填因子以下按处理冲突的不同方法分别列出相应的平均查找长度:线性探测再散列伪随机探测再散列、二次探测再散列以及再哈希法链址法,哈希法性能分析,线性探测再散列查找成功时查找失败时 伪随机探测再散列、二次探测再散列以及再哈希法查找成功时,哈希法性能分析,查找失败时 链址法查找成功时查找失败时,哈希法性能分析,从以上讨论可知：哈希表的平均查找长度是装填因子的函数，而

35、与待散列元素数目n无关。因此，无论元素数目n有多大，都能通过调整，使哈希表的平均查找长度较小。已知一组关键字序列（19，14，23，01，68，20，84，27，55，11，10，79）按哈希函数H(key)=key%13 和线性探测处理冲突构造所得哈希表ht0.15,如下图所示。,哈希法性能分析,手工计算等概率情况下查找成功的平均查找长度公式其中Ci为查找第i个元素时所需的比较次数。采用线性探测再散列法处理冲突，计算出在等概率查找的情况下其查找成功的平均查找长度为：,哈希法性能分析,手工计算等概率情况下查找不成功的平均查找长度公式Ci为哈希函数取值为i时查找不成功的比较次数。查找不成功的情况

36、：遇到空单元按解决冲突的方法完全探测一遍后仍未找到。0到r-1相当于r个不成功的查找的入口，从每个入口进入后，直到确定查找不成功为止，其关键字的比较次数就是与入口对应的不成功查找长度。,哈希法性能分析,采用线性探测再散列法处理冲突，计算出在等概率查找的情况下其查找不成功的平均查找长度为：,第八章查找,查找的基本概念基于线性表的查找法 基于树的查找法 计算式查找法哈希法要点小结,要点小结,查找表的检索机制线性索引：记录关键字一般按序排列，以提高检索速度，对应检索采用基于比较的检索方法。树型索引：树型的典型结构是二叉排序树，其检索时间复杂度与树的深度数量级，为对数函数，其对应的检索方法是基于树表的

37、检索，即将待查找的表组织成树、在树型结构上实现查找。散列（哈希）结构：根据数据的关键字“计算”数据的存储地址。散列（哈希）表既是建立表的方法，也是查找表的方法，其对应的检索方法是“计算式”的检索。,要点小结,平均查找长度为确定数据元素在列表中的位置，需和给定关键字进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。由于查找算法的基本运算是关键字之间的比较操作，所以平均查找长度是衡量查找算法性能的重要指标。计算平均查找长度的基本公式对于长度为n的列表，查找成功时的平均查找长度为：Pi为查找列表中第i个元素的概率，Ci为找到列表中第i个元素时，已经进行过的关键字比较次数。,要点小

38、结,计算方法采用公式法计算（通用），也可采用手工计算公式（具体），针对实际的具体问题，计算相应的查找成功时的平均查找长度。虽然两种方式在计算相同问题时得到的具体结果不一定相同，但基于的原理原则相同。故应当掌握这些方法原则并能应用。折半查找折半查找要求待查找表应采用顺序存储结构且按关键字有序排列。折半查找过程借助于折半判定树加以描述。判定树中每一结点对应表中一个记录在表中的位置序号。,要点小结,折半查找算法的性能：在等概率时查找成功的平均查找长度与折半判定树的深度相关：折半查找算法速度快，平均性能好，但插入删除困难。二叉排序树性质：中序遍历一个二叉排序树可以得到一个递增有序序列。含有n个结点的二

39、叉排序树型态不唯一，其构造与数列的输入顺序有关。,要点小结,查找过程与折半查找过程类似，在二叉排序树上的查找一个记录时，其比较次数不超过树的深度。就平均性能而言，在二叉排序树上的查找和折半查找相差不大，平均查找长度仍然是O(log2n)。二叉排序树的插入、删除操作无需移动大量结点，经常变化的动态表宜采用二叉排序树结构。哈希法基本思想：以元素的关键字k为自变量，通过哈希函数H，计算其存储位置p，即p=H(k)，从而实现按关键字计算的方式建立表与查找表。哈希表的查找过程与哈希表的创建过程对应一致。,要点小结,哈希法主要包括：哈希函数构造常用的方法有除留余数法处理冲突方法线性探测再散列法二次探测再散列法链地址法哈希法中影响关键字比较次数的因素哈希函数处理冲突的方法哈希表的装填因子,