本文以例题形式讲解散列查找中，散列表的构建，以及查找成功的ASL和失败的ASL。重点讲解求解失败的ASL的过程，巨详细
【2010年全国试题41（10分）】将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为： H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。
(1) 请画出所构造的散列表。
(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
| key | 7 | 8 | 30 | 11 | 18 | 9 | 14 |
|---|---|---|---|---|---|---|---|
| H(key) | 0 | 3 | 6 | 5 | 5 | 6 | 0 |
| 实际散列位置 | 0 | 3 | 6 | 5 | 7 | 8 | 1 |
| 查找成功需要探测次数 | 1 | 1 | 1 | 1 | 3 | 3 | 2 |
（1）装填因子
, 所以 n = 10
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 7 | 14 | 8 | 11 | 30 | 18 | 9 |
（2）根据表1-1中 查找查找成功需要探测次数，
接下来重点讲解查找失败的ASL
求解查找失败的ASL需要计算出每个散列位置（即每个模对应的值）查找失败所需要的的次数，本题散列函数模的是7，所以只需要计算模为0,1,2,3,4,5,6的关键字查找失败所需要的次数。查找到空说明查找失败，查找示意图如下
- 查找模为0的关键字，失败时比较的次数为3
- 查找模为1的关键字，失败时比较次数为2
- 查找模为2的关键字，失败时比较次数为1
- 查找模为3的关键字，失败时比较次数为2
- 查找模为4的关键字，失败时比较次数为1
- 查找模为5的关键字，失败时比较次数为5
- 查找模为6的关键字，失败时比较次数为4
将上述过程整理成表格如下
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 7 | 17 | 8 | 11 | 30 | 18 | 9 | ||||
| 各个模查找失败需要比较的次数 | 3 | 2 | 1 | 2 | 1 | 5 |
查找失败的平均比较次数为：