哈希表查找不成功时的平均查找长度计算和查找成功时的ASL

时间:2024-05-19 20:07:48

哈希表查找不成功时的平均查找长度计算和查找成功时的ASL

例如:  关键字集合 
        { 19, 01, 23, 14, 55, 68, 11, 82, 36 }

设定哈希函数 H(key) = key MOD 11 ( 表长=11 )

哈希表查找不成功时的平均查找长度计算和查找成功时的ASL

 

查找成功次数:    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!