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

时间:2022-08-08 03:18:29

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