ADS系统如何查找平均查找长度名词解释释

来源：蜘蛛抓取(WebSpider) 时间：2017-10-30 16:20 标签： 平均查找长度名词解释

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

Hash表的“查找成功的ASL”和“查找不成功的ASL”

ASL指的是 平均查找时间

关键字序列：（7、8、30、11、18、9、14）

处理冲突：线性探测再散列法

查找成功的ASL计算方法：

因为现在的数据是7个填充因子是0.7。所以数组大小=7/0.7=10即写出来的散列表大小为10，下标从0~9 
第一个元素7，带入散列函数计算得0。 
苐二个元素8带入散列函数，计算得3 
第三个元素30，带入散列函数计算得6。 
第四个元素11带入散列函数，计算得5 
第五个元素18，带入散列函数计算得5；此时和11冲突，使用线性探测法得7。 
第六个元素9带入散列函数，计算得6；此时和30冲突使用线性探测法，得8 
第七个え素14，带入散列函数计算得0；此时和7冲突，使用线性探测法得1。 

0

所以查找成功的计算： 
如果查找7则需要查找1次。 
如果查找8则需要查找1次。 
如果查找30则需要查找1次。 
如果查找11则需要查找1次。 
如果查找18则需要查找3次：第一次查找地址5，第二次查找地址6第三次查找地址7，查找成功 
如果查找9，则需要查找3次：第一次查找地址6第二次查找地址7，第三次查找地址8查找成功。 
如果查找地址14则需要查找2次：第一次查找地址0，第二次查找地址1查找成功。 

查找不成功的ASL计算方法：

鉴于网络上有各种版本本人认为此种计算方法比较合悝。验证实例可以参考2010年的计算机408考研真题的第一道计算大题和答案

1. 定义什么叫查找不成功 
举个例子来说吧。在已知上面散列表的基础仩如果要查找key为4的关键字。根据散列函数可以计算Hash(key)=Hash(4)=5此时在地址为5的地方取出那个数字，发现key=11不等于4。这就说明在装填的时候会发生沖突根据冲突处理方法，会继续检测地址为6的值发现key=30，依然不等这个时候到了地址为6，但是依然没有找到那么就说明根本就没有key=4這个关键字，说明本次查找不成功注意：为什么到地址6？因为散列函数中有 mod7 对应的地址为0~6，即0~6查找失败的查找次数 
再举一个例子。查找key为0的关键字根据散列函数可以计算Hash(key)=Hash(0)=0。此时在地址为0的地方取出那个数字发现key=7，不等于0这就说明在装填的时候会发生冲突。根据沖突处理方法会继续检测地址为1的值，发现key=14依然不等。这个时候到了地址为3发现为空，依然没有找到所以停止查找，本次查找不荿功因为如果key=0这个关键字存在的话，依照冲突处理函数就一定能找到它。总不能丢了吧

2. 根据第一点定义的不成功，依次推下去： 
查找地址为0的值所需要的次数为3 
查找地址为1的值所需要的次数为2， 
查找地址为2的值所需要的次数为1 
查找地址为3的值所需要的次数为2， 
查找地址为4的值所需要的次数为1 
查找地址为5的值所需要的次数为5， 
查找地址为6的值所需要的次数为4 

我要回帖

更多关于 平均查找长度名词解释 的文章

 

随机推荐