ハッシュ法とは
キーから計算した値（ハッシュ値）をそのまま格納位置にして、ほぼ一定時間で検索する方法。
解説
ハッシュ法は、キーをハッシュ関数に通して得た値を配列の添字として使い、データの格納と検索をほぼ一定時間（平均 O(1)）で行う方法です。異なるキーが同じハッシュ値になる「衝突（シノニム）」が起こり得るため、対策が必要です。代表的なのは、同じ位置に鎖状にデータをつなぐ「チェイン法」と、空いている別の位置を探して入れる「オープンアドレス法」です。
試験での出方
シノニム（衝突）の意味と、チェイン法・オープンアドレス法の動作を問う問題が出ます。格納位置を計算で求める点が、二分探索との大きな違いです。
あわせて読みたい用語
この用語が解説に出てくる問題
- 平成31年度 春期 問18データ検索時に使用される，理想的なハッシュ法の説明として，適切なものはどれか。
- 平成30年度 春期 問7表探索におけるハッシュ法の特徴はどれか。
- 平成29年度 春期 問27RDBMSが二つの表を結合する方法のうち，ソートマージ結合法に関する記述はどれか。
- 令和6年度 秋期 問6自然数をキーとするデータを，ハッシュ表を用いて管理する。キー x のハッシュ関数 h(x) を h(x) ＝ x mo…
- 令和5年度 春期 問19ハッシュ表の理論的な探索時間を示すグラフはどれか。ここで，複数のデータが同じハッシュ値になることはないものとする。
この用語がよく出る分野：アルゴリズムの要点と過去問一覧