首页 > 试题广场 >

假设把整数关键字K Hash到有N个槽的散列表，以下哪些散列

[单选题]

假设把整数关键字K Hash到有N个槽的散列表，以下哪些散列函数比较合适（）

```
H(K)=k/N
```
```
H(k)=k mod N
```
```
H(k)=1
```

H(k)=(k+Random(N))mod N，其中Random(N)返回0到N-1的整数

查看答案及解析

牛客-007

答案：D

设把整数关键字K Hash到有N个槽中，首先要考虑K>N的情况，所以要modN保证hash值落在0~N-1之间

所以A和C选项是不合适的

其实考虑K<<N的情况，如果 K远小于N，则B选项中的K mod N =K，这只能保证前K个槽中有值，不能起到散列的作用，因此B选项不合适

D选项中(k+Random(N))mod N得到0到N-1之间的随机值，符合条件

编辑于 2015-08-05 13:10:26 回复(5)

王俊超

答案是B

D是错误的，Random(N)返回0-N的整数，在查找的时候会出现问题，再次使用Random(N)不一定和上次存储产生的数字一样，这样子就会发生找不到的情况，而且题库还有道题与这个题目一样的，答案是B

发表于 2015-07-30 18:11:35 回复(9)

本命年的Offer！

什么鬼题，解析都不一样。。。不过应该是B吧(虽然我选的是D)，但是D在插入数据的时候应该可以解决冲突的问题，但是在查找的时候可能会找不到，因为是随机的嘛

发表于 2017-10-08 08:49:09 回复(1)

为梦奔跑

答案：B。 D选项的散列效果不如B选项好，若Random(N)恒等于0或N，则B，D等价，现 Random(N)为0~N-1, 无形中增加了不同K值散列为同一N位置的可能性。

如：k分别=1、2、3、4.....N-1， Random(N)分别为N-1、N-2、N-3、N-4......1， H(k)=(k+Random(N))mod N都等于0，相同散列值。而B选项避免了这写情况。

同时增加了相同K值散列到不同N位置的可能性，

对于牛客-007的观点不敢苟同，

散列本质上是存储，查找技术，最重要满足：K₁不等于K₂时，H(k₁)不等于 H(k₂)

“ 其实考虑K<<N的情况，如果 K远小于N，则B选项中的K mod N =K，这只能保证前K个槽中有值，不能起到散列的作用，因此B选项不合适”这种说法不合适

K<<N的情况，B、D都满足 K ₁ 不等于K ₂ 时， H(k₁)不等于 H(k₂)，但由于 K<<N，两者HASH表的利用率都极低，所以这两种散列函数都不理想。

发表于 2016-08-22 12:19:47 回复(0)

菜鸟女程序员

随机的可以么？不能再次找到吧？

发表于 2015-07-23 07:48:30 回复(1)

牛客854470544号

记忆有点错乱了,b选项是hash的除留余数法的哈希函数
d选项是hash除余法的解决冲突的调整方法之一开放地址法中的一种(随机数法)

开放地址法还有还有线性探测和二次探测法两种形式

发表于 2023-05-19 20:27:31 回复(0)

Sakura丶薄荷

除留余数法构建哈希表，N 一般选择不超过 K 的最大素数。

发表于 2022-12-30 10:56:42 回复(0)

云云云一飞冲天

光考虑处理哈希冲突的问题了，结果忘记了最基本的查哈希的时候每次应该是相同的，不应该是随机的。ε=(´ο｀*)))

发表于 2022-08-20 11:39:10 回复(0)

恶寒轻轻

D确实是因为无法查找到

发表于 2021-11-26 17:34:04 回复(0)

牛客554761865号

d插入可以解决哈希冲突和堆积问题，但是因为加上随机数后无法查找，所以d排除

发表于 2020-04-25 19:59:46 回复(0)

孤单的跟鞋声和你的笑丶

a明显不行的啊，n的选取有讲究的，要是小于n的最大素数才好

发表于 2017-11-21 21:21:50 回复(0)

Waleee

应该是多选题b，d

发表于 2016-06-07 10:25:58 回复(0)

妞妞粉

支持二楼的说法，选d

发表于 2016-03-31 11:52:03 回复(0)

慎独之客

例如k序列12，24，36，48，60，72

H(k)=k mod 12
序列都为0，A是有问题的

发表于 2016-02-28 20:15:23 回复(0)

张客牛

为了体现哈希表查找插入删除O(1)特性，必须保证查找稳准狠，虽然H(K)=K mod N比较简单，课本上讲了一个利用Horner法则的散列函数

发表于 2015-11-01 12:19:35 回复(0)

disibutatian

(1)A,C 明显错误，不能保证一定在（0--N)之间，B，D都可以，D更好，解释见楼下。

(2)选B,D

发表于 2015-05-20 22:54:21 回复(0)

提交观点

问题信息

欢聚集团组合数学哈希

上传者：小牧魔法袋

难度：

16条回答 626收藏 16036浏览

假设把整数关键字K Hash到有N个槽的散列表，以下哪些散列

问题信息

热门推荐

相关试题