数据结构查找

《数据结构查找》由会员分享，可在线阅读，更多相关《数据结构查找（59页珍藏版）》请在装配图网上搜索。

1、第八章第八章 查找查找81 查找的基本概念82 顺序表查找83 索引查找84 树表查找85 散列表查找8查找的基本概念1查找表查找表查找表（Search Table）是由记录序列组成的文件或线性表。2查找表上常见的操作（1）查询某个“特定的”记录是否在查找表中；（2）检索某个“特定的”记录的信息；（3）在查找表中插入记录；（4）在查找表中删除记录。根据在查找表上实施的操作不同，可将查找表分为。3静态查找表静态查找表和动态查找表动态查找表 静态查找表只做前两项统称为“查找”的操作，在查找的过程中不再动态地改变查找表，即不做插入和删除记录的操作；动态查找表的表结构本身是在查找过程中动态生成的，即在

2、查找过程中同时插入查找表中不存在的记录，或者从表中删除已经存在的某个记录。4查找依据：一般是把记录的关键字作为查找的依据 5查找查找（Search）的定义：给定某个特定值k，在查找表中找出关键字等于给定值k的记录，若找到，则查找成功查找成功，返回该记录在表中的序号；否则查找不成功查找不成功，给出查找失败的信息。6评价查找算法的效率 平均查找长度平均查找长度ASL（Average Search Length），其计算公式为：其中，n是记录的个数；Ci是找到第i个记录需要进行的比较次数；Pi是查找第i个记录的概率，这里P1=P2=Pi=Pn=1/n。7查找表常用的存储方式：顺序、链接、索引和散列四

3、种来存储。本章共介绍了四类查找方法，即顺序表查找、索引查找、树表查找、散列表查找。82顺序表查找 顺序存储结构存储的查找表，就是顺序表。顺序表的存储结构用C语言描述如下：#define N 100 typedef struct KeyType key;DataType other;RecType;RecType RN+1;N是记录的个数；R0闲置的主要原因为：（1）使下标和记录序号对应；（2）留作他用，比如用作监视哨。基于顺序表的查找两种方法：顺序查找和二分查找8 82 21 1顺序查找顺序查找 顺序查找顺序查找（Sequential Search）又称线性查找线性查找，是最简单、最基本的查找

4、方法。顺序查找的基本思想基本思想是：从表的一端开始，依次将每个记录的关键字与给定值k进行比较，若某个记录的关键字与k相等，表明查找成功，并给出记录在表中的位置（序号）；若整个表检测完，仍未找到与k相等的关键字，表明查找失败，给出查找失败的信息。顺序查找算法的C函数如下：int seqSearch(RecType R,KeyType k)/*在数组R中顺序查找关键字等于k的记录，若找到返回记录序号，否则返回0*/int i；R0.key=k;/*R0用作监视哨*/i=N;/*从表的尾端向前查找*/while（Ri.key!=k）i-；return i；顺序查找算法的性能分析平均查找长度平均查找长

5、度 查找成功时，平均查找长度为：查找不成功时，与关键字的比较次数总是n+1次。查找算法的平均时间复杂度查找算法的平均时间复杂度O(n)。优缺点优缺点 优点是算法简单，可以方便地插入记录。缺点是当n很大时，平均查找长度较大，查找效率较低。顺序查找方法不仅适用于顺序表，也同样适合于单链表。8 82 22 2 二分查找二分查找二分查找二分查找（Binary Search）又称折半查找折半查找，是一种效率较高的查找方法。二分查找要求顺序表是有序表 二分查找的基本思想基本思想是：初始时，查找区间为整个有序表，取查找区间的中间记录作为比较对象，若中间记录的关键字与给定值相等，则查找成功；若给定值小于中间记

6、录的关键字，则在中间记录的前半区继续查找；若给定值大于中间记录的关键字，则在中间记录的后半区继续查找。不断重复上述查找过程，直至新区间中间记录的关键字等于给定值，则查找成功，或者查找区间不断缩小直到为空，表明查找失败。二分查找的具体查找步骤为：二分查找的具体查找步骤为：（1）设变量）设变量low和和high表示查找区间的起始和终端下表示查找区间的起始和终端下标，初始时查找区间是标，初始时查找区间是R1RN，low取值为取值为1，high取值为取值为N。设变量。设变量mid表示查找区间中间位置的表示查找区间中间位置的下标，计算公式：下标，计算公式：mid=(low+hign)/2（2）当）当lo

