我要招人

去企业版

首页 > 试题广场 >

已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测

[单选题]

已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行____次探测。

```
n-1
```
```
n
```
```
n+1
```
```
n(n+1)
```
```
n(n+1)/2
```
```
1+n(n+1)/2
```

查看答案及解析

推荐

￥種田￥

二次探测再散列 
{   D = H(key);  
    ND = (D+di)%m;　　di 取 1*1,-1*1,2*2,-2*2,……,K*K,-K*K 　(K≤m/2)
　　 值得提醒的是，对利用开放地址法查了冲突所产生的哈希表中删除一个元素，不能简单地直接删除，因为这样将截断其它具有相同哈希地址的元素的查找地址，所以应设定一个特殊的标志以表明该元素已被删除。

编辑于 2015-11-15 11:27:33 回复(1)

向宇铜桌

二次探测的哈希函数h(k,i)=(h'(k)+C1*i+C2*i^2)mod m，假设n个关键字具有相同的哈希值，也就是它们的h'(k)是一样的，那么先插第1个关键字，需要探测1次；接着插第2个关键字，i=0,第1次探测将会冲突，i=1,理想情况下，第2次就不会冲突了。依次类推，插第n个关键字，需要探测n次。所以总共要1+2+3+…n=n(n+1)/2次探测。

发表于 2015-11-30 16:58:19 回复(0)

侯卿

问的是“至少”，那么设表原来为空表。

第一个：直接找到坑，入坑，1次；

第二个：和第一个同hash，找到坑被第一个给占了，找下一个，入坑，2次；

第三个：第一个被占了，第二个也被占了，找第三个，入坑，3次；

。。。

第n个：n次；

一共：（1+n）*n / 2 次

【二次探测属于开放地址法，开放地址法（除了随机探测）都是（1+n）*n / 2 次】

发表于 2018-04-21 21:43:37 回复(1)

嘻嘻兔

题目中明确是问几次探测，而不是几次二次线性探测。因此第一次探测为空，插入元素，也计算在内。

发表于 2016-03-21 21:29:04 回复(5)

Aban

E 一共有n个相同哈希值的数，插入第一个时探测一次。最佳情况下第二个数插入时额外探测一次，以此类推，第n个数最少需要探测n次，1+2+....+n = n(n + 1) / 2

发表于 2018-03-07 16:54:33 回复(0)

细雨湿身

发表于 2016-09-15 22:56:08 回复(0)

天尊墨宇

选E

二次探测再散列 
{   D = H(key);  
    ND = (D+di)%m;　　di 取 1*1,-1*1,2*2,-2*2,……,K*K,-K*K 　(K≤m/2)
　　 值得提醒的是，对利用开放地址法查了冲突所产生的哈希表中删除一个元素，不能简单地直接删除，因为这样将截断其它具有相同哈希地址的元素的查找地址，所以应设定一个特殊的标志以表明该元素已被删除。

发表于 2020-07-14 15:43:27 回复(0)

Spectre_

发表于 2019-10-15 23:27:59 回复(0)

fy_bihan

每次都从头节点遍历嘛？？

发表于 2018-12-02 14:44:47 回复(0)

求一个offer555

第i个数对应i次探测，所以是1+2+...+n，即为n * (n + 1) / 2

发表于 2018-10-25 19:08:00 回复(0)

Mark宇宙

1 + 2 + ... + n

发表于 2018-10-25 17:28:22 回复(0)

processzero

怎么感觉牛客的题质量越来越不保证了？？之前遇到的几道题第一个有坑直接入的就不算一次探测，现在又算了，发题之前没人审核的吗？好坑！

发表于 2018-07-01 11:42:43 回复(1)

谱乐

开放地址法除了随机探测都是n*(n+1)/2

发表于 2018-06-11 21:20:35 回复(0)

Anoyer_元戎内推：AEMTt

E 1+2+3+4+5+.......n

发表于 2018-03-06 19:18:30 回复(0)

好吃不过炸酱面

1+2-3+....+n

发表于 2017-07-01 18:40:37 回复(0)

霞43

插入第一个关键字就算探测一次？？

发表于 2017-06-11 09:28:51 回复(1)

sherryNie

完全搞不清楚。。。

发表于 2016-07-11 17:15:56 回复(0)

名字多响亮

n个关键字具有相同的哈希值的话，不应该只需要再探测(n-1)个关键字吗？怎么会全部关键字都需要探测呢？

发表于 2016-03-09 21:27:06 回复(1)

提交观点

问题信息

哈希

上传者：陈木木

难度：

18条回答 508收藏 20310浏览

已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测

问题信息

热门推荐

相关试题