ハッシュテーブル可視化ツール

テーブルの使用率は75%で、検索1回あたりの探査回数は平均3.5回である。線形探査の標準公式では、その負荷率において2.5回と予測される。どちらが誤っているのかを突き止めよ。

1. どちらも誤ってはおらず、その理由はキーにある。6つのキーそれぞれをテーブル固有の関数でハッシュ化すると、いずれも3を返す。これらは公差8の等差数列であり、テーブルにはちょうど8つのスロットが存在する。

   $$h(k)=k \bmod 8:\quad 3,11,19,27,35,43\ \longmapsto\ 3,3,3,3,3,3$$

2. 負荷率は確かに0.75のままである（8つのスロットに6つのキー）。それは単に、キーがどこに入ったかについて何も語っていないだけである。

   $$\alpha=\frac{n}{m}=\frac{6}{8}=0.75$$

3. したがって、探査列は考えられうる最悪のものとなる。1つ目のキーは空きスロットに入り、2つ目のキーは1スロット進み、3つ目のキーは2スロット進む。6つのキー全体で 1 + 2 + … + 6 = 21 回の探査を要し、そのうち 15 回がパネルの報告する余分な作業である。

   $$\text{probes}=1,2,3,4,5,6\quad\Longrightarrow\quad \sum=21,\quad \text{extra}=21-6=15$$

4. これは検索1回あたり平均 3.5 回の探査となる。

   $$\bar{p}=\frac{21}{6}=3.5$$

5. 教科書の見積もりはキーが一様に分散することを前提としており、α = 0.75 では 2.5 となる。2.5 と 3.5 の差は誤差ではない。テーブルサイズと共通の因数を持つハッシュ関数を、同じく共通の因数を持つキー群に適用したことで生じるコストである。

   $$\tfrac12\left(1+\frac{1}{1-\alpha}\right)=\tfrac12\left(1+4\right)=2.5\ \ \text{(random keys)}\ \ <\ \ 3.5$$

パネルは 8 個のスロットに 6 個のキーを入れ、占有率 0.75、探索回数 3.5 と報告します。この占有率での成功探索はおよそ 2.5 回——余裕があります。ではなぜ、現実のハッシュマップはどれも満杯にせず、ちょうど 0.75 でリサイズするのでしょうか。

1. パネルの状態から始めます。4 分の 3 が埋まっていて、メモリの使い方としては妥当に聞こえます。

   $$\alpha=\frac{n}{m}=\frac{6}{8}=0.75$$

2. 成功探索は安心できる数です。目当てのキーが見つかるまでに、平均しておよそ 2.5 個のスロットを調べるだけ。

   $$S(\alpha)\approx\frac12\left(1+\frac{1}{1-\alpha}\right)=\frac12(1+4)=2.5$$

3. 失敗探索は別の式に従い、その違いに答えのすべてがあります。失敗は「無い」ことを示すために、埋まったスロットの連なりを端まで歩き切らねばならない——だから空き具合の項が線形ではなく 2 乗で効きます。

   $$U(\alpha)\approx\frac12\left(1+\frac{1}{(1-\alpha)^{2}}\right)=\frac12(1+16)=8.5$$

4. 占有率を少し上げて、2 乗が何をするか読み取ってください。0.75 から 0.90 は、埋まり具合の変化としては控えめに聞こえます。

   $$U(0.90)=\frac12(1+100)=50.5,\qquad U(0.95)=\frac12(1+400)=200.5$$

5. 同じ一歩に対する 2 つの増え方を比べます。ヒットの費用は 2 倍を少し超える程度、ミスの費用は 6 倍近くになります。

   $$\alpha:0.75\to0.90\quad\Longrightarrow\quad S:2.5\to5.5\ (\times2.2),\qquad U:8.5\to50.5\ (\times5.9)$$

6. だからテーブルは代わりに倍化します。全キーを再ハッシュするので m 回の操作がかかりますが、次にそれが起きるまでに m 回の挿入を買えます。

   $$m\to2m\quad\Longrightarrow\quad \alpha\to\tfrac{\alpha}{2},\qquad \frac{m}{m}=O(1)$$