アルゴリズムと計算量の問題

バケット数 $3$ のチェイン法ハッシュ表が最初は空である。この表に、互いに異なる $4$ 個のキーを挿入する。各キーのハッシュ値は $3$ 個のバケットのどれかに等確率 $\frac{1}{3}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$4$ 個のキーをすべて挿入し終えたとき、キーを $2$ 個以上含むバケットの個数の期待値を求めよ。

バケット数 $20$ のチェイン法ハッシュ表に、互いに異なる $6$ 個のキーを挿入する。各キーのハッシュ値は $20$ 個のバケットのどれかに等確率 $\frac{1}{20}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$6$ 個のキーから選んだ $2$ 個のキーの組（順序は考えない）のうち、$2$ 個が同じバケットに入る組を「衝突する組」と呼ぶ。衝突する組の個数の期待値を求めよ。

番号 $0,1,2,3,4$ の $5$ 個のスロットからなるハッシュ表が最初は空である。この表に、互いに異なる $3$ 個のキーを $1$ 個ずつ順に、次の線形探査法（オープンアドレス法）で挿入する。

• キーのハッシュ値を $h$ とし、スロット $h,h+1,h+2,\dots$ の順に（番号は $5$ を法として考え、スロット $4$ の次はスロット $0$ とする）調べ、最初に見つかった空のスロットにそのキーを入れる。
• $1$ 個のスロットを調べることを探査 $1$ 回と数える。キーを入れた空のスロットを調べることも $1$ 回に数える（たとえば、スロット $h$ が空ならば探査は $1$ 回）。

各キーのハッシュ値は $0,1,2,3,4$ のどれかに等確率 $\frac{1}{5}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$3$ 個のキーを挿入し終えるまでの探査回数の合計の期待値を求めよ。

番号 $0,1,2,3,4,5$ の $6$ 個のセルからなる、線形探査法（オープンアドレス法）のハッシュ表がある。最初はすべてのセルが空である。この表に、互いに異なる $4$ 個のキーを $1$ 個ずつ順に挿入する（削除は行わない）。

キー $x$ を挿入するときは、ハッシュ値 $h(x)\in \{0,1,\dots ,5\}$ から始めて、セル $h(x),h(x)+1,h(x)+2,\dots$（番号は $6$ を法として考え、セル $5$ の次はセル $0$ とする）の順に調べ、最初に見つかった空のセルにキーを格納する。調べたセルの個数（キーを格納した空のセルも $1$ 個と数える）を、その挿入の探査回数とよぶ。

各キーのハッシュ値は $0,1,\dots ,5$ のどれかに等確率 $\frac{1}{6}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$4$ 個のキーの挿入における探査回数の合計の期待値を求めよ。

バケット数 $5$ のチェイン法ハッシュ表が最初は空である。互いに異なるキーを $1$ 個ずつ順に挿入していき、すでに $1$ 個以上のキーが入っているバケットにキーが挿入された時点（最初の衝突が起きた時点）で挿入をやめる。各キーのハッシュ値は $5$ 個のバケットのそれぞれに確率 $\frac{1}{5}$ で、ほかのキーとは独立に定まるものとする。挿入をやめるまでに挿入したキーの個数を $T$ とする（衝突を起こしたキーも数える）。$T$ の期待値 $E[T]$ を求めよ。