线性探测法查找失败平均查找长度

线性探测法（Linear Probing）是一种简单的哈希表冲突解决策略，当两个或更多的元素被哈希到同一个槽位时，线性探测法会按照一定的顺序在相邻的槽位上查找下一个空闲的槽位，直到找到为止。查找过程就像沿着哈希表的一条线搜索。

查找失败平均查找长度（Average Search Length on Collision，简称ASL）是指在最坏情况下，即哈希表中所有槽位都被填满，每次查找都需要探测多个位置才能找到目标元素的平均探测次数。这个值取决于哈希表的装载因子（装载因子 = 填充元素数 / 总槽位数）和探测步长（通常是1，表示每次探测后只移动一步）。

在满载的情况下，平均查找长度公式通常是这样的：

如果探测步长为1，ASL = (n + 1) / 2，其中n是总槽位数，因为最坏情况下可能会探测到数组的第一个、最后一个和中间的槽位。

随着装载因子增加，ASL的增长速度会变快，因此为了保持性能，哈希表的设计通常会限制其装载因子，以便在接近满载时仍能保持合理的查找效率。

相关问题

线性探测法在计算等概率情况下查找失败计算公式是什么

线性探测法在计算等概率情况下查找失败时的平均查找长度，可以使用以下公式：

(表长 / 2) * (1 / (1 - α)^2)

其中，表长为散列表的长度，α为填装因子，即已经插入的关键字数目与散列表长度的比值。

这个公式的推导比较复杂，但是可以通过假设每个关键字在散列表中出现的位置是等概率的，并且每个关键字的探测长度也是等概率的来进行推导。最终得到的结果是一个二次函数，与填装因子的平方成正比，这就意味着填装因子越大，查找失败时平均查找长度会增加得更快。

设哈希函数H(K)-3Kmod11,哈希地址空间为0~10,对关键字序列(32,13,4 924,38,21,4,12),按下述两种解决冲突的方法构造哈希表，井分别求出等概率下查找成功时和查找失败时的平均查找长度ASI SuC SL-unsSucco 线性探测法；链地址法。

1. 线性探测法

构造哈希表如下：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |
|---|---|---|---|---|---|---|---|---|---|---|
|38 | | |12 |21 |32 |13 | | | | 4 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |

对于查找成功的情况，每个关键字在哈希表中的概率相等，平均查找长度ASL-Succ = (1/7)*(1+1+1+1+1+1+1) = 1。对于查找失败的情况，每个关键字最终都会找到一个空位置，平均查找长度ASL-UnsSucc = (1/4)*(1+2+3+4) = 2.5。其中，4表示哈希表中空位置的个数，1/4表示每个关键字最终落到空位置的概率相等。

2. 链地址法

构造哈希表如下：

| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |
|---|---|---|---|---|---|---|---|---|---|---|
| | | | | | | | | | | |
|13 | | | | | | | |38 | | |
| | | | | 4 | | | | | | |
| | | | | | | |12 |21 | |32 |

对于链地址法，每个关键字在哈希表中的概率相等，平均查找长度ASL-Succ = (1/7)*(1+1+1+1+1+1+1) = 1。对于查找失败的情况，每个关键字最终会落到一个链表中的某个位置上，平均查找长度ASL-UnsSucc = (1/4)*(1+1+1+1) = 1。其中，4表示哈希表中链表的个数，1/4表示每个关键字最终落到某个链表的某个位置上的概率相等。