data-structures - 使用线性探针将行中的3个键插入哈希，第4个元素的概率是多少需要3个探针

Question

使用线性探针将行中的 3 个键插入哈希中，第 4 个元素需要 3 个探针的概率是多少？，我得到 12/n^3，因为在插入第一个元素后，您可以为第二个元素插入 3 个位置（第一个元素的左边，第一个元素，第一个元素的右边），即 3/n。第三个元素你有 4 个地方可以插入以使它们连续，所以 4/n 和最后的第 4 个元素必须插入到第一个元素的散列中，所以 1/n。概率是 3/n *4/n *1/n =12/n^3 还是只是 12/n^2 ？

Answer 1

我认为您错过了前两个元素不相邻但第三个元素填补空白的（一对）案例。数学是相似的，虽然 3/n*4/n + 2/n*2/n = 16/n^2 得到三个相邻的，然后 1/n 的几率击中第一个得到 16/n^3。