采用线性火灾探测器探测法处理冲突的散列表中，同义...

来源：蜘蛛抓取(WebSpider) 时间：2011-09-28 11:57 标签： 线性火灾探测器
线性表的查找
树上的查找
处理冲突的方法
利用线性探测法构造散列表
　& 【例9.1】已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。
　　解答:为了减少冲突，通常令装填因子α&l。这里关键字个数n=10，不妨取m=13，此时α≈0.77，散列表为T[0..12]，散列函数为：h(key)=key％13。
&&& 　由除余法的散列函数计算出的上述关键字序列的散列地址为(0，10，2，12，5，2，3，12，6，12)。
&&& 　前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。
&&& 　当插入第6个关键字15时，其散列地址2(即h(15)=15％13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)％13=3，此地址开放，所以将15放入T[3]中。
&&& 　当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。
&&& 　当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此地址开放，可将12插入其中。
&&& 　类似地，第9个关键字06直接插入T[6]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。
&&& 　构造散列表的具体过程【】
聚集或堆积现象
　&&& 用线性探查法解决冲突时，当表中i,i+1，…，i+k的位置上已有结点时，一个散列地址为i，i+1，…，i+k+1的结点都将插入在位置i+k+1上。把这种散列地址不同的结点争夺同一个后继散列地址的现象称为聚集或堆积(Clustering)。这将造成不是同义词的结点也处在同一个探查序列之中，从而增加了探查序列的长度，即增加了查找时间。若散列函数不好或装填因子过大，都会使堆积现象加剧。
　　【例】上例中，h(15)=2，h(68)=3，即15和68不是同义词。但由于处理15和同义词41的冲突时，15抢先占用了T[3]，这就使得插入68时，这两个本来不应该发生冲突的非同义词之间也会发生冲突。
&&& 　为了减少堆积的发生，不能像线性探查法那样探查一个顺序的地址序列(相当于顺序查找)，而应使探查序列跳跃式地散列在整个散列表中。
&②二次探查法(Quadratic Probing)
&& 　二次探查法的探查序列是：
&&&&&&&& hi=(h(key)+i*i)％m
　　 即探查序列为d=h(key)，d+12，d+22，…，等。
&&& 　该方法的缺陷是不易探查到整个散列空间。
③双重散列法(Double Hashing)
&&& 　该方法是开放定址法中最好的方法之一，它的探查序列是：
&&&&&& hi=(h(key)+i*h1(key))％m
//即di=i*h1(key)
&&& 　即探查序列为：
&&&&&& d=h(key)，(d+h1(key))％m，(d+2h1(key))％m，…，等。
& 　该方法使用了两个散列函数h(key)和h1(key)，故也称为双散列函数探查法。
　&&& 定义h1(key)的方法较多，但无论采用什么方法定义，都必须使h1(key)的值和m互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。
　　【例】 若m为素数，则h1(key)取1到m-1之间的任何数均与m互素，因此，我们可以简单地将它定义为：
&&&&&&&&&&&&&&
h1(key)=key％(m-2)+1
　　【例】对例9.1，我们可取h(key)=key％13，而h1(key)=key％11+1。
　　【例】若m是2的方幂，则h1(key)可取1到m-1之间的任何奇数。您的访问出错了(404错误)
很抱歉，您要访问的页面不存在。
1、请检查您输入的地址是否正确。
进行查找。
3、感谢您使用本站，两秒后自动跳转至网站首页假定有k个关键字互为同义词,若用线性探测再散列法把这k个关键字存入散列表中,至少要进行____次探测.
ballance1﹔2岡
至少需要 1 + 2 + ...+ k-1 = k(k-1)/2 次探测.解析：在Hash表中存入第一个同义关键字后,后面至少连续有k-1个单元为空,则按线性探测再散列法可依次存入剩余的k-1个关键字,这样探测次数最少.
为您推荐：
其他类似问题
K（K+1）/2其实就是1+2+3+4+......+K每次存入关键字的时候都要探测的，只是如果冲突，再继续探测。
k(k-1)/2散列表的查找过程和建表过程类似。假设给定的值为K，根据建表时设定的散列函数H，计算出散列地址H(K)，若表中该地址对应的空间未被占用，则查找失败，否则将该地址中的值与K比较，若相等则查找成功，否则按建表时设定的处理冲突方法找下一个地址，如此反复下去，直到某个地址空间未被占用（查找失败）或者关键字比较相等（查找成功）为止。此处的查找就可以看成探测，固由以上结论得1...
扫描下载二维码散列冲突处理：开放定址法 -- 简明现代魔法博客访问： 707980
博文数量： 179
博客积分： 4132
博客等级： 中校
技术积分： 2020
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
利用线性探测法构造哈希表&&&&& 已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，用除余法构造散列函数，用线性探查法解决冲突构造这组关键字的散列表。　　解答:为了减少冲突，通常令装填因子α<l。这里关键字个数n=10，不妨取m=13，此时α≈0.77，散列表为T[0..12]，散列函数为：h(key)=key％13。&&& 　由除余法的散列函数计算出的上述关键字序列的散列地址为(0，10，2，12，5，2，3，12，6，12)。&&& 　前5个关键字插入时，其相应的地址均为开放地址，故将它们直接插入T[0]，T[10)，T[2]，T[12]和T[5]中。&&& 　当插入第6个关键字15时，其散列地址2(即h(15)=15％13=2)已被关键字41(15和41互为同义词)占用。故探查h1=(2+1)％13=3，此地址开放，所以将15放入T[3]中。&&& 　当插入第7个关键字68时，其散列地址3已被非同义词15先占用，故将其插入到T[4]中。&&& 　当插入第8个关键字12时，散列地址12已被同义词38占用，故探查hl=(12+1)％13=0，而T[0]亦被26占用，再探查h2=(12+2)％13=1，此地址开放，可将12插入其中。&&& 　类似地，第9个关键字06直接插入T[6]中；而最后一个关键字51插人时，因探查的地址12，0，1，…，6均非空，故51插入T[7]中。
阅读(7600) | 评论(0) | 转发(1) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。

我要回帖

更多关于 线性火灾探测器 的文章

 

随机推荐