ハッシュテーブルとは？

詳細解説

ハッシュテーブル（Hash Table）は、キー（key）をハッシュ関数（hash function）でインデックス（バケット番号）に変換し、対応する位置にデータを格納することで、平均O(1)の超高速な検索・挿入・削除を実現するデータ構造です。ハッシュ関数は「キーを特定の整数（ハッシュ値）に変換する関数」で、例えば文字列キーの各文字コードの和をテーブルサイズで割った余りをインデックスとする手法があります。同じインデックスに複数のキーが割り当てられる「衝突（コリジョン）」は避けられず、衝突処理として「チェーン法（同インデックスにリストで連結）」と「オープンアドレス法（次の空きバケットを探す）」があります。負荷率（Load Factor: 格納数/テーブルサイズ）が高くなると衝突が増えて性能が低下するため、定期的なリハッシュ（テーブルサイズ拡大）が行われます。FE試験ではハッシュ法の「衝突発生の仕組み」「衝突処理の方法の違い」「探索計算量O(1)の前提（衝突が少ない場合）」が出題ポイントです。Pythonの辞書（dict）やJavaのHashMapはハッシュテーブルの代表実装です。

FE試験での出題ポイント

• 1平均O(1)の検索・挿入・削除が強み（最悪は衝突多発でO(n)）
• 2衝突（コリジョン）の発生メカニズムと処理法（チェーン法・オープンアドレス法）
• 3負荷率（Load Factor）が高くなると性能低下→リハッシュ
• 4FE試験：ハッシュ関数の計算（キーmod テーブルサイズ）のトレース

関連用語