用线性探针将3个键插入哈希中，第4个元素出现的概率是多少?

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得到相邻的3，然后1/n的概率击中第一个得到16/n^3