7、whigh（查找区间非空）时，求（查找区间非空）时，求mid=(low+hign)/2，进行如下比较：，进行如下比较：若若k=Rmid.key，查找成功，返回记录在表中位置，查找成功，返回记录在表中位置若若kRmid.key，则，则low=mid+1，在后半区继续查找，在后半区继续查找（3）当）当lowhigh时，查找区间为空，说明查找失败时，查找区间为空，说明查找失败例例8.8.一个有序表中有13个记录，记录的关键字序列为（7，14，18，21，23，29，31，35，38，42，46，49，52），给定值k分别为14和22，在表中查找关键字与k相等的记录。low=1 high=13 mid

8、=7 low=1 high=6 kRmid，调整到前半区：，调整到前半区：high=mid-1 mid=3 low=1 high=2 kRmid，调整到后半区：，调整到后半区：low=mid+1 mid=2 k=Rmid，查找成功，返回找到的记录序号，查找成功，返回找到的记录序号2 查找查找k=14的过程示意图的过程示意图714 18 21 23 29 31 35 38 42 46 49 520 1 2 3 4 5 6 7 8 9 10 11 12 13 low=1 high=13 mid=7 low=1 high=6 kRmid，low=mid+1 mid=5 low=high=4 kRmi

9、d，low=mid+1 lowhigh 查找区间为空，查找失败。查找区间为空，查找失败。查找查找k=22的过程示意图的过程示意图714 18 21 23 29 31 35 38 42 46 49 520 1 2 3 4 5 6 7 8 9 10 11 12 13二分查找非递归算法的C函数：int binarySearch(RecType R,KeyType k)/*用二分查找法在数组R中查找关键字为k的记录，若找到返回该记录的位置，否则返回0。*/int low,hign,mid;low=1;high=N;/*设置初始查找区间*/while(low=high)/*查找区间非空*/mid=(lo

10、w+high)/2;/*计算查找区间中间位置的下标*/if(k=Rmid.key)return mid;/*查找成功，返回记录的位置*/else if(kRmid.key)high=mid-1;/*调整到前半区*/else low=mid+1;/*调整到后半区*/return 0;二分查找过程判定树判定树 例8.1的二分查找过程对应的判定树 查找成功情况下的平均查找长度为：查找成功情况下的平均查找长度为：ASL=（1+22+34+46）/13=36/13。查找不成功情况下的判定树查找不成功时的平均查找长度查找不成功时的平均查找长度ASL为：为：ASL不成功不成功=（32+412）/14=54/

11、14。二分查找性能分析二分查找的平均查找长度 以树高为k的满二叉树为例，树中共有n=2k-1个结点，第i层有2i-1个结点，则二分查找的平均查找长度为：二分查找算法的平均时间复杂度为O(log2n)011111 222.2nkiiiASLPCkn221log(1)1 log(1)1nnnn 二分查找的特点 优点：比较次数相对较少，查找效率较高。缺点：在查找之前需要建立有序表，二分查找要求顺序存储有序表，因而在表中插入或删除记录都需要移动大量的记录，二分查找方法适合于数据相对稳定的静态查找表。二分查找只适合顺序存储结构，而不适合链接存储结构。83 索引查找 索引查找是建立在索引存储结构索引存储结

12、构上的查找方法。例如在英文字典里查找某个单词的过程就是一个索引查找。把字典看作是索引查找的对象，其中，字典的正文是主要部分，称作是主表主表，字母索引表是为了方便查找而建立的索引，称作是索引表索引表。8 83 31 1 索引表的组织索引表的组织 索引存储的基本思想基本思想是：除了存储主表的记录外，还要为主表建立一个或若干个附加的索引表。索引表用来标识主表记录的存储位置，它由若干个被称为索引项索引项的数据元素组成。索引项的一般形式为（索引关键字，地址），（索引关键字，地址），索引关键字是记录的某个数据项，一般会是记录的关键字，地址是用来标识一个或一组记录的存储位置。若一个记录对应一个索引项，则该索

13、引表为稠稠密索引密索引（Dense Index）。若一组记录对应一个索引项，则该索引表为稀疏索引稀疏索引（Sparse Index）。例例8.2 8.2 为表为表8.18.1所示的通讯录建立索引表。所示的通讯录建立索引表。编号姓名性别职称电话号码所在院系1001刘林女讲师82626777法学院1002赵红男教授67891234法学院1003陈曲女副教授68889245法学院1004南方男讲师89891900理学院1005朱红男讲师23452345理学院1006刘微微女副教授56347812外语学院1007陈俊亮男副教授34512345外语学院1008赵婷婷女讲师67645321外语学院1009

