首页 > 试题广场 >

哈希查找中k个关键字具有同一哈希值,若用线性探测法将这k个关

[单选题]
哈希查找中k个关键字具有同一哈希值,若用线性探测法将这k个关键字对应的记录存入哈希表中,至少要进行(    )次探测。
  • k
  • k+1
  • k(k+1)/2
  • 1+k(k+1)/2
这题,,,牛客能不能不出错题啊。。。
审核严谨点,
发表于 2017-08-07 09:02:21 回复(1)
发表于 2018-01-11 21:07:56 回复(0)
问的是“至少”,那么设表原来为空表。
第一个:直接找到坑,入坑,1次;
第二个:和第一个同hash,找到坑被第一个给占了,找下一个,入坑,2次;
第三个:第一个被占了,第二个也被占了,找第三个,入坑,3次;
。。。
第n个:n次;
一共:(1+n)*n / 2 次
【开放地址法(除了随机探测)都是(1+n)*n / 2 次】
编辑于 2018-04-21 21:44:23 回复(2)
①如果按照线性探测的定义来说,只有存在冲突之后才算是探测,也就是说插入第一个0探测,第二个1探测,因此总的应该是k(k-1)/2;
②但是题中给出的答案没有这个选项,所以,题中是规定了插入也算探测,即插入第一个1探测,第二个2探测,因此总的是k(k+1)/2。
发表于 2018-04-06 09:46:39 回复(1)
当哈希表为空时,第一个插入的关键字要算探测吗?
这题是要算,可是另一道题就没算了???

发表于 2020-08-21 23:16:32 回复(0)
<p>探测是包括第一次检测</p><p>线性探测是冲突后所需的检测</p>
发表于 2020-10-17 14:29:20 回复(0)
应该是k*(k-1)/2次。因为第一个不需要探测,只需要探测除第一个外的k-1个
发表于 2019-11-25 18:52:01 回复(0)
应该是(k-1)^2/2吧
发表于 2017-12-27 11:24:53 回复(0)