哈希表平均查找长度

题目:关键字序列为:{38,25,74,63,52,48},哈希函数为H(k)=k%7,哈希表的长度为7,用线性探测和链地址法处理冲突,分别计算等概率情况下查找成功的平均查找长度。

注:没给哈希表长度,给出装填因子时,可求哈希表长度,
可根据此公式装填因子=元素个数/表长推:表长=元素个数/装填因子。

线性探测法

哈希表平均查找长度

由上构造的哈希表如下:
哈希表平均查找长度

等概率下查找成功的平均查找长度为:
ASL=(1+3+1+1+2+4)/6=2

链地址法
哈希表平均查找长度

由上构造的哈希表如下:
哈希表平均查找长度

等概率下查找成功的平均查找长度为:
ASL=(1*4+2*2)/6=1.3