哈希表查找不成功的平均查找长度

### 哈希表查找失败时的平均查找长度

在哈希表中，当查找一个不存在的关键字时，所经历的比较次数称为查找失败的比较次数。对于不同的哈希表实现方式，这一数值会有所不同。

#### 对于线性探测法
在线性探测法中，如果发生碰撞，则按照一定的顺序（通常是逐位递增）寻找下一个可用位置。因此，在最坏情况下，可能需要遍历整个表来确认某个键确实不在其中。假设哈希表大小为 \( m \)，装载因子 \( \alpha=n/m \) （\( n \) 是已存入的数据项数目），则查找失败的平均查找长度可以表示为：

\[ ASL_{fail}=\frac{1}{m}\sum _{{i=0}}^{{m-1}}{\left(\text {number of probes when searching a non-existent key with hash value i}}\right)[^1]

具体来说，随着负载因子增加，即表越满，查找失败所需的探针数量也会相应增多。当接近完全填充状态 (\( \alpha \to 1 \)) ，每次不成功的查找几乎都要访问所有的槽位[^2]。

#### 链地址法下的情况
而在链地址法下，即使存在大量冲突也不会影响到其他节点的位置分布。此时，只要沿着对应索引处形成的单向链接列表逐一检验直至到达链尾即可断定目标元素缺失。由于每条链独立运作互不影响，故而其期望值主要取决于该桶内实际拥有的结点个数而非全局参数。设某特定散列码对应的子集规模为 k，则有:

\[ E[\text {{probes on failed search}}]=k+1 \]

这里加一是因为还需要额外的一次判断以确定链结束且未找到匹配项[^3]。

综上所述，不同类型的哈希表设计决定了具体的查找性能特征，特别是针对那些未能命中记录的情形。理解这些差异有助于优化应用中的数据检索效率并合理规划资源分配策略。

def calculate_average_search_length(m, alpha):
    """计算基于线性探测法的哈希表查找失败时的平均查找长度"""
    sum_probes = 0
    
    for i in range(m):
        # 这里简化处理，实际上应考虑更复杂的逻辑
        num_of_probes = int((1 / (1 - alpha)))
        sum_probes += num_of_probes
        
    avg_search_length_fail = sum_probes / m
    return avg_search_length_fail