给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79)哈希函数为：H(key)=key % 13, 哈希表长为m=15，设每个记录的查找概率相等。
给定一组查找关键字(19,14,23,1,65,20,84,27,55,11,10,79)
哈希函数为：H(key)=key % 13, 哈希表长为m=15，设每个记录的查找概率相等。
-
请画出按照线性探测再散列处理冲突得到的哈希表（给出求解过程），并计算查找成功和查找失败时的平均查找长度各是多少。
-
请画出按照链地址法处理冲突得到的哈希表，并计算查找成功和查找失败时的平均查找长度各是多少。
关键字除以13取余后分别得到:6,1,10,1,0,7,6,1,3,11,10,1
线性探测:
成功时的平均查找次数：（1+1+2+3+2+4+1+1+3+1+1+3）/12 = 23/12
失败时的平均查找次数：（10+9+8+7+6+5+4+3+2+1+4+3+2）/ 13 = 64/13
链地址法:
0—>65
1—>14,1,27,79
2
3—>55
4
5
6—>19, 84
7—>20
8
9
10—>23,10
11—>11
总查找次数: 1+1+2+3+4+1+1+2+1+1+2+1=20
成功时的平均查找次数：20/12=5/3
失败时的平均查找次数：（4+1+2+1+2+1）/ 11 = 1
发布评论