线性探测法平均查找长度
时间：2025-01-08 05:00:47
线性探测法平均查找长度
线性探测法的平均查找长度与冲突次数和探测顺序有关。在等概率情况下，查找成功的平均查找长度可以通过以下公式计算：ASL_success = (Σ(i * pi)) / n，其中i表示查找长度，pi表示查找长度为i的概率，n表示关键字个数。查找不成功的平均查找长度可以通过以下公式计算：ASL_unsuccess = (Σ(i * pi)) / m，其中i表示查找长度，pi表示查找长度为i的概率，m表示冲突次数。
以关键字序列为：（75，33，52，41，12，88，66，27），哈希表长为10，哈希函数为：H（k）＝kmod7，解决冲突用线性探测再散列法为例。查找成功的平均长度为：(4x1+3x2+1x3)/8=13/8。查找不成功的平均长度为：第一次查找不成功：10-4=6，第二次查找不成功：10-3=7，第三次查找不成功：10-1=9，(6x1+7x2+9x3)/8=47/8。
《线性探测法平均查找长度》不代表本网站观点，如有侵权请联系我们删除
精彩推荐