テクノロジ系出題頻度 2/3
ハッシュテーブル
はっしゅてーぶる
定義
キーからハッシュ関数で計算したインデックスで値を格納・検索するデータ構造。
詳細解説
キー（key）をハッシュ関数で数値に変換し、その値をインデックスとして配列に格納する。平均的に挿入・検索・削除がO(1)と非常に高速で、辞書型（dict、map、Hashなど）の内部実装で使われる。異なるキーが同じハッシュ値になる「衝突」が起きるため、チェイン法やオープンアドレス法で対処する。データベースのインデックス、キャッシュ、重複排除などに広く用いられる。
「ハッシュテーブル」が出る問題
関連用語
よくある質問
Q. ハッシュテーブルとは何ですか？
A. キーからハッシュ関数で計算したインデックスで値を格納・検索するデータ構造。
Q. IT パスポート試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 2/3 （★2）。 中程度の頻度で出題されます。