37.2° Blog

1.Sample1

问题

对下面的关键字集（30, 15, 21, 40, 25, 26, 36, 37）若查找表的装填因子为0.8，采用线性再散列方法解决冲突。

1. 设计哈希函数表
2. 画出哈希表
3. 计算查找成功和查找失败的平均查找长度

分析

表长：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，采用开放地址二次探测再散列方法解决冲突

1. 对该关键字构造哈希表
2. 请计算该哈希表再等概率情况下查找成功的平均查找长度

分析

地址	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解决冲突。

1. 画出哈希表
2. 计算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

注意：链地址法解决冲突，在计算失败查找长度时，结点指针为空不算一次查找。