1、1第八章第八章 查找查找v查找的概念查找的概念v静态查找表静态查找表v动态查找表动态查找表v 哈哈希表希表2查找表查找表 是由同一类型的数据元素是由同一类型的数据元素(或记录或记录)构成构成的集合的集合,由于由于“集合集合”中的数据元素之间存在着中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数松散的关系，因此查找表是一种应用灵便的数据结构。据结构。对查找表的操作对查找表的操作:查询某个查询某个“特定的特定的”数据元素是否在查找表中；数据元素是否在查找表中；检索某个检索某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；在查找表中插入一个数据元素；在查找表中插入一个数据元素
2、；从查找表中删去某个数据元素从查找表中删去某个数据元素 查找的概念3静态查找表静态查找表仅作查询和检索操作的查找表。静态查找仅作查询和检索操作的查找表。静态查找表在查找过程中查找表本身不发生变化。表在查找过程中查找表本身不发生变化。动态查找表动态查找表在查找过程中同时插入查找表中不存在的在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，或者从查找表中删除已存在的某个数据元素数据元素,此类表为动态查找表。动态查找表在此类表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。查找过程中查找表可能会发生变化。查找表的分类：查找表的分类：4关键字关键字是数据元
3、素（或记录）中某个数据项的值，是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。若用以标识（识别）一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓此关键字可以识别唯一的一个记录，则称之谓“主关键字主关键字”。若此关键字能识别若干记录，则。若此关键字能识别若干记录，则称之谓称之谓“次关键字次关键字”。学号学号 姓名姓名 专业专业 年龄年龄 0101 王洪王洪 计算机计算机 17 17 02 02 孙文孙文 计算机计算机 18 18 03 03 谢军谢军 计算机计算机 1818 04 04 李辉李辉 计算机计算机 2020 05 05 沈祥福沈祥福 计
4、算机计算机 25 25 06 06 余斌余斌 计算机计算机 1919 07 07 巩力巩力 计算机计算机 1717 08 08 王辉王辉 计算机计算机 18185 根据给定的某个值，在查找表中确定一个其关根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。键字等于给定值的数据元素或（记录）。若查找表中存在这样一个记录，则称若查找表中存在这样一个记录，则称“查查找成功找成功”，查找结果：给出整个记录的信，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；息，或指示该记录在查找表中的位置；否则称否则称“查找不成功查找不成功”，查找结果：给，查找结果：给出出“空记录
5、空记录”或或“空指针空指针”。查找查找 6 如何进行查找？如何进行查找？查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。由于查找表中的数据元素之间不存在明显的组由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。织规律，因此不便于查找。为了提高查找的效率，为了提高查找的效率，需要在查找表中的需要在查找表中的元素之间人为地元素之间人为地 附加某种确定的关系，换句附加某种确定的关系，换句话说，话说，用另外一种结构来表示查找表。用另外一种结构来表示查找表。7查找方法评价查找方法评价 查找速度查找速度 占用存储空间多少占用存储空间多少 算法本身复杂程度算法本身复杂程度 平均查找
6、长度平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的比较的关键字的个数的期望值叫查找算法的ASL个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：个记录的表，对含有icpipcpASLniniiiniii1118抽象数据类型静态查找表的定义抽象数据类型静态查找表的定义:ADT StaticSearchTable D是具有相同特性的是具有相同特性的数据元素的集合。每数据元素的集合。每个数据元素含有类型个数据元素含有类型相同的关键字，可唯相同的关键字，可唯
7、一标识数据元素。一标识数据元素。数据关系数据关系R：数据元素同属一个集合。：数据元素同属一个集合。静静 态态 查查 找找 表表数据对象数据对象D:9Create(&ST,n);/构造一个含构造一个含 n 个数据个数据元素的静态查找表元素的静态查找表ST。Destroy(&ST);/销毁表销毁表ST。Search(ST,key);/查找查找 ST 中其关键字等中其关键字等于于kval 的数据元素。的数据元素。Traverse(ST,Visit();/按某种次序对按某种次序对ST的每个元素调用函数的每个元素调用函数Visit()一次且仅一次，一次且仅一次，ADT StaticSearchTable
8、基本操作基本操作 P：10顺序表的查找顺序表的查找typedef struct ElemType*elem;/数据元素存储空间基址，建表时数据元素存储空间基址，建表时 按实际长度分配，按实际长度分配，0号单元留空号单元留空 int length;/表的长度表的长度 SSTable;以顺序表表示静态查找表，则以顺序表表示静态查找表，则Search函数可函数可用顺序查找来实现。用顺序查找来实现。其顺序存储结构如下：其顺序存储结构如下：11i0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找找6464监视哨监视哨iiii比较次数比较次
9、数=5比较次数：比较次数：查找第查找第n个元素：个元素：1查找第查找第n-1个元素：个元素：2.查找第查找第1个元素：个元素：n查找第查找第i个元素：个元素：n+1-i查找失败查找失败：n+1查找过程：查找过程：从表的一端开始逐个进行记从表的一端开始逐个进行记录的关键字和给定值的比较。录的关键字和给定值的比较。例如：例如：12算法描述：算法描述：int Search_Seq(SSTable ST,KeyType kval)/在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于 key的数的数据元素据元素 ST.elem0.key=kval;/设置设置“哨兵哨兵”for(int i=
10、ST.length;ST.elemi.key!=kval;-i);/从后往前找从后往前找 return i;/若找到，则函数值为该元素在表中的若找到，则函数值为该元素在表中的位置位置,找不到时，找不到时，i为为0 /Search_Seq13顺序查找性能分析顺序查找性能分析查找算法的平均查找长度查找算法的平均查找长度(Average Search Length)：为确定记录在查找表中的位置，需和给定值为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值。进行比较的关键字个数的期望值。niiiCPASL1其中其中:n 为表长为表长Pi 为查找表中第为查找表中第i个记录的概率个记录的
11、概率Ci为找到该记录时，曾和给定值比较过的为找到该记录时，曾和给定值比较过的关键字的个数关键字的个数11niiP14顺序表查找的平均查找长度为：顺序表查找的平均查找长度为：对顺序表而言，对顺序表而言，Ci=n-i+121111n)i(nnASLnissASL=nP1+(n-1)P2+2Pn-1+PnnPi1在等概率查找的情况下，在等概率查找的情况下，15 在不等概率查找的情况下，在不等概率查找的情况下，ASLss 在在 PnPn-1P2P1时取极小值。表中记录按查找概率由时取极小值。表中记录按查找概率由小到达重新排列小到达重新排列,以提高查找效率。以提高查找效率。若查找概率无法事先测定，则查若
12、查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移找之后，将刚刚查找到的记录直接移至表尾的位置上。至表尾的位置上。16顺序表的查找算法简单，但平均查顺序表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找找长度较大，不适用于表长较大的查找表。表。若以若以有序表有序表表示静态查找表，则查表示静态查找表，则查找过程可以基于找过程可以基于“折半折半”进行。进行。有序表的查找有序表的查找折半查找折半查找查找过程查找过程：每次将待查记录所在区间缩小一：每次将待查记录所在区间缩小一半。半。适用条件适用条件：采用顺序存储结构的：
13、采用顺序存储结构的有序表有序表。17折半查找算法实现折半查找算法实现1.1.设表长为设表长为n n，lowlow、highhigh和和midmid分别指向待分别指向待查元素所在区间的上界、下界和中点查元素所在区间的上界、下界和中点,k k为为给定值。给定值。2.2.初始时，令初始时，令low=1,high=n,mid=low=1,high=n,mid=(low+high)/2(low+high)/2 让让k k与与midmid指向的记录比较指向的记录比较若若k=rmid.keyk=rmid.key，查找成功，查找成功若若krmid.keykrmid.keykrmid.key，则，则low=mi
14、d+1low=mid+13.3.重复上述操作，直至重复上述操作，直至lowhighlowhigh时，查找失败。时，查找失败。18lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid例如例如 key=21 的查找过程的查找过程low 指示查找区间的下界;hi
15、gh 指示查找区间的上界;mid=(low+high)/2。19例例key=70 的查找过程的查找过程1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88
16、92lowhighmid201 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh当下界当下界low大于上界大于上界high时，则说明表中时，则说明表中没有关键字等于没有关键字等于Key的元素，查找不成功。的元素，查找不成功。21int count=0;/记录查找次数记录查找次数int Search_Bin(SSTable ST,KeyType kval)/在顺序表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于 key的数据元素的数据元素 int low=1,mid,high=ST.length;/置区间初值置区间初
17、值while(low=high)count+;mid=(low+high)/2;if(kval=ST.elemmid.key)return mid;/若找到，则函数值为该元素在表中的位置若找到，则函数值为该元素在表中的位置else if(kvaldata.key)else if(LT(key,T-data.key)else p=f;return FALSE;/查找不成功 p=T;return TRUE;/查找成功SearchBST(T-lchild,key,T,p);/在左子树中继续查找SearchBST(T-rchild,key,T,p);/在右子树中继续查找44fT设 key=48fTfT
18、22pfTfTTTTfffp3020104035252345 根据动态查找表的定义，根据动态查找表的定义，“插入插入”操操作在查找不成功时才进行作在查找不成功时才进行;若二叉排序树为空树，则新插入的结若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位点必为一个新的叶子结点，其插入位置由查找过程得到。置由查找过程得到。二叉排序树的插入算法二叉排序树的插入算法46int InsertBST(BiTree&T,ElemType e)if(!SearchBST(T,e.key,NULL,p)s=new BiTNode;/为新
19、结点分配空间为新结点分配空间s-data=e;s-lchild=s-rchild=NULL;if (!p)T=s;/插入插入 s 为新的根结点为新的根结点 else if(e.keydata.key)p-lchild=s;/插入插入*s 为为*p 的左孩子的左孩子else p-rchild=s;/插入插入*s 为为*p 的右孩子的右孩子 return 1;/插入成功插入成功 else return 0;/Insert BST503080209085403588325050503040355050809047 一个无序序列可以通过构造一棵二一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列
20、叉排序树而变成一个有序序列 每次插入的新结点都是二叉排序树每次插入的新结点都是二叉排序树上新的叶子结点上新的叶子结点 插入时不必移动其它结点，仅需修插入时不必移动其它结点，仅需修改某个结点的指针改某个结点的指针结论结论48二叉排序树的删除算法二叉排序树的删除算法 和插入相反，删除在查找成功之后进行，并和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。然保持二叉排序树的特性。可分三种情况讨论：可分三种情况讨论：被删除的结点是叶子；被删除的结点是叶子；被删除的结点只有左子树或者只有右子树；被删除的结点只有左
21、子树或者只有右子树；被删除的结点既有左子树，也有右子树被删除的结点既有左子树，也有右子树。4950308020908540358832（1）被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”5050308020908540358832（2）被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字=40805150308020908540358832（3）被删除的
22、结点既有左子树，也有右子树既有左子树，也有右子树4040以其前驱替代之，然以其前驱替代之，然后再删除该前驱结点后再删除该前驱结点被删结点前驱结点被删关键字被删关键字=5052Status DeleteBST(BiTree&T,KeyType key)/若二叉排序树若二叉排序树 T 中存在其关键字等于中存在其关键字等于 key 的的 /数据元素，则删除该数据元素结点，并返回数据元素，则删除该数据元素结点，并返回 /函数值函数值 TRUE，否则返回函数值，否则返回函数值 FALSE if(!T)return FALSE;/不存在关键字等于key的数据元素 else /DeleteBST算法描述如下
23、：算法描述如下：53if(EQ(key,T-data.key)/找到关键字等于key的数据元素else if(LT(key,T-data.key)else Delete(T);return TRUE;DeleteBST(T-lchild,key);/继续在左子树中进行查找DeleteBST(T-rchild,key);/继续在右子树中进行查找54void Delete(BiTree&p)/从二叉排序树中删除结点 p，/并重接它的左子树或右子树 if(!p-rchild)else if(!p-lchild)else /Delete其中删除操作删除操作过程如下所描述：55p/右子树为空树则只需重接
24、它的左子树q=p;p=p-lchild;delete(q);pqq56/左子树为空树只需重接它的右子树q=p;p=p-rchild;delete(q);ppqq57q=p;s=p-lchild;while(!s-rchild)q=s;s=s-rchild;/s 指向被删结点的前驱/左右子树均不空p-data=s-data;if(q!=p)q-rchild=s-lchild;else q-lchild=s-lchild;/重接*q的左子树delete(s);s58PCpFPRfCLQSLQLSqsfCpFPRSCLQQLSLqsfLpFPRPCLqsq=p;s=p-lchild;while(!s
25、-rchild)q=s;s=s-rchild;/s 指向被删结点的前驱/左右子树均不空p-data=s-data;if(q!=p)q-rchild=s-lchild;/重接*q的右子树 else q-lchild=s-lchild;/重接*q的左子树delete(s);59二叉排序树查找性能的分析二叉排序树查找性能的分析 对于每一棵特定的二叉排序树，均可按照对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的平均查找长度的定义来求它的 ASL 值，显然，值，显然，由值相同的由值相同的 n 个关键字，构造所得的不同形态个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长的各棵二叉排
26、序树的平均查找长 度的值不同，度的值不同，甚至可能差别很大。甚至可能差别很大。60由关键字序列由关键字序列 3，1，2，5，4构造构造而得的二叉排序树而得的二叉排序树由关键字序列由关键字序列 1，2，3，4，5构构造而得的二叉排序树，造而得的二叉排序树，例如：例如：2134535412ASL=（1+2+3+4+5）/5 =3ASL=（1+2+3+2+3）/5 =2.261 二叉平衡树是二叉查找树的另一种形式，其二叉平衡树是二叉查找树的另一种形式，其特点为：树中每个结点的左、右子树深度之差特点为：树中每个结点的左、右子树深度之差的绝对值不大于的绝对值不大于1 1RLhh例如例如:54825482
27、1是平衡树是平衡树不是平衡树不是平衡树平衡二叉树平衡二叉树62v 构造二叉平衡（查找）树的方法构造二叉平衡（查找）树的方法：在插入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。例如例如:依次插入的关键字为依次插入的关键字为5,4,2,8,6,94258665842先向右旋转再向左旋转542向右旋转一次6584263426589426895向左旋转一次继续插入关键字 964哈希表的相关定义哈希表的相关定义哈希函数的构造方法哈希函数的构造方法处理冲突的方法处理冲突的方法哈希表的查找哈希表的查找哈希表的插入哈希表的插入哈希查找分析哈希查找分析哈希表哈希表 hash 65哈希查找哈希查找:
28、又叫散列查找，利用哈希函数进行查找又叫散列查找，利用哈希函数进行查找的过程。的过程。基本思想基本思想：在记录的存储地址和它的关键字之间：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。一次存取就能得到所查元素的查找方法。哈希函数哈希函数:在记录的关键字与记录的存储地址之间在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。从关键字空间到存储地址空间的一种映象。可写成，可写成，addr(ai
29、)=H(ki)其中：其中：ai是表中的一个元素是表中的一个元素 addr(ai)是是ai的存储地址的存储地址 ki是是ai的关键字的关键字哈希表的相关定义哈希表的相关定义66哈希表哈希表根据设定的哈希函数根据设定的哈希函数 H(key)和所选中和所选中的处理冲突的方法，将一组关键字映象到的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集一个有限的、地址连续的地址集(区间区间)上，上，并以关键字在地址集中的并以关键字在地址集中的“象象”作为相应作为相应记录在表中的存储位置，如此构造所得的记录在表中的存储位置，如此构造所得的查找表称之为查找表称之为“哈希表哈希表”。67例例 30个地
30、区的各民族人口统计表个地区的各民族人口统计表编号编号 地区地区 总人口总人口 汉族汉族 回族回族1 北京北京2 上海上海.以编号作关键字，以编号作关键字，构造构造哈希函数：哈希函数：H(key)=keyH(1)=1H(2)=2以地区名作关键字，取地区以地区名作关键字，取地区名称第一个拼音字母的序号名称第一个拼音字母的序号作哈希函数：作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=1968从例子可见：从例子可见：哈希函数只是一种映象，所以哈希哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关函数的设定很灵活，只要使任何关键字的哈希函数值都落在
31、表长允许键字的哈希函数值都落在表长允许的范围之内即可。的范围之内即可。冲突：冲突：key1 key2，但，但H(key1)=H(key2)的现象的现象69哈希函数构造的方法哈希函数构造的方法直接定址法直接定址法数字分析法数字分析法平方取中法平方取中法折叠法折叠法除留余数法除留余数法随机数法随机数法70哈希函数为关键字的线性函数哈希函数为关键字的线性函数 H(key)=key 或者或者 H(key)=a key+b此法仅适合于：此法仅适合于：地址集合的大小地址集合的大小=关键字集合的大小关键字集合的大小其中其中a和和b为常数为常数直接定址法直接定址法71 数字分析法数字分析法 假设关键字集合中的
32、每个关键字假设关键字集合中的每个关键字都是由都是由 s 位数字组成位数字组成(u1,u2,us)，分析关键字集中的全体，分析关键字集中的全体，并从中提取并从中提取分布均匀的若干位或它们的组合作为分布均匀的若干位或它们的组合作为地址。此法地址。此法适于适于能预先估计出全体关能预先估计出全体关键字的每一位上各种数字出现的频度。键字的每一位上各种数字出现的频度。72例例 有有80个记录，关键字为个记录，关键字为8位十进制数，位十进制数，哈希地址为哈希地址为2位十进制数位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78
33、1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5.分析：分析：只取只取8 只取只取1 只取只取3、4 只取只取2、7、5 数字分布近数字分布近 乎随机乎随机所以：取所以：取任意两位任意两位 或两位或两位 与另两位的叠加作哈与另两位的叠加作哈 希地址希地址73 以关键字的平方值的中间几位作为存储地以关键字的平方值的中间几位作为存储地址。求址。求“关键字的平方值关键字的平方值”的目的是的目的是“扩大扩大差别差别”，同时平方值的中间各位又能受到整，同时平方值的中间各位又能受到整个关键字中各位的影响。个关键字中各位的影响。此方法适合
34、于此方法适合于:关键字中的每一位都有某些数字重复出现频关键字中的每一位都有某些数字重复出现频度很高的现象。度很高的现象。平方取中法平方取中法 74将关键字分割成若干部分，然后取它们的叠加将关键字分割成若干部分，然后取它们的叠加和为哈希地址。和为哈希地址。两种叠加处理的方法：两种叠加处理的方法：移位叠加移位叠加:将分割后的几部分低位对齐相加将分割后的几部分低位对齐相加间界叠加间界叠加:从一端沿分割界来回折送，然后对从一端沿分割界来回折送，然后对齐相加齐相加(此法适于关键字的数字位数特别多此法适于关键字的数字位数特别多)折叠法折叠法 例例 关键字为关键字为：0442205864，哈希地址位数为，哈
35、希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加75除留余数法除留余数法 设定哈希函数为设定哈希函数为:H(key)=key MOD p (pm)其中，其中，m为为表长表长 p 为不大于为不大于 m 的质数的质数 或是或是 不含不含 20 以下的质因子以下的质因子76 给定一组关键字为给定一组关键字为:12,39,18,24,33,21，若取若取 p=9,则他们对应的哈希函数值将为则他们对应的哈希函数值将为:3,3,0,6,6,3可见，若可见，若 p
36、中含质因子中含质因子 3,则所有含质因子则所有含质因子 3 的的关键字均映射到关键字均映射到“3 的倍数的倍数”的地址上，从而增的地址上，从而增加了加了“冲突冲突”的可能的可能例如：例如：为什么要对为什么要对 p 加限制？加限制？77随机数法随机数法设定哈希函数为设定哈希函数为:H(key)=Random(key)其中，其中，Random 为伪随机函数为伪随机函数此法用于构造关键字长度不等的哈希函数。此法用于构造关键字长度不等的哈希函数。选取哈希函数考虑的因素：选取哈希函数考虑的因素：计算哈希函数所需时间计算哈希函数所需时间关键字长度关键字长度哈希表长度（哈希地址范围）哈希表长度（哈希地址范围
37、）关键字分布情况关键字分布情况记录的查找频率记录的查找频率 78处理冲突的方法处理冲突的方法 “处理冲突处理冲突”的实际含义是：的实际含义是：为产生冲突的地址寻找下一个哈希地址。为产生冲突的地址寻找下一个哈希地址。开放定址法开放定址法 再哈希法再哈希法 链地址法链地址法79为产生冲突的地址为产生冲突的地址 H(key)求得一个地求得一个地址序列：址序列：H0,H1,H2,Hs 1sm-1Hi=(H(key)+di)MOD m 其中：其中：i=1,2,sH(key)为哈希函数为哈希函数;m为哈希表长为哈希表长;di为增量序列为增量序列,有下列三种取法有下列三种取法:开放定址法开放定址法80对增量
38、对增量 di 的三种取法：的三种取法：1)线性探测再散列线性探测再散列 di=c i 最简单的情况最简单的情况 c=12)二次探测再散列二次探测再散列 di=12,-12,22,-22,3)随机探测再散列随机探测再散列 di 是一组伪随机数列是一组伪随机数列 或者或者 di=iH2(key)(又称双散列函数探测又称双散列函数探测)81注意：注意：增量增量 di 应具有应具有“完备性完备性”即：产生的即：产生的 Hi 均不相同，且所产生的均不相同，且所产生的 s(m-1)个个 Hi 值能覆盖哈希表中所有值能覆盖哈希表中所有 地址。则要求：地址。则要求：平方探测时的表长平方探测时的表长 m 必为形
39、如必为形如 4j+3 的素数（如的素数（如:7,11,19,23,等）；等）；随机探测时的随机探测时的 m 和和 di 没有公因子。没有公因子。82例例 表长为表长为11的哈希表中已填有关键字为的哈希表中已填有关键字为17，60，29的记录，的记录，H(key)=key MOD 11,现有第现有第4个记录，个记录，其关键字为其关键字为38，按三种处理冲突的方法，将它填，按三种处理冲突的方法，将它填入表中入表中(1)H(38)=38 MOD 11=5 冲突冲突 H1=(5+1)MOD 11=6 冲突冲突 H2=(5+2)MOD 11=7 冲突冲突 H3=(5+3)MOD 11=8 不冲突不冲突(
40、2)H(38)=38 MOD 11=5 冲突冲突 H1=(5+1)MOD 11=6 冲突冲突 H2=(5-1)MOD 11=4 不冲突不冲突(3)H(38)=38 MOD 11=5 冲突冲突 设伪随机数序列为设伪随机数序列为9，则：，则：H1=(5+9)MOD 11=3 不冲突不冲突0 1 2 3 4 5 6 7 8 9 1060 17 2938383883例如例如:给定关键字集合构造哈希表给定关键字集合构造哈希表 19,01,23,14,55,68,11,82,36 设定哈希函数设定哈希函数 H(key)=key MOD 11(表长表长=11)190123 145568190123 1468
41、若采用线性探测再散列处理冲突若采用线性探测再散列处理冲突若采用二次探测再散列处理冲突若采用二次探测再散列处理冲突11 8236551182361 1 2 1 3 6 2 5 184将所有哈希地址相同的记录都链接在同一链表中。将所有哈希地址相同的记录都链接在同一链表中。例例:给定关键字给定关键字 19,01,23,14,55,68,11,82,36 哈希函数为哈希函数为 H(key)=key MOD 7 链地址法链地址法 550123456 11 198268 1436 01 23 85例例 已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希
42、函数为：哈希函数为：H(key)=key MOD 13,用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 1412779685519842023101186再哈希法再哈希法方法：构造若干个哈希函数，当发方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，生冲突时，计算下一个哈希地址，直到冲突不再发生。直到冲突不再发生。即：即：Hi=Rhi(key)i=1,2,k其中：其中：Rhi不同的哈希函数不同的哈希函数特点：计算时间增加特点：计算时间增加87哈希查找过程哈希查找过程给定给定k值值计算计算H(k)此地址为空此地址为空关键字关键字=k查找失败
43、查找失败查找成功查找成功按处理冲突按处理冲突方法计算方法计算HiYNYN哈希表的查找哈希表的查找对于给定值对于给定值 K,K,计算哈希地址计算哈希地址 i=H(K)i=H(K)若若 ri=NULL ri=NULL 则查找不成功则查找不成功 若若 ri.key=K ri.key=K 则查找成功则查找成功 否则否则“求下一地址求下一地址 Hi”Hi”，直至，直至rHi=rHi=NULL (NULL (查找不成功查找不成功)或或rHi.key=K (rHi.key=K (查查找成功找成功)为止。为止。88例例 已知一组关键字已知一组关键字(19,14,23,1,68,20,84,27,55,11,1
44、0,79)哈希函数为哈希函数为H(key)=key MOD 13,哈希表长为哈希表长为 m=16，用线性探测再散列处理冲突得哈希表用线性探测再散列处理冲突得哈希表 给定值给定值K=38的查找过程为的查找过程为:H(38)=12 不空且不等于不空且不等于38,冲突冲突H1=(12+1)MOD16=13空记录空记录表中不存在关键字等于表中不存在关键字等于38 的记录的记录,查找不成功。查找不成功。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1514 168 27 55 19 20 84 79 23 11 10给定值给定值K=84的查找过程为的查找过程为:H(84)=6 不
45、空且不等于不空且不等于84,冲突冲突H1=(6+1)MOD16=7不空且不等于不空且不等于84,冲突冲突 H2=(6+2)MOD16=8不空且等于不空且等于84,查找成功查找成功,返回记录在表中的序号。返回记录在表中的序号。89int SearchHash(HashTable H,KeyType K,int&p,int&c)/在开放定址哈希表在开放定址哈希表H中查找关键码为中查找关键码为K的记录的记录/探查地址的次数探查地址的次数p=Hash(K);/求得哈希地址求得哈希地址while(H.elemp.key!=NULLKEY&(K!=H.elemp.key)collision(p,+c);/
46、求得下一探查地址求得下一探查地址 pif(K=H.elemp.key)return SUCCESS;/查找成功，返回待查数据元素位置查找成功，返回待查数据元素位置 pelse return UNSUCCESS;/查找不成功查找不成功/SearchHash查找算法查找算法90int InsertHash(HashTable&H,ElemType e)int p,c=0;if(SearchHash(H,e.key,p,c)=SUCCESS)return DUPLICATE;/表中已有与表中已有与 e 有相同关键字的元素有相同关键字的元素 else if(c hashsize/2)/冲突次数冲突次数
47、 c 未达到上限，（阀值未达到上限，（阀值 c 可调）可调）H.elemp=e;+H.count;return 1;/查找不成功时，返回查找不成功时，返回 p为插入位置为插入位置 else RecreateHashTable(H);/重建哈希表重建哈希表/InsertHash哈希表的插入哈希表的插入91哈希表查找的分析哈希表查找的分析 从查找过程得知，哈希表查找的平均查找长度从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。实际上并不等于零。决定哈希表查找的决定哈希表查找的ASL的因素：的因素：1)选用的哈希函数选用的哈希函数;2)选用的处理冲突的方法选用的处理冲突的方法;3)哈希表饱
48、和的程度，哈希表饱和的程度，装载因子装载因子:=n/m 值的大小值的大小（n表中填入的记录数，表中填入的记录数，m表的长度）表的长度）装填因子越小，表中填入的装填因子越小，表中填入的记录就越少，发生冲突的记录就越少，发生冲突的可能性就会小，反之，表可能性就会小，反之，表中已填入的记录越多，再中已填入的记录越多，再填充记录时，发生冲突的填充记录时，发生冲突的可能性就越大，则查找时可能性就越大，则查找时进行关键字的比较次数就进行关键字的比较次数就越多。越多。92 一般情况下，可以认为选用的哈希函数一般情况下，可以认为选用的哈希函数是是“均匀均匀”的，则在讨论的，则在讨论ASL时，可以不考虑时，可以
49、不考虑它的因素。它的因素。因此，哈希表的因此，哈希表的ASL是处理冲突方法和装载因是处理冲突方法和装载因子的函数。子的函数。例如：前述例子例如：前述例子线性探测处理冲突时，线性探测处理冲突时，ASL=22/9双散列探测处理冲突时，双散列探测处理冲突时，ASL=14/9链地址法处理冲突时，链地址法处理冲突时，ASL=13/9 93线性探测再散列线性探测再散列链地址法链地址法随机探测再散列随机探测再散列)111(21nlS)1ln(1nrS21ncS可以证明：查找成功时有下列结果：可以证明：查找成功时有下列结果：94从以上结果可见，从以上结果可见，哈希表的平均查找长度是哈希表的平均查找长度是 的函
50、数的函数，而不是而不是 n 的函数。的函数。这说明，用哈希表构造查找表时，这说明，用哈希表构造查找表时，可以选择一个适当的装填因子可以选择一个适当的装填因子 ，使得使得平均查找长度限定在某个范围内。平均查找长度限定在某个范围内。这是哈希表所特有的特点。这是哈希表所特有的特点。951设有序表为a,b,c,d,e,f,g，请分别画出对给定值f,g和h进行拆半查找的过程。2.设散列表长m=14，哈希函数为H(k)=k mod 11，表中一共有8个元素15,27,50,73,49,61,37,60，试画出采用二次探测法处理冲突的散列表。3.线性表的关键字集合为113,12,180,138,92,67,
