哈希中的线性探测

Question

在线性探测散列中，如果聚类不是问题，我们将假设一个非常大的表，并且每个探测都独立于前面的探测。这些假设被随机碰撞分解策略所满足。首先，在不成功的搜索中，我们得到了期望的探测数量。在我们找到一个空的单元格之前，这只是期望的探测数量。由于空单元格的分数是(1 - (N/M))，其中N是元素数，M是散列表大小。我们期望探测的细胞数为1/(1 - (N/M))。成功搜索的探测数等于插入特定元素时所需的探测数。

我的问题是，在上述文本中，我们如何得到我们期望的单元格数为1/(1-(N/M))。

谢谢!

Answer 1

探测的工作原理大致如下:你有成功的概率p，你一直在努力直到你成功。这意味着您正在处理几何概率分布，因此在您成功之前所期望的尝试次数是1/p。

在这种情况下，p=1-(N/M)，所以预期的尝试次数是1/(1-(N/M))。