首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
设哈希表长m=14,哈希函数H(key)=key%11。表中
[填空题]
设哈希表长m=14,哈希函数H(key)=key%11。表中已有4个结点:addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空。如果用二次探测再散列处理冲突,关键字为49的结点的地址是
1
查看正确选项
添加笔记
求解答(14)
邀请回答
收藏(197)
分享
纠错
9个回答
添加回答
9
张云超
这题电击小子回答好像是错的,根据数据结构Java实现这本书5.4.2,二次探测探测的是散列表,而不是在Hash值,是取得Hash值之后采用
1
2
、2
2
、也就是
addr(n)=hash(n)+i
2
(i从0开始取),好像也有
addr(n)=hash(n)±i
2
,即先实验+1再实验-1,依次
编辑于 2019-08-08 10:30:21
回复(8)
11
嘿哈biu
插入前15,38,61,84的H(key)分别为:4,5,6,7 存放地址为4,5,6,7
49的H(key)为5,发生冲突.
用二次探测再散列法解决冲突:
1:(49+1^2)%11=(49+1)%11=6,仍然发生冲突.
2:(49-1^2)%11=(49-1)%11=4,仍然发生冲突.
3:(49+2^2)%11=(49+4)%11=9,不再发生冲突.
故选D。
发表于 2019-08-06 20:43:12
回复(1)
1
程序猿Go师傅
有关哈希表二次探测再散列处理冲突可以看以下图片:
解决 hash 碰撞-
开放定址法-
二次探查法部分
编辑于 2019-10-21 16:49:52
回复(0)
10
長歌當行
前一段时间做了一个用线性探测再散列的题,今天又补了一下二次探测再散列
😂
🤣
🤣
🤣
对于处理冲突数据结构书(C语言版)上有一个公式:
Hi = ( H (key) + di ) MOD m
其中i=1,2,3,......k(k<=m-1)、H(key)为哈希函数、m为哈希表表长;di为增量序列。
当di=1,2,3,....m-1,称为线性探测再散列;
当di=(正负)K^2(K=1,2,3,...m/2)称为二次探测再散列(先正后负)
题目中哈希表长为14,所以代入后应该是这样的:
H1=(5+1)%14=6 冲突
H1=(5-1)%14=4 冲突
H2=(5+4)%14=9 无冲突
所以结果为9
若有错误,还请路过的大牛们指正,多谢
发表于 2019-08-12 15:38:52
回复(5)
1
卖女孩的小火柴20181211163556
9
发表于 2019-10-18 12:37:34
回复(0)
1
卓卓卓卓卓~
先用49%11=5,本来应该存在地址为5的位置
但是5已经存了,用二次探测法处理冲突
5存了就看6存了没有,6也存了再看4,4还存了就看9,如果9也存了数据再找1;
依次找的是 5,6(5+1^2),4(5-1^2),9(5+2^2),1(5-2^2),14(5+3^2).....
直到找到空位
发表于 2019-09-17 17:20:14
回复(0)
0
stich
9
发表于 2019-12-27 13:31:55
回复(0)
0
尼根的猜想
9
发表于 2019-12-03 22:19:44
回复(0)
0
_老地方
9
发表于 2019-11-14 23:48:30
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
C++工程师
瓜子二手车
哈希
2019
Java工程师
上传者:
小小
难度:
9条回答
197收藏
8361浏览
热门推荐
相关试题
(verbal)最近的研究显示,许...
言语理解与表达
2019
普华永道
人力资源
审计
税务服务
风险管理
管理咨询
行政管理
评论
(2)
来自
职能类模拟题14
关于C++中的new和C语言中的m...
C++
Java工程师
C++工程师
算法工程师
瓜子二手车
2019
评论
(18)
(verbal)最近的研究显示,许...
言语理解与表达
2019
普华永道
人力资源
审计
税务服务
风险管理
管理咨询
行政管理
评论
(3)
来自
职能类模拟题14
之前的经历中单品数据分析的经验丰富...
评论
(1)
2022 诺瓦科技 Perl re...
perl
System Verilog
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题