Hash表的平均查找长度ASL计算方法

转载自 http://blog.csdn.net/u013806583/article/details/52643541?locationNum=2&fps=1 CSDN 关小二

ASL指的是 平均查找时间

关键字序列：（7、8、30、11、18、9、14）

散列函数：
H(Key) = (key x 3) MOD 7

装载因子：
0.7

处理冲突：线性探测再散列法

查找成功的ASL计算方法：

因为现在的数据是7个，填充因子是0.7。所以数组大小=7/0.7=10，即写出来的散列表大小为10，下标从0~9。
第一个元素7，带入散列函数，计算得0。
第二个元素8，带入散列函数，计算得3。
第三个元素30，带入散列函数，计算得6。
第四个元素11，带入散列函数，计算得5。
第五个元素18，带入散列函数，计算得5；此时和11冲突，使用线性探测法，得7。
第六个元素9，带入散列函数，计算得6；此时和30冲突，使用线性探测法，得8。
第七个元素14，带入散列函数，计算得0；此时和7冲突，使用线性探测法，得1。
所以散列表：

所以查找成功的计算：
如果查找7，则需要查找1次。
如果查找8，则需要查找1次。
如果查找30，则需要查找1次。
如果查找11，则需要查找1次。
如果查找18，则需要查找3次：第一次查找地址5，第二次查找地址6，第三次查找地址7，查找成功。
如果查找9，则需要查找3次：第一次查找地址6，第二次查找地址7，第三次查找地址8，查找成功。
如果查找地址14，则需要查找2次：第一次查找地址0，第二次查找地址1，查找成功。
所以，ASL=（1+2+1+1+1+3+3）/ 7=12/ 7

查找不成功的ASL计算方法：

鉴于网络上有各种版本，本人认为此种计算方法比较合理。验证实例可以参考2010年的计算机408考研真题的第一道计算大题和答案。

1. 定义什么叫查找不成功
举个例子来说吧。在已知上面散列表的基础上，如果要查找key为4的关键字。根据散列函数可以计算Hash(key)=Hash(4)=5。此时在地址为5的地方取出那个数字，发现key=11，不等于4。这就说明在装填的时候会发生冲突。根据冲突处理方法，会继续检测地址为6的值，发现key=30，依然不等。这个时候到了地址为6，但是依然没有找到。那么就说明根本就没有key=4这个关键字，说明本次查找不成功。注意：为什么到地址6？因为散列函数中有 mod7 ，对应的地址为0~6，即0~6查找失败的查找次数。
再举一个例子。查找key为0的关键字，根据散列函数可以计算Hash(key)=Hash(0)=0。此时在地址为0的地方取出那个数字，发现key=7，不等于0。这就说明在装填的时候会发生冲突。根据冲突处理方法，会继续检测地址为1的值，发现key=14，依然不等。这个时候到了地址为3，发现为空，依然没有找到。所以停止查找，本次查找不成功。因为如果key=0这个关键字存在的话，依照冲突处理函数，就一定能找到它。总不能丢了吧。

2. 根据第一点定义的不成功，依次推下去：
查找地址为0的值所需要的次数为3，
查找地址为1的值所需要的次数为2，
查找地址为2的值所需要的次数为1，
查找地址为3的值所需要的次数为2，
查找地址为4的值所需要的次数为1，
查找地址为5的值所需要的次数为5，
查找地址为6的值所需要的次数为4。
3.计算
查找不成功ASL=（3+2+1+2+1+5+4）/ 7=18/ 7