首页 > 试题广场 >

设哈希表长为14,哈希函数为h(key)=key%11。表中

[单选题]

设哈希表长为14,哈希函数为h(key)=key%11。表中现有数据15、38、61和84,其余位置为空,如果用二次探测再散列处理冲突,则49的位置是

  • 8
  • 3
  • 5
  • 9
处理的冲突的一种方式
开放定址法:Hi=(H(key)+di)MOD m,其中H(key)为哈希函数;m为哈希表长;di为增量序列,可有以下三种取法:
<1>di=1,2,3,......m-1,称为线性探测再散列;
<2>di=1^2,-1^2,2^2,-2^2.......k^2,-k^2,(k<=m/2),称为二次探测再散列
<3>di=伪随机数序列,称伪随机探测再散列
哈希表如下
0
1
2
3
4
5
6
7
8
9
10
11
12
13




15
38
61
84






以此将15、38、61和84代入 哈希函数求的如上表
然后49%11=5%14=5有冲突,然后分别将di=1,-1代入都有冲突,
当di=4时没有冲突 所以49的位置是5+4=9


编辑于 2017-06-20 10:38:43 回复(7)
线性探测再散列的增量序列为1,-1,4,-4,9,-9
Hi(key) = (H(key)+增量)%哈希表长
H1 = (5+1)%14 = 6
H2 = (5-1)%14 = 4
H3 = (5+4)%14 = 9
发表于 2017-08-01 17:24:25 回复(0)
15,38,61,84依次哈希值4,5,6,7
49---》5与38冲突,用二次探测再散列:di=12-1222-22…,k2-k2    ( k<=m/2 )
公式为:Hi=(H(key)+di% m   i=1,2,…,n
H1 = (5+1**2)%11 = 6冲突
H1 = (5-1**2)%11 = 4冲突
H1 = (5+2**2)%11 = 9不冲突,即为9
发表于 2019-05-15 09:15:58 回复(0)
为什么不是8,8的位置还空着
 5+4=9   4是怎么来的,49除以11的商吗
发表于 2021-04-09 14:55:29 回复(1)
开放地址法:Hi=(H(key)+di) mod m,   其中H(key)为哈希函数,m为哈希表长,di为增量序列,增量序列有以下取法:
(1):  di=1,2,3,4....,m-1 称为线性探测再散列
(2):  di=1^2 ,- 1^2,2^2,- 2^2,.....,k^2,-k^2(k<=m/2),称为二次探测再散列
(3):di=伪随机数序列,称为随机探测再散列;
发表于 2018-07-22 15:54:03 回复(0)
这道题目我有异议,我选5,有没有一样的小伙伴呀,15是在4,38在6,5不是空着吗,怎么还到9去了
发表于 2017-11-25 17:25:09 回复(6)