在以下 MIT 讲座中： https ://www.youtube.com/watch?v= JZHBa-rLrBA 在 1:07:00，教授教计算不成功搜索中的探针数。
但我的计算方法与他不符。我的回答是：
探针数=
m=没有。哈希表中的槽数
n = 没有。元素（键）
解释：
1.哈希函数可以命中一个空槽，概率为mn/m。
2.或者它可以以 n/m 的概率命中一个被占用的键槽。
3.现在在情况 2 中，我们将不得不再次调用哈希函数，有两种机会： (i) 我们得到一个没有密钥的槽，概率为 (mn)/(m-1)。(ii) 我们得到一个带有概率 (n-1)/(m-1) 的密钥槽。
4.现在重复案例 3，但概率不同，如图所示
为什么我得到不同的答案。它出什么问题了？
该问题要求我们在哈希表中找到需要完成的预期探测次数。
无论如何你必须做一个，所以你有一个开始。然后，n / m您有可能发生碰撞。你的解释是对的。
如果发生碰撞，则必须进行另一次探测（甚至更多）。依此类推，所以答案是教授得到的答案：
1 + (n / m)(1 + ((n - 1) / (m - 1))(1 + ...))
你不会乘以你得到一个空槽的概率。如果你没有得到一个空槽，你将没有得到一个空槽的概率乘以你必须执行的操作数（1，因为在这种情况下你必须至少再做一次探测）。
像您正在做的那样，将获得空位的概率乘以没有获得空位的概率是没有意义的。请记住，我们想要找到我们需要进行的预期探测次数。因此，您将每一步的操作（探测）数量乘以您无法获得理想结果（空槽）的概率，因为如果发生此事件，那么我们将不得不做更多操作（探针），否则我们就完成了。
如果您仔细观看直到最后，这在您链接到的讲座中得到了很好的解释。