14、陈华女教授89764567艺术学院1010佟晓伟男讲师34523455艺术学院（1）稠密索引：稠密索引为每个记录建立索引项（索引关键字，地址）主表：0 1 2 3 4 5 6 7 8 9 索引表：1001100210031004100510061007100810091010关键字地址100101002110032100431005410065100761008710098101091）稀疏索引：把主表的记录按照某种规则划分为几个子表子表，然后再为每个子表建立索引项（索引关键字，地址）按照所在院系划分，可以有4个子表，分别为：法学院LA1=（1001，1002，1003），理学院LA2=（10

15、04，1005），外语学院LA3=（1006，1007，1008），艺术学院LA4=（1009，1010）。索引表：这种按照主表的非关键字建立的索引表称为辅助索辅助索引表引表。索引关键字起始下标结束下标法学院02理学院34外语学院57艺术学院898 83 32 2 分块查找分块查找分块查找（Block Search）又称索引顺序查找索引顺序查找，是对顺序查找方法的一种改进。分块查找要求对顺序存储的主表建立索引：（1）主表主表“分块分块”有序有序：将主表划分为几个子表，即分块，块内可以无序，但块与块之间必须有序，即前一个块中的最大关键字必须小于后一个块中的最小关键字；（2）建立有序的索引表建立有

16、序的索引表：为每一块建立索引项，索引项包括：每一块中的最大关键字和每一块在主表中的起止位置。由于主表分块有序，所以索引表一定是个递增的有序表。分块查找的基本思想基本思想是：首先在索引表中查找与给定值k对应的索引项，以确定下一步的查找在主表中的哪个分块中进行；然后在分块中继续查找与给定值k对应的记录。设：记录的关键字序列为（14，31，8，22，18，43，62，49，35，52，88，78，71，83）实现分块查找。316388161151014143182218436249355288787183 下标 0 1 2关键字起始下标结束下标索引表数组R下标主表 1 2 3 4 5 6 7 8 9

17、 10 11 12 13 14索引表存储结构的C语言描述如下：#define MAXSIZE 10typedef KeyType IndexType;typedef struct IndexType index;/*IndexType是索引关键字的类型*/int start,end;/*子表在主表中的起始下标和结束下标*/IndexTable;/*IndexTable是索引项的类型*/IndexTable IndexMAXSIZE;/*MAXSIZE的值应该大于索引项数*/实现分块查找算法的C函数：int blockSearch(RecType R,IndexTable Index,int m

18、,KeyType k)/*在主表R和长度为m的索引表Index中查找关键字为k的记录，查找成功返回记录序号，否则返回0*/int i,j;for(i=0;im;i+)/*在索引表中顺序查找与k对应的索引项*/if(k=Indexi.index)break;if(im)/*在第i个子表中顺序查找关键字为k的记录*/for(j=Indexi.start;jkey=k)return t;if(t-key k)t=t-lchild;else t=t-rchild;return NULL;2 2二叉排序树的插入及建立二叉排序树的插入及建立二叉排序树中插入一个结点的过程如下：设待插入结点为*s，若二叉排序

19、树为空，则将新结点*s作为根结点插入；若二叉排序树非空，比较结点*s与根结点的关键字，可分为三种情况：（1）若s-key与根结点的关键字相等，说明树中已经存在该结点，不用插入；（2）若s-key小于根结点的关键字，则将*s插入到根结点的左子树中；（3）若s-key大于根结点的关键字，则将*s插入到根结点的右子树中。在左、右子树中的插入过程和二叉排序树的插入过程是相同的。如此进行下去，直到左子树或右子树为空时，新结点*s作为叶子结点插入到二叉排序树中。一棵二叉排序树插入结点6063 55 90 42 58 70 98 451067 83 60 二叉排序树上插入运算的C函数：BstNode*ins

20、ertNode(BstNode*t,BstNode*s)/*在根结点为*t的二叉排序树上插入新结点*s，并返回根结点*t*/BstNode*p,*q;if(t=NULL)return s;/*二叉排序树为空，新结点为根结点*/p=t;/*二叉排序树非空，开始查找插入位置*/while(p)q=p;if(s-key=p-key)return t;/*二叉排序树中已经存在该结点*/if(s-key key)p=p-lchild;/*在子树中寻找插入位置*/else p=p-rchild;if(s-key key)q-lchild=s;/*插入新结点*/else q-rchild=s;return

