麻省理工学院讲座错了吗？散列中的开放寻址分析
MIT Lecture WRONG? Analysis of open addressing in hashing
在下面的麻省理工学院讲座中：
https://www.youtube.com/watch?v=JZHBa-rLrBA 1:07:00 教授教授计算搜索失败的探测次数
但是我的计算方法和他的不符。
我的回答是：
探测数量=
m=没有。哈希中的插槽数 table
n=没有。元素（键）
解释：
1.The 哈希函数可以以 m-n/m 的概率命中空槽。
2.Or 它可以以 n/m 的概率命中一个全神贯注的键位。
3.Now 在情况2中，我们将不得不再次调用哈希函数，有两次机会：
(i) 我们得到一个没有密钥的槽，概率为 (m-n)/(m-1)。
(ii) 我们以概率 (n-1)/(m-1).
得到一个带有键的槽
4.Now 重复案例 3，但概率不同，如图所示
为什么我得到不同的答案。怎么了？
问题要求我们在散列中找到需要完成的预期探测数量 table。
无论如何你必须做一个，所以你有1个开始。然后，您有 n / m 的机会发生碰撞。你的解释是对的。
如果发生碰撞，则必须再进行一次探测（甚至更多）。依此类推，所以答案就是教授得到的答案：
1 + (n / m)(1 + ((n - 1) / (m - 1))(1 + ...))
您不会乘以获得空位的概率。将 not 得到一个空槽的概率乘以如果你没有得到一个空槽你必须做的操作数（1，因为你必须至少再做一个在这种情况下进行调查）。
将获得空位的概率与未获得空位的概率相乘是没有意义的，就像您所做的那样。请记住，我们想要找到我们需要执行的预期探测次数。所以你将每一步的操作（探测）数量乘以你没有得到你理想中想要得到的东西（一个空槽）的概率，因为如果这个事件发生，那么我们将不得不做更多操作（探测），否则我们就完成了。
如果您仔细观看到最后，这在您链接的讲座中解释得很好。
在下面的麻省理工学院讲座中： https://www.youtube.com/watch?v=JZHBa-rLrBA 1:07:00 教授教授计算搜索失败的探测次数
但是我的计算方法和他的不符。 我的回答是：
探测数量=
m=没有。哈希中的插槽数 table
n=没有。元素（键）
解释：
1.The 哈希函数可以以 m-n/m 的概率命中空槽。
2.Or 它可以以 n/m 的概率命中一个全神贯注的键位。
3.Now 在情况2中，我们将不得不再次调用哈希函数，有两次机会： (i) 我们得到一个没有密钥的槽，概率为 (m-n)/(m-1)。 (ii) 我们以概率 (n-1)/(m-1).
得到一个带有键的槽4.Now 重复案例 3，但概率不同，如图所示
为什么我得到不同的答案。怎么了？
问题要求我们在散列中找到需要完成的预期探测数量 table。
无论如何你必须做一个，所以你有1个开始。然后，您有 n / m 的机会发生碰撞。你的解释是对的。
如果发生碰撞，则必须再进行一次探测（甚至更多）。依此类推，所以答案就是教授得到的答案：
1 + (n / m)(1 + ((n - 1) / (m - 1))(1 + ...))
您不会乘以获得空位的概率。将 not 得到一个空槽的概率乘以如果你没有得到一个空槽你必须做的操作数（1，因为你必须至少再做一个在这种情况下进行调查）。
将获得空位的概率与未获得空位的概率相乘是没有意义的，就像您所做的那样。请记住，我们想要找到我们需要执行的预期探测次数。所以你将每一步的操作（探测）数量乘以你没有得到你理想中想要得到的东西（一个空槽）的概率，因为如果这个事件发生，那么我们将不得不做更多操作（探测），否则我们就完成了。
如果您仔细观看到最后，这在您链接的讲座中解释得很好。