用線性探針將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。