首页 > 试题广场 >

设有n个关键字具有相同的Hash函数值，则用线性探测法把这n

[单选题]
设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做几次线性探测？ 
  • n2
  • n*(n+1)
  • n*(n+1)/2
  • n*(n-1)/2
查看答案及解析
添加回答
推荐
叶小鱼头像 叶小鱼
第一个关键字直接插入，第二个关键字要做1次探测，所以类推n个关键词要做0+1+2+...+(n-1) = n*(n-1) / 2 答案是D
编辑于 2015-02-03 18:12:26 回复(10)
dkplatform头像 dkplatform
首先要看清题目，题目问的是需要几次线性探测，
第一次不需要线性探测。
第二次之后的每一次都会发生冲突，都需要进行线性探测
结果为
1+2+3+。。。+n-1 = (n-1)n/2
发表于 2015-08-22 19:22:57 回复(1)
美团到店招聘头像 美团到店招聘
不要纠结于文字游戏！
如果第一次不算线性探测，那就是0+1+2+......n-1
如果第一次算线性探测，那就是1+2+3+....n
地球人都知道在考啥，纠结这些就没意思了。
发表于 2017-02-19 17:10:36 回复(10)
喜一阿夏头像 喜一阿夏
<p>线性探测比探测次数要少算一次，第一次算探测但不算线性探测，线性探测是产生冲突以后才做的</p>
发表于 2020-09-10 21:33:39 回复(0)
风不动心动头像 风不动心动
这两题是不是有一题答案是错的？？
发表于 2019-06-08 14:56:03 回复(0)
牛客716543232号头像 牛客716543232号
这题问的是做多少次线性探测（冲突才使用），第一个关键字不冲突，所以执行k(k-1)/2次。
要是问的是做多少次探测（冲突与否都要执行），所有关键字都要探测，所以执行k(k+1)/2次。
发表于 2023-02-18 17:09:36 回复(0)
fast-is-slow头像 fast-is-slow
假设有大小为n的未填充的数组，将n个哈希冲突的元素插入，第一个探测次数为0，第二个探测次数为1...第n个探测次数为n-1，根据等差数列求和得出探测次数为n(n-1)/2
发表于 2022-08-03 09:37:25 回复(0)
id_9527头像 id_9527
第三个吧，直接插入也算一次探测啊，前面有一题答案就是直接插入算一次探测。。
发表于 2018-08-05 15:40:33 回复(0)
阳光依旧smile头像 阳光依旧smile
看清题目 映射表示插入 直接插入是0次线性探测
发表于 2016-04-14 10:50:06 回复(0)
GoAshore头像 GoAshore
有这个选这个，没有这个选＋1那个
发表于 2022-11-30 19:01:04 回复(0)
牛客951254626号头像 牛客951254626号
几次探测-比较次数 几次线性探测-函数执行了多少次 如果问需要几次探测，应该是n*(n+1)/2 如果问几次线性探测，应该是n*(n-1)/2
发表于 2021-12-01 17:12:11 回复(0)
烬天玉藻前头像 烬天玉藻前
用线性探测法来解决n个关键字具有相同哈希值会造成聚集现象，就是这些哈希值都排在一起了。
第1个数直接插入，
第2个数需要探测1次，再插入，
以此类推
总探测次数 = 0 + 1 + 2 +...+ (n - 1) = (n-1+0)*n/2
发表于 2020-08-21 23:01:10 回复(0)
牛客218196695号头像 牛客218196695号
要点第一次是必有得 从第二次开始线性探测 （1+2+  ....... n-1）  所以为(n)*(n-1)/2
发表于 2020-05-21 16:16:12 回复(0)
Juvenile少年头像 Juvenile少年

发表于 2019-12-20 16:37:09 回复(0)
名字是谷雨头像 名字是谷雨
插入不算探测次数
发表于 2019-10-16 17:10:00 回复(0)
灰灰_两个人儿头像 灰灰_两个人儿
忘记了，第一次不用做，只需要是n*(n-1)
发表于 2019-07-27 08:38:29 回复(0)
一念清浊头像 一念清浊
这题真没意思，前两天做到一个一模一样的题，那里给的第一次算答案是C，这里又不算答案是D，有意思吗？
发表于 2019-04-15 09:54:55 回复(0)
蒋娜蝶头像 蒋娜蝶
线性探测解决冲突的办法指一旦目标空间被占有，则探测相邻的下一个空间，如果空闲则插入，否则继续向下一个探测，如果到了队列末尾则返回队列头探测，一旦全部空间都被占据则无法插入。
发表于 2018-12-04 15:55:05 回复(0)
放开那个女孩，我来头像 放开那个女孩，我来

k个关键字在依次填入的过程中，只有第一个不会发生冲突，限行探测次数应该为c选项🙃🙃🙃

选d的laji

发表于 2018-11-09 14:46:53 回复(1)
梦境迷离头像 梦境迷离
第一次不算探测，可以瞎跳？
发表于 2017-12-04 20:52:45 回复(0)
^O^201710210945219头像 ^O^201710210945219
n(n-1)/2
发表于 2017-10-21 12:12:35 回复(0)
提交观点

问题信息

哈希 人人网
来自：人人网2015研发笔试卷C
上传者：Joyce
难度：
26条回答 26767浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号