小编Nam*_*wal的帖子

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

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