首页 > 试题广场 >

设哈希表长m=9.哈希函数H(key)=key%7。表中已填

[单选题]

设哈希表长m=9.哈希函数H(key)=key%7。表中已填关键字：13,25,68，其余地址为空，如用二次探测再散列处理冲突，关键字为75的地址是（）。

Tom_jerry

13: 6
25: 4
68: 5
di=1,-1,4,-4,9,-9...
75%7=5,
5+1=6冲突，5-1=4冲突，5+4=9大于表的长度，实际结果为0

发表于 2018-05-01 15:39:19 回复(0)

牛客882122502号

开放定址法：

H_i=(H(key)+d_i) MOD m

m为哈希表的表长，i=1,2,...,k(k<=m-1)

二次探测的d_i=1²,-1²,2²,-2²,...,+k²,-k²(k<=m/2)

(5+1)%9=6,仍冲突

(5-1)%9=4,仍冲突

(5+4)%9=0，可以存放

为什么地址不为0

发表于 2021-04-06 23:05:05 回复(0)

牛客274233608号

选A

双重散列法(Double Hashing)

该方法是开放地址法中最好的方法之一，它的探查序列是：

hi=(h(key)+i*h1(key))%m 0≤i≤m-1 //即di=i*h1(key)

即探查序列为：

d=h(key)，(d+h1(key))%m，(d+2h1(key))%m，…，等。

该方法使用了两个散列函数h(key)和h1(key)，故也称为双散列函数探查法。

d1=75%7=5 d2=(5+5)%9=1

发表于 2020-11-22 18:31:35 回复(1)

风吹列子归

D， H(75)=75%7=5,（5+2^2）%9=9

发表于 2018-04-11 11:15:50 回复(2)

提交观点

问题信息

哈希

上传者：城市里的养猫者

难度：

4条回答 6收藏 4519浏览

扫一扫，把题目装进口袋