1.Sample1
问题
对下面的关键字集(30, 15, 21, 40, 25, 26, 36, 37)若查找表的装填因子为0.8,采用线性再散列方法解决冲突。
- 设计哈希函数表
- 画出哈希表
- 计算查找成功和查找失败的平均查找长度
分析
表长:
tableLength = 8 / 0.8 = 10
哈希函数:
Hash(key) = key % 7
哈希表:
地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
key | 21 | 15 | 30 | 36 | 25 | 40 | 26 | 37 | ||
成功次数 | 1 | 1 | 1 | 3 | 1 | 1 | 2 | 6 | ||
失败次数 | 9 | 8 | 7 | 6 | 5 | 4 | 3 |
ASL:
key是无穷无尽的,但是key映射到
0~p-1
的单元,如果将每个0~p-1
的单元失败的情况穷举一下,那么就能获得所有失败情况。ASLsuc = (1+1+1+3+1+1+2+6)/8 = 2
ASLfail = (9+8+7+6+5+4+3)/7 = 6
2.Sample2
问题
已知一组关键字序列为{32, 18, 138, 50, 81, 98, 55, 90, 96, 271, 140},采用哈希函数 H(key) = key MOD 13,表长m=15,采用开放地址二次探测再散列方法解决冲突
- 对该关键字构造哈希表
- 请计算该哈希表再等概率情况下查找成功的平均查找长度
分析
地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
key | 81 | 55 | 18 | 32 | 98 | 138 | 96 | 271 | 50 | 90 | 140 | ||||
成功次数 | 1 | 2 | 1 | 1 | 1 | 1 | 4 | 3 | 1 | 1 | 4 | ||||
失败次数 | 1 | 1 | 1 | 3 | 5 | 5 | 5 | 6 | 6 | 4 | 7 | 4 | 2 |
ASLsuc = (1+2+1+1+1+1+4+3+1+1+4)/11 = 20/11
ASLfail = (1+1+1+3+5+5+5+6+6+4+7+4+2)/13 = 4
查找成功计算:
32 % 13 = 6
18 % 13 = 5
138 % 13 = 8
50 % 13 = 11
81 % 13 = 3
98 % 13 = 7
55 % 13 = 3 → 3+1 = 4
90 % 13 = 12
96 % 13 = 5 → 5+1=6 → 5-1=4 → 5+4=9
271 % 13 = 11 → 11+1=12 → 11-1 = 10
140 % 13 = 10 → 10+1=11 → 10-1=9 → 10+4=14
查找失败计算:
3 → 3+1=4 → 3-1=2
4 → 4+1=5 → 4-1=3 → 4+4=8 → 4-4=0
5 → 5+1=6 → 5-1=4 → 5+4=9 → 5-4=1
6 → 6+1=7 → 6-1=5 → 6+4=10 → 6-4=2
7 → 7+1=8 → 7-1=6 → 7+4=11 → 7-4=3 → (7+9)%15=1
8 → 8+1=9 → 8-1=7 → 8+4=12 → 8-4=4 → (8+9)%15=2
9 → 9+1=10 → 9-1=8 → 9+4=13
10 → 10+1=11 → 10-1=9 → 10+4=14 → 10-4=6 → (10+9)%15=4 → (10-9)%15=1
11 → 11+1=12 → 11-1=10 → (11+4)%15=0
12 → 12+1=13
3.Sample3
问题
对{32,18,138,50,81},填装因子是0.5,采用在哈希函数
Hi=(Hi-1+RV(key))%7
解决冲突。- 画出哈希表
- 计算ASLsuc
分析
表长:
tableLength = 5/0.5=10
哈希函数:
Hash(key)=key%7
地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
key | 32 | |||||||||
成功次数 | ||||||||||
失败次数 |
查找成功:
32%7=4
18%7=4
4.Sample4
问题
选取哈希函数
H(key)=key%7
,用链地址法解决冲突,使用0~6的散列地址空间对关键字序列{31,17,27,19,11,13,91,61,41}构造哈希表,并计算概率下查找成功的平均查找长度。table Length=7分析

ASLsuc = (1+1+1+2+1+1+2+1+2+3)/10 = 1.5
ASLfail = (1+0+1+2+1+2+3)/7=10/6
注意:链地址法解决冲突,在计算失败查找长度时,结点指针为空不算一次查找。