Hash表的“查找成功的ASL”和“查找不成功的ASL”
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。 所以散列表：| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| key | 7 | 14 | 8 | 11 | 30 | 18 | 9 |
所以查找成功的计算：
如果查找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 分类: