《数据结构 第九章 动态查找.ppt》由会员分享，可在线阅读，更多相关《数据结构 第九章 动态查找.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 一、哈希表是什么？一、哈希表是什么？二、哈希函数的构造方法哈希函数的构造方法 三、处理冲突的方法处理冲突的方法 四、哈希表的查找哈希表的查找 五、哈希表的删除操作哈希表的删除操作 六、哈希表也可用来构造静态查找表哈希表也可用来构造静态查找表9.3 哈哈 希希 表表 以上两节讨论的表示查找表的各种结构结构的共同特点特点：记录在表中的位置位置和它的关键关键字字之间不存在不存在一个确定的关系，一、哈希表是什么？哈希表是什么？查找的过程查找的过程为给定值给定值依次和关键字集合中各个关键字关键字进行比较比较，查找的效率查找的效率取决于和给定值进行比较进行比较的关键字个数个数。用这类方法表示的查找表，其
2、平均查找长度都不为零。不同的表示方法，其差别仅在于：差别仅在于：关键字和给定值进行比较的顺序不同。只有一个办法：预先知道所查关键字在表中的位置，对于频繁使用的查找表，希望 ASL=0。即，要求：记录在表中位置和其关键字之间存在一种确定的关系。若以下标为以下标为000 999 的顺序表的顺序表表示之。例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999(前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较不需要经过比较便可直接从顺序表中找到待查关键字。但是，对于动态查找表动态查找表而言，因此在一般情况下，需在关键字与
3、记录在表中的存储位置之间建立一个函数关系，以 f(key)作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key)为哈希函数。1)表长不确定；2)在设计查找表时，只知道关键字所属 范围，而不知道确切的关键字。Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dai 例如：对于如下 9 个关键字设设 哈希函数哈希函数 f(key)=(Ord(第一个字母第一个字母)-Ord(A)+1)/2 ChenZhaoQianSunLiWuHanYeDai问题问题:若添加关键字 Zhou,怎么办？怎么办？能否找到能否找到另一个哈希函数？1)哈希函数是一个映象映象，即：将关键字将关键
4、字的集合映射到某个地址集合上的集合映射到某个地址集合上，它的设置很灵活灵活，只要这个地址集地址集合的大小不超出允许不超出允许范围范围即可；从这个例子可见：从这个例子可见：2)由于哈希函数是一个压缩映象压缩映象，因此，在一般情况下，很容易产生“冲突冲突”现象，即：key1 key2，而 f(key1)=f(key2)。3)很难很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”的方法。哈希表的定义：根据设定的哈希函数哈希函数 H(key)
5、和所选中的处理冲突的方法处理冲突的方法，将一组关键字映象到映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置存储位置，如此构造所得的查找表称之为“哈希表哈希表”。二、构造哈希函数的方法构造哈希函数的方法 对数字数字的关键字可有下列构造方法：若是非数字关键字非数字关键字，则需先需先对其进进行数字化处理行数字化处理。1.直接定址法直接定址法3.平方取中法平方取中法5.除留余数法除留余数法4.折叠法折叠法6.随机数法随机数法2.数字分析法数字分析法哈希函数为关键字的线性函数 H(key)=key 或者 H(key)=a key+b1.直接定址法直接
6、定址法此法仅适合于：此法仅适合于：地址集合的大小地址集合的大小=关键字集合的大小关键字集合的大小此方法仅适合于：此方法仅适合于：能预先估计出预先估计出全体关键字的每一位每一位上上各种数字出现的频度数字出现的频度。2.数字分析法数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。3.平方取中法平方取中法此方法适合于此方法适合于:关键字中的每一位都有某些数字重复出现
7、频度很高的现象。将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加移位叠加和间界叠加间界叠加。4.折叠法折叠法此方法适合于此方法适合于:关键字的数字位数特别多。5.除留余数法除留余数法 设定哈希函数为设定哈希函数为:H(key)=key MOD p 其中其中，pm(表长表长)并且并且 p 应为不大于应为不大于 m 的素数的素数 或是或是 不含不含 20 以下的质因子以下的质因子 给定一组关键字为：12,39,18,24,33,21，若取 p=9,则他们对应的哈希函数值将为：3,3,0,6,6,3例如：例如：为什么要对 p 加限制？可见，若 p 中含质因子 3，
8、则所有含质因则所有含质因子子 3 的关键字均映射到的关键字均映射到“3 的倍数的倍数”的地址上的地址上，从而增加了“冲突”的可能。6.随机数法随机数法设定哈希函数为设定哈希函数为:H(key)=Random(key)其中，其中，Random 为伪随机函数为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。实际造表时，采用何种采用何种构造哈希函数的方法方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的的原则原则是是使产生冲突的可能性降到使产生冲突的可能性降到尽可能地小尽可能地小。三、处理冲突的方法处理冲突的方法 “处理冲突处理冲突”的实际含义是：为产生冲突的地址寻找下一个
9、寻找下一个哈希地址。1.开放定址法开放定址法2.链地址法链地址法 为产生冲突的地址 H(key)求得一个地址序列地址序列：H0,H1,H2,Hs 1 sm-1其中：H0=H(key)Hi=(H(key)+di)MOD m i=1,2,s1.开放定址法开放定址法对增量 di 有三种取法：1)线性探测再散列线性探测再散列 di=c i 最简单的情况 c=12)平方探测再散列平方探测再散列 di=12,-12,22,-22,3)随机探测再散列随机探测再散列 di 是一组伪随机数列伪随机数列 或者 di=iH2(key)(又称双散列函数探测又称双散列函数探测)即：产生的 Hi 均不相同，且所产生的s(
10、m-1)个个 Hi 值能覆盖覆盖哈希表中所有地址。则要求：注意：注意：增量增量 di 应具有应具有“完备性完备性”随机探测时的 m 和 di 没有公因子。平方探测时的表长 m 必为形如 4j+3 的素数（如:7,11,19,23,等）；例如例如:关键字集合 19,01,23,14,55,68,11,82,36 设定设定哈希函数 H(key)=key MOD 11(表长=11)190123 145568190123 1468若采用线性探测再散列线性探测再散列处理冲突若采用二次探测再散列二次探测再散列处理冲突11 8236551182361 1 2 1 3 6 2 5 1 H2(key)是另设定的
11、一个哈希函数，它的函数值应和 m 互为素数。若 m 为素数，则 H2(key)可以是 1 至 m-1 之间的任意数任意数；若 m 为 2 的幂次，则H2(key)应是 1 至 m-1 之间的任意奇数任意奇数。例如，当 m=11时，可设 H2(key)=(3 key)MOD 10+11901231455681182362 1 1 1 2 1 2 1 3将所有哈希地址相同的记录将所有哈希地址相同的记录都链接在同一链表中。都链接在同一链表中。2.链地址法链地址法0123456140136198223116855 ASL=(61+22+3)/9=13/9例如:同前例的关键字，哈希函数为 H(key)=
12、key MOD 7 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程查找过程为：四、哈希表的查找哈希表的查找 对于给定值 K，计算哈希地址 i=H(K)若若 ri=NULL 则查找不成功若若 ri.key=K 则查找成功否则否则“求下一地址 Hi”，直至 rHi=NULL (查找不成功)或 rHi.key=K (查找成功)为止。int hashsize=997,.;typedef struct ElemType *elem;int count;/当前数据元素个数当前数据元素个数 int sizeindex;/hashsizesizeindex为当前容为当前容量量 HashTable
13、;#define SUCCESS 1#define UNSUCCESS 0#define DUPLICATE -1/-开放定址哈希表开放定址哈希表的存储结构-Status SearchHash(HashTable H,KeyType K,int&p,int&c)/在开放定址哈希表在开放定址哈希表H中查找关键码为中查找关键码为K的记录的记录/SearchHashp=Hash(K);/求得哈希地址求得哈希地址while(H.elemp.key!=NULLKEY&!EQ(K,H.elemp.key)）collision(p,+c);/求得下一探查地址求得下一探查地址 pif(EQ(K,H.elemp
14、.key)return SUCCESS;/查找成功，返回待查数据元素位置查找成功，返回待查数据元素位置 pelse return UNSUCCESS;/查找不成查找不成功功Status InsertHash(HashTable&H,Elemtype e)/InsertHashc=0;if(HashSearch(H,e.key,p,c)=SUCCESS)return DUPLICATE;/表中已有与表中已有与 e 有相同关键字的元素有相同关键字的元素else H.elemp=e;+H.count;return OK;/查找不成功时，返回查找不成功时，返回 p为插入位置为插入位置else Recr
15、eateHashTable(H);/重建哈希表重建哈希表 if(c hashsizeH.sizeindex/2)/冲突次数冲突次数 c 未达到上限，（阀值未达到上限，（阀值 c 可调）可调）1)选用的哈希函数哈希函数；2)选用的处理冲突的方法处理冲突的方法；3)哈希表饱和的程度，装载因子装载因子 =n/m 值的大小大小（n记录数，记录数，m表的长度）表的长度）决定哈希表查找的决定哈希表查找的ASL的因素的因素：哈希表查找的分析:从查找过程得知，哈希表查找的平均查找长度实际上并不等于零实际上并不等于零。一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。因此，哈
16、希表的因此，哈希表的ASL是是处理冲突方法处理冲突方法和和装装载因子载因子的函数。的函数。例如：前述例子线性探测处理冲突时，ASL=双散列探测处理冲突时，ASL=链地址法处理冲突时，ASL=22/914/913/9线性探测再散列线性探测再散列链地址法链地址法随机探测再散列随机探测再散列可以证明：查找成功查找成功时有下列结果：从以上结果可见：哈希表的平均查找长度是 的函数，而不是 n 的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子 ，使得平均查找长度限定在某个范围内平均查找长度限定在某个范围内。这是哈希表所特有的特点。这是哈希表所特有的特点。从哈希表中删除记录时，要作特特殊处理
17、殊处理，相应地，需要修改查找的算法。五、哈希表的删除操作五、哈希表的删除操作六、哈希表也可以用来构造静态查六、哈希表也可以用来构造静态查找表找表 并且，对静态查找表，有时可以对静态查找表，有时可以找到不发生冲突的哈希函数。即，此时的哈希表的哈希表的 ASL=0,称此类哈希函数为理想（perfect）的哈希函数。1.顺序表顺序表和有序表有序表的查找方法及其平均查找长度的计算方法。2.熟练掌握二叉排序树二叉排序树的构造和查找方法。本章学习要点本章学习要点 3.理解B-树树、B+树和键树树和键树的特点以及特点以及它们的建树和查找的过程。它们的建树和查找的过程。4.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。5.掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。