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

期待値の線形性より、$k$ 番目（$k=1,2,3,4$）の挿入の探査回数の期待値 $E_k$ を求めて足せばよい。

ブロックによる表し方. ある時点で、埋まっているセルが連続して並ぶ極大な部分（環状に考える）をブロックとよぶ。挿入するキーのハッシュ値が長さ $L$ のブロックの先頭から $j$ 番目（$1\le j\le L$）のセルなら、そのブロックの残り $L-j+1$ 個の埋まったセルと、その直後の空のセル $1$ 個を調べるので、探査回数は $L-j+2$ である。ハッシュ値が空のセルなら探査回数は $1$ である。ハッシュ値は $6$ 個のセルに等確率なので、埋まったセルが $3$ 個以下（つねに空のセルがある）のとき
$$E[\text{探査回数}]=1+\frac{1}{6}\sum _{\text{ブロック}}\sum _{j=1}^L(L-j+1)=1+\frac{1}{6}\sum _{\text{ブロック}}\frac{L(L+1)}{2}$$
となる。

$k=1$. 表は空なので $E_1=1$。

$k=2$. ブロックは長さ $1$ が $1$ 個なので $E_2=1+\frac{1}{6}\cdot 1=\frac{7}{6}$。

2 個挿入後の状態. 回転対称性より、$1$ 個目のキーはセル $0$ に入ったとしてよい。$2$ 個目のハッシュ値 $h_2$ によって
- $h_2=0,1$ のとき占有 $\{0,1\}$、$h_2=5$ のとき $\{5,0\}$：隣接（確率 $\frac{3}{6}$）
- $h_2=2,4$：間が $1$ つ空いた $2$ セル（確率 $\frac{2}{6}$）
- $h_2=3$：向かい合う $2$ セル（確率 $\frac{1}{6}$）

$k=3$. 隣接ならブロック $\{2\}$ で $\sum \frac{L(L+1)}{2}=3$、それ以外はブロック $\{1,1\}$ で $2$。よって
$$E_3=1+\frac{1}{6}\left(\frac{1}{2}\cdot 3+\frac{1}{2}\cdot 2\right)=1+\frac{5}{12}=\frac{17}{12}.$$

3 個挿入後の状態. 占有セルを $a,a+1$（隣接）とすると、$h_3=a,a+1,a+2$ のときキーはセル $a+2$ に、$h_3=a-1$ のときセル $a-1$ に入り、長さ $3$ のブロックになる（$4$ 通り）。$h_3=a+3,a+4$ のときはブロック $\{2,1\}$（$2$ 通り）。
占有セルを $a,a+2$ とすると、$h_3=a,a+1$ でブロック $\{3\}$（$2$ 通り）、$h_3=a+2,a+3,a+5$ でブロック $\{2,1\}$（$3$ 通り）、$h_3=a+4$ でブロック $\{1,1,1\}$（$1$ 通り）。
占有セルを $0,3$ とすると、どの $h_3$ でもブロック $\{2,1\}$ になる。
したがって
$$P(\{3\})=\frac{3}{6}\cdot \frac{4}{6}+\frac{2}{6}\cdot \frac{2}{6}=\frac{16}{36},P(\{2,1\})=\frac{3}{6}\cdot \frac{2}{6}+\frac{2}{6}\cdot \frac{3}{6}+\frac{1}{6}\cdot 1=\frac{18}{36},P(\{1,1,1\})=\frac{2}{6}\cdot \frac{1}{6}=\frac{2}{36}.$$
（和は $1$ になる。）

$k=4$. $\sum \frac{L(L+1)}{2}$ はブロック $\{3\}$ で $6$、$\{2,1\}$ で $3+1=4$、$\{1,1,1\}$ で $3$ なので
$$E_4=1+\frac{1}{6}\cdot \frac{16\cdot 6+18\cdot 4+2\cdot 3}{36}=1+\frac{174}{216}=\frac{65}{36}.$$

合計.
$$E_1+E_2+E_3+E_4=\frac{36}{36}+\frac{42}{36}+\frac{51}{36}+\frac{65}{36}=\frac{194}{36}=\frac{97}{18}.$$

線形探査法では、$k$ 個のキーを挿入した直後の占有セルは、空きセルの直後から始まる連続した占有セルの塊（巡回的に数える）に分かれる。長さ $L$ の塊に対し、ハッシュ値がその塊の先頭から $j$ 番目（$j=0,\dots ,L-1$）のセルなら、探査回数は $L-j+1$ である。ハッシュ値が空きセルなら探査回数は $1$ である。したがって次の挿入の探査回数の期待値は
$$1+\frac{1}{6}\sum _{\text{塊}}\frac{L(L+1)}{2}$$
となる。

$k$ 個挿入後の塊の分布を求める。長さ $L_i$ の塊が複数あるとき、その占有パターンになるハッシュ列の数は $\frac{k!}{\prod L_i!}\prod (L_i+1{)}^{L_i-1}$ である。各塊の中は駐車関数の個数 $(L+1{)}^{L-1}$ で数え、キーをどの塊に振り分けるかを多項係数で数える。

$T=\sum L(L+1)/2$ の期待値を $E_k$ とおく。
- $k=0$: $E_0=0$。
- $k=1$: $T=1$ なので $E_1=1$。
- $k=2$: 隣接する 2 セルは 6 通りで、重みは各 $3$、$T=3$。隣接しない 2 セルは 9 通りで、重みは各 $2$、$T=2$。総重み $36$。よって $E_2=(18\cdot 3+18\cdot 2)/36=5/2$。
- $k=3$: 長さ 3 の塊は 6 通りで、重みは各 $16$、$T=6$。長さ 2 と長さ 1 の塊は 12 通りで、重みは各 $9$、$T=4$。長さ 1 の塊が 3 つ並ぶ配置は 2 通りで、重みは各 $6$、$T=3$。総重み $216$。よって $E_3=(576+432+36)/216=29/6$。

$E_0+E_1+E_2+E_3=0+1+\frac{5}{2}+\frac{29}{6}=\frac{25}{3}$。

期待値の合計は
$$4+\frac{1}{6}\cdot \frac{25}{3}=4+\frac{25}{18}=\frac{97}{18}.$$

検算として、各 $k$ の総重みが $6^k$ に一致することを確認した（$k=2$ で $36$、$k=3$ で $216$）。