data-structures - 線形プローブを使用してハッシュに3つのキーを連続して挿入すると、4番目の要素の確率は3つのプローブが必要になります

Question

線形プローブを使用してハッシュに3つのキーを続けて挿入すると、4番目の要素に3つのプローブが必要になる確率はどれくらいですか？1番目の要素を挿入した後、2番目の要素に挿入できる場所が3つあるため、12 / n ^ 3になります（ 3 / nである1番目の要素の左側、1番目の要素、1番目の要素の右側）。3番目の要素は4つの場所を挿入して連続させるため、4 / nであり、最後の4番目の要素は1番目の要素のハッシュに挿入する必要があるため1/nです。確率は3/n * 4 / n * 1 / n = 12 / n ^ 3ですか、それとも12 / n ^ 2ですか？

Answer 1

最初の2つの要素が隣接していないが、3番目の要素がギャップを埋める（ペアの）ケースを見逃したと思います。数学は似ていますが、3 / n * 4 / n + 2 / n * 2 / n = 16 / n ^ 2で3つを隣接させ、最初の1つをヒットして16 / n^3を得る確率は1/nです。