数据结构第25讲：第10章查找表可扩充散列

《数据结构第25讲：第10章查找表可扩充散列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、哈希表是什么？二、哈希函数的构造方法三、处理冲突的方法四、哈希表的查找9.4哈希表五.可扩充散列1查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为:四、哈希表的查找对于给定值K,计算哈希地址Hi=H(K)若r[Hi].key=NULL则查找不成功若r[Hi].key=K则查找成功否则“求下一地址Hi”，直至r[Hi].key=NULL(查找不成功)或r[Hi].key=K(查找成功)为止。2inthashsize[]={997,...};//一个素数序列typedefstruct{ElemType*elem;//数据元素存储基址intcount;//当前数据元素

2、个数intsizeindex;//hashsize[sizeindex]为当前容量}HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1//---开放定址哈希表的存储结构---3StatusHashSearch(HashTableH,KeyTypeK,int&p,int&c){//p指示待查数据元素K在表中的位置，c为冲突计数}//SearchHashp=Hash(K);//求得哈希地址while(H.elem[p].key!=NULL&&//该位置有记录!EQ(K,H.elem[p].key)）//且不等于Kc

3、ollision(p,++c);//处理冲突,求得下一探查地址pif(EQ(K,H.elem[p].key))returnSUCCESS;//查找成功，返回待查数据元素位置pelsereturnUNSUCCESS;//查找不成功查找算法4StatusInsertHash(HashTable&H,Elemtypee){c=0;if(HashSearch(H,e.key,p,c)==SUCCESS)returnDUPLICATE;//表中已有与e有相同关键字的元素elseif(c

4、p]=e;++H.count;returnOK;//查找不成功时，返回p为插入位置}elseRecreateHashTable(H);//重建哈希表}//InsertHash插入算法5StatusDeleteHash(HashTable&H,Elemtypee){}//DeleteHashelse{H.elem[p]=null;--H.count;returnOK;}c=0;if(HashSearch(H,e.key,p,c)==UNSUCCESS)returnERROR;//表中无与e有相同关键字的元素删除算法H.Info[p]=deleted;//将待删除位置置为不可能//出

5、现的值.//将待删除位置用探测序列//的下一个关键字顺序递补.//另外定义一个删除标志数组//并置删除标志pH.InfoH.elem61)选用的哈希函数;2)选用的处理冲突的方法;3)哈希表饱和的程度：装载因子α=记录数/表的长度通常要求α≤0.5决定哈希表查找的ASL的因素：哈希表查找的分析:从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。7查找关键码时所需的平均查找次数在散列函数中，除留余数法优于其它类型的散列函数，最差的是折叠法。对于冲突处理方法：链地址法优于开放定址法；链地址法需要增设链接指针,增加了存储？由于开放定址法须保持大量的空闲空间以确保搜索效率，如平方

6、探查法要求装填因子0.5。而记录所占空间又比指针大得多，故链地址法反而节省存储空间。8用不同的冲突处理方法时散列表的平均查找长度如果取α＝0.51.52.521.251.19从以上结果可见，哈希表的平均查找长度是的函数，而不是n的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子，使得平均查找长度限定在某个范围内。——这是哈希表所特有的特点。10例1：求散列表大小并设计散列函数条件：设有一个含200个记录的散列表，要求用平方探查法解决冲突，且要求按关键码查询时，找到一个新记录插入位置的平均探查次数不超过1.5。问题：哈希表至少应该多大？并设计哈希函数。分析：对

7、平方探测法，查找不成功的平均搜索长度为Un＝1/(1-α),解答：根据要求n＝200，且：Un＝1/(1-α)1.51/3=n/m=200/mm60011一、哈希表是什么？二、哈希函数的构造方法三、处理冲突的方法四、哈希表的查找9.4哈希表五.可扩充散列12五.可扩充散列问题提出：1。再散列问题：对于静态散列表，无论使开发定址法还是链址法，都需要静态分配存储空间。如果表的记录太满，则查找和插入的时间将很长，甚至插入操作可能失败。由于静态散列表的长度不能够增加（?），解决