ハッシュテーブル — ハッシュ化の仕組みと衝突解決

ハッシュテーブルは、各キーをハッシュ化して配列の添字に変換することで、キーと値の組を保存します。これにより、保存された要素を1つずつ順番に調べるのではなく、正しい場所の近くへすばやく移動できます。

そのため、ハッシュテーブルの探索・挿入・削除は、平均的には $O(1)$ に近いことがよくあります。ただし条件があります。ハッシュ関数がキーをある程度うまく分散させる必要があり、さらに衝突に対するルールも必要です。

ハッシュテーブルがすること

ハッシュテーブルは、"name" -> "Ada" や 42 -> "blue" のようなキーと値の組を保存します。主な構成要素は2つです。

• スロットまたはバケットの配列
• 各キーをそれらのスロットの1つに対応づけるハッシュ関数

配列に $m$ 個のスロットがあるなら、ハッシュ関数は $0$ から $m-1$ までの添字を返すものと考えられます。

小さな整数の例では、ルールは次のようになります。

$$h(k) = k \bmod 8$$

すると、キー $10$ は $10 \bmod 8 = 2$ なので、スロット $2$ に入ります。

実際のハッシュ関数は、特に文字列や大きなデータ集合に対しては、もっと慎重に設計されます。それでも中心となる考え方は同じです。すばやく添字を計算し、そこに保存されている項目を確認します。

ハッシュ衝突が避けられない理由

衝突とは、異なる2つのキーが同じスロットに対応づけられることです。

これは普通のことです。というのも、テーブルのスロット数は、通常、取りうるキーの総数より少ないからです。たとえば

$$h(k) = k \bmod 8$$

では、キー $10$、$18$、$26$ はすべてスロット $2$ に対応します。つまり、関数が定義どおり正しく動いていても、テーブル側では解決すべき衝突が発生します。

したがって、ハッシュテーブルはすべてのキーに一意のスロットを約束するわけではありません。衝突をうまく処理できるなら、探索範囲をすばやく絞り込めることを約束するのです。

具体例：1つのテーブルで1回の衝突

あるテーブルに $8$ 個のスロットがあり、次を使うとします。

$$h(k) = k \bmod 8$$

キー $10$、$18$、$7$ を挿入します。

まず、$10$ は $10 \bmod 8 = 2$ なので、スロット $2$ に入ります。

次に、$18$ もスロット $2$ にハッシュされるので、衝突が起こります。

そして、$7$ はスロット $7$ に入るので、この挿入では衝突しません。

重要な流れはいつも同じです。

1. キーをハッシュ化する。
2. 指定されたスロットへ行く。
3. そこに別のキーがすでにあれば、衝突処理のルールを適用する。

この流れがはっきりすると、2つの主要な衝突処理戦略も理解しやすくなります。

連鎖法とオープンアドレッシング

連鎖法では各スロットにバケットを持つ

連鎖法では、各スロットには1つの要素だけでなく、小さな要素集合を保存します。

$10$ と $18$ がどちらもスロット $2$ にハッシュされるなら、バケット $2$ には次のように保存できます。

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

キー $18$ を探すとき、テーブルはバケット $2$ に移動し、そのバケット内の要素だけを比較します。

連鎖法は考え方がシンプルで、削除もオープンアドレッシングより簡単なことが多いです。その代わり、バケットが長くなると処理は遅くなります。

オープンアドレッシングは配列の中だけで処理する

オープンアドレッシングでは、各配列スロットには高々1つの要素しか入りません。元のスロットが埋まっていれば、テーブルは決められたルールに従って別のスロットを調べます。

よくあるルールの1つが線形探索です。たとえばスロット $2$ が埋まっていれば、$3$、次に $4$、次に $5$ というように試し、必要なら末尾から先頭へ回り込みます。

この方法では別のバケットリストは不要ですが、埋まったスロットが近くに集まってクラスタを作ることがあります。もう1つ大事なのは、探索と削除でも、挿入時に使ったのと同じ探索ルールを守らなければならないことです。

$O(1)$ と言ってよいのはどんなときか

ハッシュテーブルは、探索・挿入・削除が平均で $O(1)$ だとよく説明されます。ただし、この平均計算量の主張は次の条件に依存します。

• ハッシュ関数がキーをある程度うまく分散させる
• 負荷率が適切に保たれている
• 衝突処理の戦略が正しく実装されている

負荷率とは、次の比のことです。

$$\text{load factor} = \frac{\text{number of stored entries}}{\text{number of slots}}$$

テーブルがいっぱいになりすぎると、衝突はより頻繁に起こり、性能は悪化します。そのため、多くの実装では配列が埋まってくるとサイズを拡張します。

最悪の場合には、あまりに多くのキーが同じ場所付近に集中して、性能が $O(n)$ に近づくこともあります。

ハッシュテーブルでよくある誤解

衝突が起きるとハッシュ関数が失敗したと思う

そうではありません。衝突は想定内です。本当に重要なのは、テーブルがそれを効率よく処理できるかどうかです。

$O(1)$ を無条件だと考える

$O(1)$ は通常、平均的な場合についての説明であり、どんな入力やどんな瞬間にも成り立つ保証ではありません。

ここでのハッシュ化と暗号化を混同する

基本的なデータ構造の文脈でのハッシュ関数の目的は、主に高速な添字付けであって、秘密を守ることではありません。これは別の目的です。

実際のキー比較を忘れる

異なる2つのキーが同じハッシュ値を持つことはあります。正しいバケットや探索位置にたどり着いたあとでも、そのキーが本当に一致するかを確認する必要があります。

ハッシュテーブルが使われる場面

ハッシュテーブルは、キーにもとづく高速な探索が重要な場面で使われます。代表例としては、辞書、シンボルテーブル、キャッシュ、インデックス付け、データ中の出現回数の集計などがあります。

キーによる正確な探索が、要素をソート順に保つことより重要なときに特に向いています。順序付きの走査、範囲検索、近い値の探索が必要なら、別のデータ構造のほうが適しているかもしれません。

似た衝突例を自分で試してみる

$8$ 個のスロットを持つ小さな配列を用意し、$h(k)=k \bmod 8$ を使ってみましょう。$3$、$11$、$19$、$27$ のようなキーを挿入し、連鎖法で1回、線形探索で1回、衝突を解決してみてください。

この1つの練習だけで、中心となる考え方がすぐに具体的になります。衝突は避けられず、どの衝突処理ルールを使うかでテーブルの振る舞いが変わるのです。次の一歩としては、テーブルサイズを変えた自分なりの例も試し、衝突の起こり方がどう変わるかを見てみるとよいでしょう。