目录
给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79)
线性探测法例题
链地址法例题
网上一些博客错误的指正
给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79)
哈希函数为:H(key)=key % 13, 哈希表长为m=15,设每个记录的查找概率相等。
1. 请画出按照线性探测再散列处理冲突得到的哈希表(给出求解过程),并计算查找成功和查找失败时的平均查找长度各是多少。
2. 请画出按照链地址法处理冲突得到的哈希表,并计算查找成功和查找失败时的平均查找长度各是多少。
ps:老师改题啦,原来和下面的那题是一样的,题目任你改做不出算我输,哈哈哈(低调低调)
由第一个H(19) = 19MOD 13 = 6以此类推
19 | 14 | 23 | 1 | 68 | 20 | 84 | 27 | 55 | 11 | 10 | 79 |
6 | 1 | 10 | 1 | 0 | 7 | 6 | 1 | 3 | 11 | 10 | 1 |
可以得到散列表为
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
65 | 14 | 1 | 21 | 55 | 79 | 19 | 78 | 84 | 23 | 11 | 10 |
key | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
count | 1 | 1 | 2 | 3 | 2 | 5 | 1 | 1 | 3 | 1 | 1 | 3 |
查找成功的平均长度:(1+1+2+3+2+5+1+1+3+1+1+3)÷12 = 24/12 = 2;
key | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
count | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 4 | 3 | 2 |
查找失败得平均长度:(10+9+8+7+6+5+4+3+2+1+4+3+2)÷13 = 64/13;
(2)
链地址法:
查找成功的平均长度:(1×7+2×3+3×1+4×1)÷12 = 20/12=5/3;
查找失败的平均长度:(2+5+1+2+1+1+3+2+1+1+3+2+1)÷13 = 25/13;
请回答采用线性探测再散列和链地址法处理冲突构建的哈希表中,查找失败时的平均查找长度如何计算?
例:已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)
哈希函数为:H(key)=key MOD 13, 哈希表长为m=15,
设每个记录的查找概率相等,采用以上两种方法处理冲突,查找失败时的平均查找长度各是多少
这题可真得是出到点子上去啦,看视频,找资料,网上有得解释真的是有点误人子弟,随后加上问了老师一番才有了确定的结果
没错我们主要得难点还是查找失败得分母到底是什么呢,还有一个网上解释错得,但广为流传得,
但是还是全部体系得去写吧毕竟也许以后就忘了
线性探测
(1)
有第一个H(19) = 19MOD 13 = 6,后面得以此类推,
19 | 14 | 23 | 1 | 68 | 20 | 84 | 27 | 55 | 11 | 10 | 79 |
6 | 1 | 10 | 1 | 3 | 7 | 6 | 1 | 3 | 11 | 10 | 1 |
可以得到散列表为
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
14 | 1 | 68 | 27 | 55 | 19 | 20 | 84 | 79 | 23 | 11 | 10 |
key | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
count | 1 | 2 | 1 | 4 | 3 | 1 | 1 | 3 | 9 | 1 | 1 | 3 |
查找成功的平均长度:(1+2+1+4+3+1+1+3+9+1+1+3)÷12 = 30/12 = 2.5;
key | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
count | 1 | 13 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 |
查找失败得平均长度:(1+13+12+11+10+9+8+7+6+5+4+3+2)÷13 = 7
ps:查找失败得平均长度分母是MOD后面得数也就是13
(2)
链地址法:
查找成功的平均长度:(1×6+2×4+3×1+4×1)÷12 = 21/12;
查找失败的平均长度:(1+5+1+3+1+1+3+2+1+1+3+2+1)÷13 = 25/13;
ps:它的分母也是mod后面的数13 ,并且查的范围是0-12;
线性探测法例题
将关键字序列(14、15、9、4、16、2、21)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组。散列函数为: H(key) = (key x 3) MOD 7,处理冲突采用线性探测再散列法,要求装填因子为0.7。
(1) 请画出所构造的散列表;
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
当时由于老师让及时做出来,就有点匆忙,能懂哪个意思就行
链地址法例题
题目
将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为:H(key)=key mod 11,处理冲突采用链地址法,求在等概率下查找成功和查找不成功的平均查找长度
1mod11=1,所以数据1是属于地址1
13mod11=2,所以数据13是属于地址2
12mod11=1,所以数据12也是属于地址1(这个数据是数据1指针的另一个新数据)
34mod11=1,所以数据34是属于地址1(这个数据是数据12指针的另一个新数据)
38mod11=5,所以数据38是属于地址5
33mod11=0,所以数据33是属于地址0
27mod11=5,所以数据27是属于地址5,(这个数据是数据38指针的另一个新数据)
22mod11=0,所以数据22是属于地址0,(这个数据是数据33指针的另一个新数据)
链地址法处理冲突构造所得的哈希表如下:
查找成功时: ASL=(3×1+2×3+1×4)/8=13/8,
查找不成功时:ASL=(3+4+2+1+1+3+1+1+1+1+1)/11=19/11;或者 ASL=(7×1+1×2+2×3+1×4 )/11=19/11,
网上一些博客错误的指正
这个里面的一个解释是错的
这个地址就是9
这个也是有错的
全部少加一个1
更多推荐
数据结构:哈希表平均长度,给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79) 哈希函数为:H(key)=key % 13
发布评论