哈希表查找不成功时的平均查找长度计算和查找成功时的ASL
例如: 关键字集合
{ 19, 01, 23, 14, 55, 68, 11, 82, 36 }
设定哈希函数 H(key) = key MOD 11 ( 表长=11 )
查找成功次数: 1 1 2 1 3 6 2 5 1
查找不成功次数:10 9 8 7 6 5 4 3 2 1 1
查找成功时的平均查找长度:ASL=(1+1+2+1+3+6+2+5+1)/9=22/9
查找不成功时的平均查找长度:ASL=(10+9+8+7+6+5+4+3+2+1+1)/11=56/11
说明:
第n个位置不成功时的比较次数为,第n个位置到第1个没有数据位置的距离。
如:第0个位置到第1个没有数据位置(9)的距离为10!