电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

哈希表查找成功和不成功的算法

哈希表查找成功和不成功的算法_第1页
1/9
哈希表查找成功和不成功的算法_第2页
2/9
哈希表查找成功和不成功的算法_第3页
3/9
哈希表查找不成功怎么计算? 解答:先建好表,然后可以算出每个位置不成功时的比较次数之和,再除以表空间个数! 例如:散列函数为hash(x)=x MOD 13,用线性探测,建立了哈希表之后,如何求查找不成功时的平均查找长度!? 地址: 0 1 2 3 4 5 6 7 8 9 10 11 12 数据: 39 12 28 15 42 44 6 25 - - 36 - 38 成功次数: 1 3 1 2 2 1 1 9 1 1 不成功次数: 9 8 7 6 5 4 3 2 1 1 2 1 10 查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2 查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54 说明: 第n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。 至少要查询多少次才能确认没有这个值。 (1) 查询 hash(x)=0,至少要查询 9次遇到表值为空的时候,才能确认查询失败。 (2) 查询 hash(x)=1,至少要查询 8次遇到表值为空的时候,才能确认查询失败。 (3) 查询 hash(x)=2,至少要查询 7次遇到表值为空的时候,才能确认查询失败。 (4) 查询 hash(x)=3,至少要查询 6次遇到表值为空的时候,才能确认查询失败。 (5) 查询 hash(x)=4,至少要查询 5次遇到表值为空的时候,才能确认查询失败。 (6) 查询 hash(x)=5,至少要查询 4次遇到表值为空的时候,才能确认查询失败。 (7) 查询hash(x)=6,至少要查询3次遇到表值为空的时候,才能确认查询失败。 (8) 查询hash(x)=7,至少要查询2次遇到表值为空的时候,才能确认查询失败。 (9) 查询hash(x)=8,至少要查询1次遇到表值为空的时候,才能确认查询失败。 (10)查询hash(x)=9,至少要查询1次遇到表值为空的时候,才能确认查询失败。 (11)查询hash(x)=10,至少要查询2次遇到表值为空的时候,才能确认查询失败。 (12)查询hash(x)=11,至少要查询1次遇到表值为空的时候,才能确认查询失败。 (13)查询hash(x)=12,至少要查询10次遇到表值为空(循环查询顺序表)的时候,才能确认查询失败。 下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。 Question1: 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从 0开始的一维数组,散列函数为:H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为 0.7。...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

哈希表查找成功和不成功的算法

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部