21、t;建立一棵二叉排序树的过程就是逐个插入新结点的过程，反复调用插入运算即可。例例8.3设记录的关键字序列为（63，90，70，55，67，42，98，83，10，45，58），依次插入各个关键字，建立一棵二叉排序树。6355907042678398104558建立二叉排序树的算法的C函数如下：BstNode*creatBst()/*建立一棵二叉排序树，返回这棵树的根结点*/BstNode*root,*s;KeyType key;DataType data;root=NULL;scanf(“%d”,&key);/*从键盘读入新插入结点的关键字*/while(key!=-1)/*遇到-1，表明插入

22、操作结束*/s=(BstNode*)malloc(sizeof(BstNode);/*为新结点申请空间*/s-lchild=NULL;s-rchild=NULL;s-key=key;scanf(“%f”,&data);/*读入新插入结点的其他的数据项*/s-other=data;t=insertNode(root,s);/*调用插入算法*/scanf(“%d”,&key);return root;/*返回根结点*/3 3二叉排序树的删除二叉排序树的删除设待删除结点为*p，其双亲结点为*f，以下分三种情况进行讨论。（1）*p结点为叶子结点。只需将被删结点的双亲结点相应指针域置为空即可，这种情况最

23、简单。（2）*p结点为单分支结点。*p结点只有一棵子树。若只有左子树，根结点为*pl；或者只有右子树，根结点为*pr，此时，只需用*pl或*pr替换*p结点即可，这种情况也比较简单。（3）*p结点为双分支结点。*p结点既有左子树，又有右子树，其根结点分别为*pl和*pr。这种情况下删除*p结点比较复杂，可按中序遍历保持有序的原则进行调整，有两种调整方法：第一种方法，把*p的右子树链接到*p的中序遍历前趋结点的右指针域上，*p的中序前趋结点是它的左子树最右下结点，其右指针域一定为空，从而使得*p结点的右子树为空，变成单分支点，然后用*pl 替换*p结点；第二种方法，用*p结点的中序前趋结点（中序

24、后继结点）的值替换*p结点的值，然后删除*p的中序前趋结点（中序后继结点）。*p的中序前趋（中序后继）不是叶子结点就是单分支结点，可以按照（1）或（2）的方法将它删除。（a）一棵二叉排序树 （b）第一种方法删除结点20（c）第二种方法删除结点20 （d）第二种方法删除结点364二叉排序树查找性能分析二叉排序树的形态与结点的插入顺序有关 如结点的插入顺序为：63,90,70,55,67,42,98,10,45,58,构成的二叉排序树如图(a)ASL=(1+22+34+43)/10=2.9 如果插入顺序为：10,42,45,55,58,63,67,70,90,98,构成的二叉排序树如图(b)ASL

25、=(1+2+3+4+5+6+7+8+9+10)/10=5.5 63 55 90 42 58 70 98 451067 63559842587045106790(a)(b)二叉排序树的查找效率与树的形态有关。最好情况下，平均查找长度大约为log2n，时间复杂度为O(log2n)。最坏的情况下，平均查找长度为(n+1)/2，时间复杂度为O(n)。查找运算的平均时间复杂度仍为O(log2n)。二叉排序树的平均查找性能与二分查找近似，查找效率较高，同时使用链式存储结构，它的插入和删除操作也较为方便，所以二叉排序树非常适合作动态查找表。85 散列表查找 顺序表、索引表和树表中，记录的存储位置与记录的关键

26、字之间不存在确定的关系，在表中查找记录需要进行一系列的比较，所以查找效率主要取决于查找过程中执行的比较次数。如果记录的存储位置与关键字之间有某种确定的关系，在理想的情况下，记录的存储位置与关键字存在一一对应关系，则可以不通过比较就能找到对应的记录。本节探讨的散列表查找就是这样的查找方法。851 散列表的概念 散列存储是专为查找而设计的存储结构，它的基基本思想本思想是：以表中每一个记录的关键字k为自变量，通过某个函数Hash(k)计算出函数值，把这个值解释为记录的存储位置，将记录存储在Hash(k)所指的位置上。散列存储实现了关键字到存储地址的转换，所以也称关键字地址转换法。散列表：散列表：使用

27、散列存储方式存储的线性表，也称作哈希表哈希表（Hash Table）。散列存储中使用的函数Hash(k)，称为散列函数散列函数（哈希函数哈希函数），Hash(k)的值称为散列地址散列地址（哈希哈希地址地址）。若有一个长度为9的线性表，其中记录的关键字序列为（23，15，36，99，6，14，65，93，75），使用散列存储方式存储该线性表.0 6 14 15 23 36 65 75 93 98 9961415233665759399(1)直接定址法直接定址法 设设散列函数Hash1(key)=key,将线性表存储在长度为100的数组空间上，散列表的存储情况如图所示。直接定址法直接定址法一般形式

28、为：Hash(key)=akey+b，其中，a、b为常数，这里a为1，b为0。设线性表的长度为n，散列表（一维数组）的长度为m，则称=n/m为散列表的装填因子装填因子。装填因子的取值区间为0.6.0.9比较合适。本例中n=9，m=100，则为0.09，显然这样的散列函数是不可取的，在实际应用中较少使用。（2）除留余数法 散列函数为 Hash2（key）=key%11，将线性表存储在长度为11的数组中，则每个记录的散列地址为：Hash2(23)=23%11=1 Hash2(15)=15%11=4 Hash2(36)=36%11=3 Hash2(99)=99%11=0 Hash2(6)=6%11=

29、6 Hash2(14)=14%11=3 Hash2(65)=65%11=10 Hash2(93)=93%11=5 Hash2(75)=75%11=9 一般地，若某个散列函数Hash(k)对于不相等的关键字key1和key2，得到相同的散列地址，则称该现象为冲突冲突。发生冲突的两个不同的关键字key1和key2被称为同义词同义词，这里36和14就是同义词。如何设计一个好的散列函数和确定一种解决冲突的办法，是散列存储方式中需要解决的两个最重要问题。8 85 52 2 散列函数的设计散列函数的设计 散列函数的设计原则是：计算简单，节省时间；函数值取值范围合理，避免空间的浪费，保证在合理的取值区间；散

30、列地址尽可能均匀地分布在散列空间上，避免太多的冲突。1数字分析法数字分析法 例例8.5有一组由有一组由7位数字组成的关键字，使用数字分析位数字组成的关键字，使用数字分析法设计散列函数。法设计散列函数。关键字散列地址1（0-999）散列地址2（0-99）3 4 7 0 5 2 43 4 9 1 4 8 73 4 8 2 6 9 73 4 8 5 2 7 33 4 8 6 3 0 53 4 9 8 0 5 83 4 7 9 6 7 13 4 7 3 9 1 9 0 5 2 1 4 8 2 6 9 5 2 7 6 3 0 8 0 5 9 6 7 3 9 12 90 12 22 56 83 86 75

31、 8 2除留余数法除留余数法 Hash(key)=key%p （p是一个整数）若线性表的长度为n，散列表的长度为m，则一般选取p为质数，且 npm。根据装填因子的取值区间为0.6.0.9，p应为1.1n1.7n之间的一个质数。3平方取中法平方取中法 平方取中法是对关键字取平方后，按散列空间的大平方取中法是对关键字取平方后，按散列空间的大小，取中间的若干位作为散列地址。小，取中间的若干位作为散列地址。例例8.6 有一组关键字为0100，0111，0101，1001，0011，取平方的结果是：0010000，0012321，0010201，1002001，0000121，如果散列空间的长度为100

32、0，则可取中间的三位作为散列地址100，123，102，020，001。4折叠法折叠法 折叠法是将关键字自左到右分成位数相等的几部分，最后一部分位数可以短些，然后将这几部分叠加求和，并根据散列表的表长，选取后几位作为散列地址。例例8.7 已知关键字 key=5326248725，散列表长度为1000，使用折叠法计算散列地址。按照每三位为一部分来分割关键字，关键字分割为如下四组：532 624 872 5 532 624 872 +5 2033 Hash(key)=033 折叠法适合于关键字的位数较多，而散列地址的位数较少，同时关键字中的每一位的取值又较集中的情况。8 85 53 3 解决冲突的

33、方法解决冲突的方法1开放地址法开放地址法 所谓开放地址法，就是散列地址单元一旦发所谓开放地址法，就是散列地址单元一旦发生了冲突，就按照某种方法寻找下一个开放生了冲突，就按照某种方法寻找下一个开放地址。开放地址是指该地址单元为空，可以地址。开放地址是指该地址单元为空，可以存储记录。存储记录。寻找开放地址的方法有很多，它们的区别是寻找开放地址的方法有很多，它们的区别是形成的探测序列不同。形成的探测序列不同。（1）线性探测法）线性探测法 线性探测法的基本思想基本思想是：将散列表看成一个首尾相接的环形表，设散列表的长度为m，当向散列表中插入关键字为key的记录时，若地址d=Hash(key)的单元为空

34、，即将记录存入该地址单元。若发生冲突，则依次探测下列地址单元：d+1，d+2，m-1，0，1，d-1，直到找到一个空的地址单元，然后将记录存入其中。或者在探测过程中，遇到关键字为key的记录，说明表中已有该记录，无需插入。如果按照这种探测序列搜索整个散列表后又回到了地址空间d，则说明散列表已满。线性探测法计算下一个开放地址的公式为：Hi=（Hash（key）+i）%m 其中：i取整数，取值范围 1im-1；m为散列表的长度。例例8.8 依次向长度为11的散列表（数组R）中插入关键字为 47，7，29，11，16，92，22，8，3的记录，散列函数为：Hash（key）=key%11，用线性探测

35、法处理冲突。散列表的存储结构如图所示。829731692472211下标 0 1 2 3 4 5 6 7 8 9 1047，7，11，16，92没有发生冲突；29，22，8 发生冲突，由H1=(Hash(k)+1)%存入其中；Hash(3)发生冲突，H1=(Hash(3)+1)%11=4，仍然冲突；H2=(Hash(3)+2)%11=5，仍然冲突；H3=(Hash(3)+3)%11=6，找到空的地址单元R6，存入其中。关键字477291116922283比较次数111111224在例子8.8中，成功查找到每一个记录需要与关键字的比较次数 如表所示。查找成功时，它的平均查找长度为：ASL=（1+

36、1+1+1+1+1+2+2+4）/9=14/91.56查找不成功时，它的平均查找长度为：ASL不成功=（3+2+1+8+7+6+5+4+3+2+1）/11=42/113.82链地址法链地址法 链地址法就是把发生冲突的同义词记录用单链表链链地址法就是把发生冲突的同义词记录用单链表链接起来，散列表中的每一个单元不是用来存储记录，接起来，散列表中的每一个单元不是用来存储记录，而是存储单链表的头指针。所有散列地址相同（冲而是存储单链表的头指针。所有散列地址相同（冲突）的记录都存储在同一个单链表中。由于单链表突）的记录都存储在同一个单链表中。由于单链表每一个结点是动态生成的，所以插入和删除记录非每一个结

37、点是动态生成的，所以插入和删除记录非常方便。散列表的长度只要与散列函数的取值范围常方便。散列表的长度只要与散列函数的取值范围对应即可。对应即可。例例8.9 已知关键字序列和例8.8相同，散列函数仍为Hash(key)=key%11，使用链地址法处理冲突，用头插法向单链表中插入结点。查找成功时的平均查找长度ASL=(61+23)/9=12/91.33查找不成功时的平均查找长度：ASL=(2+0+0+2+1+1+0+2+1+0+0)/11=9/110.82012345678910162292471138297结论：（1）散列表中的平均查找长度要比顺序查找和二分查找小。查找表的长度n=9，散列表的平

38、均查找长度分别为：线性探测法：ASL=14/91.56 链地址法：ASL=12/91.33 顺序查找和二分查找的平均查找长度分别为：ASL=(9+1)/2=5 ASL=(1+22+34+42)/9=25/92.78（2）散列表的平均查找长度与散列函数的设计、冲突的解决方法有关。同样一组关键字，不同的散列函数使得冲突的发生频繁程度不同，导致平均查找长度是不同的。同样一组关键字，设定相同的散列函数，但用不同的冲突解决方法构造散列表，其平均查找长度仍然是不同的。（3）一般情况下，当散列函数的设计方法相同时，散列表的平均查找长度与装填因子有关。装填因子反映了散列空间的装满程度，越小，发生冲突的可能性就越小，查找时与关键字比较的次数较少；反之，越大，发生冲突的可能性就越大，查找时与关键字比较的次数就越多。但越小，造成空间的浪费也越大。（4）散列表的优点：关键字与记录的存储地址存在确定的对应关系，使得插入和查找操作效率很高，所以散列表是较优的动态查找表。散列表的缺点：根据关键字计算散列地址的操作需要一定的时间开销；散列表存储方式浪费存储空间；在散列存储结构中，无法体现出记录之间的逻辑关系。