查找成功时的平均查找长度是指找到表中已有表项的平均比较次数，它是找到表中各个已有表项的平均比较次数。而查找不成功的平均查找长度是指在表中找不到待查的表项，但找到插入位置的平均比较次数。它是在表中所有可能散列到的地址上插入新元素时，为找到空位置而进行探查的平均次数。表9-10中列出了使用几种不同的方法解决冲突时Hash表的平均查找长度。从中看到，Hash表的平均查找长度与关键字个数n无关，而与装填因子a有关（装填因子在考题中的用法会在例9-6中介绍）。装填因子是关键字个数和表长度的比值。

说明：对于表9-10，不需要记忆，只需了解各种冲突解决方法所对应的平均查找长度随装填因子a的变化趋势即可。

【例9-6】 用关键字序列{1，9，12，11，25，35，17，29}创建一个Hash表，装填因子a为1/2，试确定表长m，采用除留余数法构造Hash函数，采用链地址法来处理冲突，并计算查找成功与不成功时的平均查找长度ASL₁和ASL₂（只将与关键字的比较计算在内）。

分析：

1）由装填因子a的定义知道，a=n/m，其中n为关键字个数，m为表长，因此可以求出m为16（考研大题中对装填因子的考查主要在这里）。

表9-10 解决冲突的平均查找长度

2）除留余数法的Hash函数构造公式为H（key）=keyModp，其中p为不大于表长的最大素数（如果p大于m，则对p取余数后有可能映射到表之外的地址，因此p必须不大于表长，与素数做取余运算后可以使得Hash地址尽可能地散落均匀，减少冲突，因此p取素数），因表长为16，所以p取13，Hash函数为

H（key）=key Mod 13

3）用2）中构造的Hash函数并用链地址法处理冲突所建立的Hash过程如下：

1 Mod 13=1，1插在地址为1的链表表尾；

9 Mod 13=9，9插在地址为9的链表表尾；

12 Mod 13=12，12插在地址为12的链表表尾；

11 Mod 13=11，11插在地址为11的链表表尾；

25 Mod 13=12，25插在地址为12的链表表尾；

35 Mod 13=9，35插在地址为9的链表表尾；(www.daowen.com)

17 Mod 13=4，17插在地址为4的链表表；

29 Mod 13=3，29插在地址为3的链表表尾。

由此所得Hash表如图9-27所示。

图9-27 例9-6的Hash表

4）对于查找成功与不成功的情况下平均查找长度的求解与例9-5类似，对于ASL₁根据关键字来计算，对于ASL₂根据地址来计算。

① 求ASL₁。

由表9-11可知，ASL₁=（1+1+1+1+2+1+1+2）/8=1.25。

表9-11 关键字比较次数

② 求ASL₂。

由表9-12可知，ASL₂=（0+1+0+1+1+0+0+0+0+2+0+1+2）/13=0.62。

表9-12 地址比较次数