我要招人

去企业版

首页 > 试题广场 >

采用线性探测的方式解决冲突，访问hash表的次数分别为多少？

[填空题]

有一个数组（53,83,18,59,38,35），依次将其存储在hash表中，其中哈希函数为h(k)=k%7,如采用线性探测（每次向后查找1位）的方式解决冲突，则该hash表上查找38,35,53访问hash表的表项次数分别为1，2，3。

查看正确选项

牛客-007

答：5,1,1
先求出其哈希值
53 % 7 = 4 83 % 7 = 6 18 % 7 = 4
59 % 7 = 3 38 % 7 = 3 35 % 7 = 0
则存储位置如下：
53->4, 83->6, 18->5(本来是4，由于冲突向后一位)
59->3, 38->7(本来是3，由于冲突，第四位也已经被占用，继续向后移动至到遇到空位存放)
35->0
查找38，从第3个位置找起，直道第7个位置找到，访问5次
查找35，从第0个位置找起，访问1次找到
查找53，从第4个位置找起，访问1次找到

编辑于 2015-07-30 21:50:23 回复(12)

奋斗的小鸟

因为hash函数是%7,因此hash的slot是0-6编号的

0---->38

1---->35

2---->

3---->59

4---->53

5---->18

6---->83

答案:应该是5 2 1

发表于 2015-07-30 20:16:26 回复(2)

Prokias

我认为答案是：5,2,1，因为38占了0的坑，所以，35必须找2次！

发表于 2015-07-29 19:43:30 回复(0)

公众号:重温新知

发表于 2017-04-27 14:33:15 回复(0)

牛客687564号

应该是5,2,1，因为38求于的3一直往后查找到6还不可以，因为最大为六，所以存在0,35求于得0，往后一到1，所以为5,2,1

发表于 2016-03-29 17:11:30 回复(0)

watermaker

53%7=4；

83%7=6；

18%7=4；

59%7=3；

38%7=3;

35%7=0；

哈希表查找次数

0-->38 5

1-->35 2

2-->

3-->59 1

4-->53 1

5-->18 2

6-->83 1

发表于 2015-09-04 16:29:05 回复(0)

代码王子

5, 2, 1

原因：对于38%7 = 3，但是执行到38时，hash表内下标3,4,5,6都已经被占用，因此38放进下标0内，一共5次

对于35%7 = 0，但是0处已经被38占用，只能后移一位到下标1处，一共2次

对于53%7 = 4，1次即可

发表于 2015-08-18 20:48:40 回复(0)

reakingf

%7的结果即对应在hash表中的位置如下：

53 --> 4 没有冲突，所以对应位置为4

83 --> 6 没有冲突，所以位置为6

18 --> 4 与53冲突，向后线性探测，位置5为空，可以放，位置为5

59 --> 3 无冲突，位置为3

38 --> 3 与59冲突，向后线性探测，直到位置0为空，所以位置为0

35 --> 0 与38冲突，向后线性探测，位置1位空，所以位置为1

结果如下

所以，查找38时，先查找位置3，没找到，往后直到位置0才找到，从位置3到位置0总共查找了5次；

查找35，从0到1，查找了2次；

查找53，直接找到，1次。

编辑于 2016-09-11 11:36:02 回复(0)

牛客338329号

注意表长！！！！本题中数组表长为6 所以在计算38时没有第七个位置回回到第0个位置！！！

发表于 2017-03-24 13:06:47 回复(0)

小呆瓜

为什么长度为7？？

发表于 2016-08-03 16:41:57 回复(0)

huixieqingchun

注意哈希表的运算。这是里线性探测，如果产生冲突，每次向后移动一位。

发表于 2016-05-05 21:51:56 回复(0)

啥

答案为5 2 1，如下：

53： 4

83： 6

18： 4->5

59： 3

38： 3->4->5->6->0

35： 0->1

发表于 2015-12-05 21:55:44 回复(0)

Black_Mamba2

38 35 没注意到7和0 得出5 1 1

发表于 2015-09-10 10:34:26 回复(1)

ゝ少年の幻想ゝ

没有冲突就访问一次找到

发表于 2015-09-08 23:03:24 回复(0)

阿喵仔

0.1.4吧

发表于 2015-08-14 11:02:43 回复(1)

SPACELAN

k%7意思是循环的？超过第6位就要回到第0位开始找？

发表于 2015-08-06 15:56:37 回复(0)

浩大仙

郁闷，忘了38到7就换成0了，5,2,1必须的必

发表于 2015-07-31 12:53:37 回复(0)

得得小泽

应该是5 2 1 我爱你

发表于 2015-07-30 18:43:50 回复(0)

combatant

即使hash表长度不为7，当我们插入38时，位置3被占了，同理，位置4，5，6也都被占了，当为7时，7%7 = 0，那么还是要回到位置0上，所以位置0为38，位置1为35。

查找38，从位置3开始，经历3，4，5，6，0，总共5次。

查找35，从位置0开始，经历0，1，总共2次。

查找53，从位置4开始，经历4，总共1次。

所以，我认为答案应该是5，2，1.

编辑于 2015-07-20 05:52:47 回复(1)

eagle

2， 1， 1

h(53) = 53 % 7 = 4

h(83) = 83 % 7 = 6

h(18) = 18 % 7 = 4

h(59) = 59 % 7 = 3

h(38) = 38 % 7 = 3

h(35) = 35 % 7 = 0

查38，会在3的表项上找，因为59已经存在这里了，所以得向后再访问一次，即2次

同理，查35，是1次

查53，是1次

发表于 2015-01-13 23:04:54 回复(0)

提交观点

问题信息

网易网易互娱哈希游戏研发工程师 2015

来自：2015网易互娱校园招...

上传者：小牧魔法袋

难度：

20条回答 413收藏 14609浏览

采用线性探测的方式解决冲突，访问hash表的次数分别为多少？

问题信息

热门推荐

相关试题