将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为H(key)=(key×3) mod 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
1)请画出所构造的散列表。
2)分别计算等概率情况下查找成功和查找不成功的平均查找长度。
表B-3
key
7
8
30
11
18
9
14
H(key)
0
3
6
5
表B-4
地址
1
2
4
关键字
表B-5
次数
故ASL成功=查找次数/元素个数=(1+2+1+1+1+3+3)/7=12/7。
这里要特别防止惯性思维。查找失败时,是根据查找失败位置计算平均次数,根据散列函数mod 7,初始只可能在0~6的位置。等概率情况下,查找0~6位置查找失败的查找次数见表B-6。
表B-6
故ASL不成功=查找次数/散列后的地址个数=(3+2+1+2+1+5+4)/7=18/7。
这道题不是用的再散列方法吗
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
表B-3
key
7
8
30
11
18
9
14
H(key)
0
3
6
5
5
6
0
表B-4
地址
0
1
2
3
4
5
6
7
8
9
关键字
7
14
8
11
30
18
9
表B-5
key
7
8
30
11
18
9
14
次数
1
1
1
1
3
3
2
故ASL成功=查找次数/元素个数=(1+2+1+1+1+3+3)/7=12/7。
这里要特别防止惯性思维。查找失败时,是根据查找失败位置计算平均次数,根据散列函数mod 7,初始只可能在0~6的位置。等概率情况下,查找0~6位置查找失败的查找次数见表B-6。
表B-6
H(key)
0
1
2
3
4
5
6
次数
3
2
1
2
1
5
4
故ASL不成功=查找次数/散列后的地址个数=(3+2+1+2+1+5+4)/7=18/7。