首页 > 试题广场 >

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

[填空题]
设哈希表长m=14,哈希函数H(key)=key%11。表中已有4个结点:addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7,其余地址为空。如果用二次探测再散列处理冲突,关键字为49的结点的地址是1
这题电击小子回答好像是错的,根据数据结构Java实现这本书5.4.2,二次探测探测的是散列表,而不是在Hash值,是取得Hash值之后采用12、22、也就是addr(n)=hash(n)+i2 (i从0开始取),好像也有addr(n)=hash(n)±i2 ,即先实验+1再实验-1,依次
编辑于 2019-08-08 10:30:21 回复(8)
插入前15,38,61,84的H(key)分别为:4,5,6,7 存放地址为4,5,6,7  
49的H(key)为5,发生冲突.  
用二次探测再散列法解决冲突:  
1:(49+1^2)%11=(49+1)%11=6,仍然发生冲突.  
2:(49-1^2)%11=(49-1)%11=4,仍然发生冲突.  
3:(49+2^2)%11=(49+4)%11=9,不再发生冲突.  
故选D。

发表于 2019-08-06 20:43:12 回复(1)
有关哈希表二次探测再散列处理冲突可以看以下图片:解决 hash 碰撞-开放定址法-二次探查法部分

编辑于 2019-10-21 16:49:52 回复(0)
前一段时间做了一个用线性探测再散列的题,今天又补了一下二次探测再散列😂🤣🤣🤣
对于处理冲突数据结构书(C语言版)上有一个公式:
Hi = ( H (key) + di ) MOD  m
其中i=1,2,3,......k(k<=m-1)、H(key)为哈希函数、m为哈希表表长;di为增量序列。
当di=1,2,3,....m-1,称为线性探测再散列;
当di=(正负)K^2(K=1,2,3,...m/2)称为二次探测再散列(先正后负)
题目中哈希表长为14,所以代入后应该是这样的:
H1=(5+1)%14=6  冲突
H1=(5-1)%14=4 冲突
H2=(5+4)%14=9 无冲突
所以结果为9

若有错误,还请路过的大牛们指正,多谢
发表于 2019-08-12 15:38:52 回复(5)

9

发表于 2019-10-18 12:37:34 回复(0)
先用49%11=5,本来应该存在地址为5的位置
但是5已经存了,用二次探测法处理冲突
5存了就看6存了没有,6也存了再看4,4还存了就看9,如果9也存了数据再找1;
依次找的是 5,6(5+1^2),4(5-1^2),9(5+2^2),1(5-2^2),14(5+3^2).....
直到找到空位  
发表于 2019-09-17 17:20:14 回复(0)

9


发表于 2019-12-27 13:31:55 回复(0)
9
发表于 2019-12-03 22:19:44 回复(0)
9
发表于 2019-11-14 23:48:30 回复(0)