首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
哈希查找中k个关键字具有同一哈希值,若用线性探测法将这k个关
[单选题]
哈希查找中k个关键字具有同一哈希值,若用线性探测法将这k个关键字对应的记录存入哈希表中,至少要进行( )次探测。
k
k+1
k(k+1)/2
1+k(k+1)/2
查看正确选项
添加笔记
求解答(18)
邀请回答
收藏(259)
分享
8个回答
添加回答
3
zhlovy
这题,,,牛客能不能不出错题啊。。。
审核严谨点,
发表于 2017-08-07 09:02:21
回复(1)
16
我学十年君一年,君拿BA我无T
发表于 2018-01-11 21:07:56
回复(0)
14
侯卿
问的是“至少”,那么设表原来为空表。
第一个:直接找到坑,入坑,1次;
第二个:和第一个同hash,找到坑被第一个给占了,找下一个,入坑,2次;
第三个:第一个被占了,第二个也被占了,找第三个,入坑,3次;
。。。
第n个:n次;
一共:(1+n)*n / 2 次
【开放地址法(除了随机探测)都是(1+n)*n / 2 次】
编辑于 2018-04-21 21:44:23
回复(2)
12
zurp
①如果按照线性探测的定义来说,只有存在冲突之后才算是探测,也就是说插入第一个0探测,第二个1探测,因此总的应该是k(k-1)/2;
②但是题中给出的答案没有这个选项,所以,题中是规定了插入也算探测,即插入第一个1探测,第二个2探测,因此总的是k(k+1)/2。
发表于 2018-04-06 09:46:39
回复(1)
4
烬天玉藻前
当哈希表为空时,第一个插入的关键字要算探测吗?
这题是要算,可是另一道题就没算了???
发表于 2020-08-21 23:16:32
回复(0)
2
摆烂了的小冤种很热爱生活
<p>探测是包括第一次检测</p><p>线性探测是冲突后所需的检测</p>
发表于 2020-10-17 14:29:20
回复(0)
0
jfjdjdjs
应该是k*(k-1)/2次。因为第一个不需要探测,只需要探测除第一个外的k-1个
发表于 2019-11-25 18:52:01
回复(0)
0
糊口口水
应该是(k-1)^2/2吧
发表于 2017-12-27 11:24:53
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
哈希
上传者:
Letitia
难度:
8条回答
259收藏
6992浏览
热门推荐
相关试题
数据链路层滑动窗口机制中发送窗口(...
网络基础
评论
(1)
供受文者使用的具有法定效用的正式文...
京东
产品运营
2018
常识判断
行政
评论
(1)
有关linux线程的描述,正确的是...
京东
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
2018
评论
(1)
用一种动物介绍你自己
通用能力
评论
(1)
请你说几个海量数据存储常见问题以及...
评论
(1)
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题