设为首页收藏本站
  • 官方微信
    微信公众号 添加方式:
    1:搜索微信号(888888
    2:扫描左侧二维码
  • 手机访问
  • 领取福利
    开启辅助访问 天气与日历 切换风格

    生活录-艾狐网- 山西论坛,太原人自己的干支论坛【www.tyltw.com】

     找回密码
     立即注册

    QQ登录

    只需一步,快速开始

    查看: 105|回复: 6

    问道真题,知道地方不对,但这儿人气高,(*^__^*) 嘻嘻……

    [复制链接]

    15

    主题

    74

    帖子

    161

    积分

    注册会员

    Rank: 2

    积分
    161
    发表于 2022-6-26 00:49:06 | 显示全部楼层 |阅读模式 <
    <
    2010年41题,第二问,查找不成功平均长度,答案给的序列是3,2,1,2,1,5,4             除以7,得平均18/7,不明白,那个序列怎么得到的,求大神解答,拜谢
    来源于:网络
    免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
    <


    分享到:

    22

    主题

    2万

    帖子

    1万

    积分

    论坛元老

    Rank: 8Rank: 8

    积分
    19168
    发表于 2022-6-26 01:03:07 | 显示全部楼层 <
    不成功的查找长度就是说在你得到所要查找的哈希值以后运用线性探查再散列的方法找到空白的表项需要的比较次数。序列指的是你的元素映射在哈希表第0,第1,第2.。。项时查找失败所需要的步数。这里是假设映射到各个位置是等概率的,所以均值这么求,因为你MOD7的话,H(key)的值是0-6。比较困了,如果有什么不对的地方,欢迎提出!



    回复

    使用道具 举报

    6

    主题

    53

    帖子

    112

    积分

    注册会员

    Rank: 2

    积分
    112
    发表于 2022-6-26 01:17:56 | 显示全部楼层 <
    [table][tr][td]下标[/td][td]0 [/td][td]1 [/td][td]2[/td][td]3 [/td][td]4 [/td][td]5 [/td][td]6 [/td][td]7 [/td][td]8 [/td][td]9 [/td][/tr][tr][td]关键字[/td][td]7[/td][td]14[/td][td][/td][td]8 [/td][td][/td][td]11[/td][td]30[/td][td]18[/td][td]9[/td][td]回复 2# aljjj
    这是散列表,怎么感觉,数字序列还是不对啊



    回复

    使用道具 举报

    22

    主题

    2万

    帖子

    1万

    积分

    论坛元老

    Rank: 8Rank: 8

    积分
    19168
    发表于 2022-6-26 01:26:12 | 显示全部楼层 <
    下标   0  1   2  3  4   5    6    7   8  9  
    关键字 7 14      8      11  30  18  9



    回复

    使用道具 举报

    15

    主题

    74

    帖子

    161

    积分

    注册会员

    Rank: 2

    积分
    161
     楼主| 发表于 2022-6-26 01:38:52 | 显示全部楼层 <
    回复 2# aljjj


        谢谢学长,还是没懂啊,学长



    回复

    使用道具 举报

    22

    主题

    2万

    帖子

    1万

    积分

    论坛元老

    Rank: 8Rank: 8

    积分
    19168
    发表于 2022-6-26 01:50:17 | 显示全部楼层 <
    回复 5# conrad


        那我举个例子说明第一个数字为什么是3。首先,你现在需要查找的key会映射到0这个项,但是0里面有项目而且与你所要查找的key不相等,所以你得用线性探查再散列查找下一个位置,你找到了编号为1的项,这时候情况和0是一样的,那你需要继续寻找下一个位置,终于你找到了2号位置,这个位置里面是空白的,找到这个地方就能说明你想要找的key不在这个散列表中,而且你需要的比较次数是3。以此类推,你要寻找H(key)=1,2,3,4,5,6(因为是mod7,所以只有这么几个值)时查找失败需要的比较次数也就是上述的序列表示的意思。那个序列不是散列表中的值,而是当key映射到这个项时查找失败需要的步长。



    回复

    使用道具 举报

    15

    主题

    74

    帖子

    161

    积分

    注册会员

    Rank: 2

    积分
    161
     楼主| 发表于 2022-6-26 01:56:40 | 显示全部楼层 <
    回复 6# aljjj


        看半天明白了,下标0,查找3次,下标1,查找2次,下标2,查找1次,下标3,查找2次,下标4,查找1次,下标5,查找5次,下标6,查找4次,到此为止。谢谢学长不嫌麻烦这么详细的介绍



    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则 需要先绑定手机号

    官方微博:

    官方公众号:

    官方微信

    手机APP下载:

    官方微信

    QQ手机版 生活录 Discuz! X3.4 Powered by © 2001-2013 Comsenz Inc.|网站地图|网站地图|友链申请 


    备案号:晋ICP备2022005057号-1

    快速回复 快速发帖 返回顶部 返回列表