麻省理工学院讲座错了吗？散列中的开放寻址分析

Question

在下面的麻省理工学院讲座: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但具有不同的概率,如图所示

为什么我会得到不同的答案.它出什么问题了？

Answer 1

该问题要求我们找到需要在哈希表中完成的预期探测数量.

无论如何你必须做一个,所以你有1个开始.然后,n / m你有可能发生碰撞.你的解释是正确的.

如果发生碰撞,则必须进行另一次探测(甚至更多).等等,所以答案就是教授得到的答案:

1 + (n / m)(1 + ((n - 1) / (m - 1))(1 + ...))

您不会乘以获得空槽的概率.如果没有获得空槽,则将未获得空槽的概率乘以必须执行的操作数(1,因为在这种情况下,您必须至少再执行一次探测).

获得一个开放时段的概率与不获得一个时隙的概率相乘是没有意义的,就像你正在做的那样.请记住,我们希望找到我们需要做的预期探测数量.所以你将每一步的操作次数(探针)乘以你没有得到理想的东西(一个空槽)的概率,因为如果这个事件发生了,那么我们将不得不做更多操作(探测),否则我们就完成了.

如果你仔细观察直到最后,你在与之相关的讲座中会很好地解释这一点.