ハッシュテーブル
は、情報を保存・検索するためのデータ構造の一つです。コンピュータサイエンスにおいて、情報を整理・保持する仕組みは全般に「データ構造体と」呼ばれ、ハッシュテーブルはその代表例です。ハッシュテーブルは、キー（名前）と呼ばれる識別子と、それに対応する値（データ）を対応付けて保存します。たとえばキーが人の名前であれば、値はその人の電話番号や住所などになります（この値を値と呼びます）。ハッシュテーブルでは、キーから直接保存場所を決めるために、ハッシュ関数を使います。

仕組み（ざっくり説明）

内部的にはデータは配列と同じような「箱（バケツ）」の列に格納されます。各箱には 0 から始まるインデックス番号が振られています。キーをハッシュ関数をに入力すると、関数が数値（インデックス）を返し、その番号の箱に値を格納します。こうすることで、キーが分かればどの箱に入っているかを素早く特定できます。

衝突（コリジョン）とその解決方法

全てのキーが異なる箱に必ず入るわけではなく、異なるキーが同じインデックスを返すことがあります。これを「衝突（コリジョン）」と呼びます。衝突を処理する代表的な方法は主に二つです。

  • チェイニング（連鎖法）：各箱にリスト（または別の容器）を用意し、同じインデックスに来た複数の要素をそのリストに追加します。取り出すときはそのリストを走査してキーを探します。
  • オープンアドレッシング：衝突が起きたら別の空いている箱を探索して格納します。探索方法には線形探索（linear probing）、二次探索（quadratic probing）、二重ハッシュ（double hashing）などがあります。

性能（時間計算量）

  • 平均的な検索・挿入・削除：O(1)（定数時間）— 非常に高速です。
  • 最悪ケース：O(n)— 例えばすべてのキーが同じインデックスに入って長いリストを走査する場合など。

実際には良いハッシュ関数と適切なサイズ管理を行えば、ほとんどの場合で平均O(1)の性能が得られます。

実装上の重要点

  • ハッシュ関数の質：キーを均等に分散させることが重要です。偏りがあると衝突が増え、性能が低下します。
  • ロードファクタ（負荷率）：要素数 ÷ バケット数。ある閾値（例えば0.7）を超えると、配列を拡大して全要素を再配置（リハッシュ）することが一般的です。これにより平均性能を保ちます。
  • メモリと速度のトレードオフ：バケット数を多くすれば衝突は減るがメモリを多く使います。用途に応じてバランスを取る必要があります。
  • セキュリティ上の注意：悪意のある入力で衝突を多発させ、Hash DoS（サービス拒否攻撃）を引き起こすことがあります。対策としてハッシュにランダムなシードを用いるライブラリや、衝突が多いときに別アルゴリズムに切り替える実装があります。

用途・利点・欠点

ハッシュテーブルは、キーから値への高速なルックアップが必要な場面で多用されます。たとえば連想配列（マップ/辞書）、データベースのインデックス、キャッシュ、セットなどでよく使われます。

  • 利点：検索・挿入・削除が平均して非常に速い（O(1)）。実装が比較的単純で多くの言語で標準ライブラリとして提供されています。
  • 欠点：キーに順序性を持たせたい場合（例えばソート順で反復したい場合）は不向き。最悪ケースの性能が良くない（O(n)）点、メモリ使用量が増える点、ハッシュ関数設計や衝突処理の実装が必要な点に注意が必要です。

具体例（イメージ）

例えばキーが「佐藤」でハッシュ関数が返す値が7なら、配列の7番目の箱に「佐藤 → 090-xxxx-xxxx」と格納します。検索時に同じハッシュ関数で「佐藤」を計算すれば直接7番目を参照して値を取り出します（衝突がある場合はチェイニングや探査を行います）。

まとめ（使い分けの目安）

  • ランダムアクセス的にキーで高速検索したい → ハッシュテーブルが適している。
  • データを常にソートされた順で扱いたい、もしくは範囲検索が多い → バランス木（例：赤黒木）など別のデータ構造を検討する。
  • セキュリティが重要で外部入力をそのままキーにする場合は、ハッシュの衝突攻撃対策を講じる。

ハッシュテーブルは、とても実用的で幅広く使われる基本的なデータ構造です。仕組みとトレードオフを理解すれば、多くの場面で有効に活用できます。