哈希查找的平均查找长度pta

### 哈希查找的平均查找长度分析

哈希查找是一种高效的查找方法，其性能取决于多个因素。当讨论哈希查找的平均查找长度时，主要考虑的是冲突处理机制以及负载因子的影响。

#### 负载因子与冲突率的关系
负载因子 \( \alpha = \frac{n}{m} \)，其中 \( n \) 是存储在哈希表中的元素数量，\( m \) 是哈希表槽数量。随着负载因子增加，发生冲突的概率也会增大，这会直接影响到查找效率[^1]。

#### 成功查找的平均比较次数
对于成功的查找操作，在理想情况下（即没有冲突），每次查找只需要一次访问即可完成。然而实际上由于存在碰撞，因此需要额外计算探查序列长度。如果采用开放地址法，则成功查找的期望时间复杂度可以表示为：

\[ E_{\text{success}}(\alpha)=\begin{cases}
\sum^{i=0}_{k}\left(1-\alpha+\alpha k\right)\cdot p(k), & \text{(线性探测)} \\
\ln{\frac{1}{1-\alpha}},& \text{(二次探测/双重散列)}
\end{cases}
\]

这里 \(p(k)\) 表示第 \(k\) 次尝试找到目标键值的概率分布函数[^3]。

#### 失败查找的平均比较次数
对于未存在于哈希表内的关键字进行查找称为失败查找。此时无论哪种方式实现，都需要遍历整个可能的位置直到确认不存在该记录为止。理论上讲，最坏情况下的查找成本接近于满表扫描的成本。但在实际应用中，通常假设均匀随机分布模型下估算失败查找所需的时间开销:

\[E_{\text{failure}}=\frac{1}{1-\alpha}\]

此表达式适用于大多数常见的解决冲突的方法，比如链地址法、线性探测等[^2]。

def expected_search_cost(alpha, method='linear'):
    """
    计算给定负载因子α条件下不同策略的成功和不成功查找预期代价
    
    参数:
        alpha (float): 负载因子 α=n/m
        method (str): 解决冲突的方式 ('chain', 'linear')
        
    返回:
        tuple(float,float): 分别对应成功查找和失败查找的预计花费
    """
    import math
    
    if method == "chain":
        success = 1 + alpha / 2
        failure = 1 + alpha
        
    elif method == "quadratic" or method == "double_hashing":
        success = math.log(1/(1-alpha))
        failure = 1 / (1 - alpha)

    else:   # 默认为 linear probing
        from scipy.stats import geom
        pmf = lambda k : ((1 - alpha)**k)*alpha
        success = sum([(1-(alpha+(alpha*k)) * geom.pmf(k+1, alpha)) for k in range(int(1//alpha)+1)])
        failure = 1 / (1 - alpha)
    
    return round(success,4),round(failure,4)


print(expected_search_cost(.7,'linear'))