关于Weiss《C++数据结构与算法分析》线性探测哈希的两个技术疑问

问题1：第一段加粗表述的具体含义？ #

• 随机冲突解决策略的合理性：随机冲突解决策略指冲突发生时，随机选择未占用位置存放元素，这种策略下每次探测的位置和之前完全无关，天然满足“探测独立”“表规模极大”的假设。
• 负载因子λ的影响：当λ远小于1时，哈希表空位充足，线性探测时连续遇到占用位置的概率极低，实际探测过程和“独立探测”的偏差极小，因此可以用随机策略的假设来近似分析。但如果λ接近1，哈希表接近饱和，线性探测会出现严重的“聚集”现象（连续一片的占用位置），此时每次探测的结果完全依赖前一次的探测，“独立探测”的假设不再成立，推导结果也会严重偏离实际。

问题2：如何推导得出1/(1−λ)这一结论？ #

这个推导基于几何分布的概率模型：

1. 定义每次探测为一次独立试验，“成功”事件为找到空单元格。已知空单元格占比为1−λ，因此每次探测成功的概率为 ( p = 1 - \lambda )。
2. 不成功搜索的期望探测次数，本质是首次成功（找到空位）所需的期望试验次数。根据几何分布的性质，首次成功的期望试验次数为 ( \frac{1}{p} )。
3. 将 ( p = 1 - \lambda ) 代入，直接得到期望探测次数为 ( \frac{1}{1 - \lambda} )。
4. 注意：该推导严格依赖“探测独立”的假设，因此仅当λ不接近1时，这个结果能反映线性探测的实际情况；若λ接近1，聚集效应会使实际期望次数远高于该值。

内容的提问来源于stack exchange，提问作者Aaron Swartz