ハッシュ表（ハッシュ法）とは？

ハッシュ表（ハッシュ法）の意味

キーをハッシュ関数で計算して格納位置（添字）を直接求める方式。データ量が増えても比較回数がほとんど増えず、理想的には探索・追加・削除がO(1)で行える。FEではハッシュ関数の計算結果を求める問題と、衝突が起きたときの動作が問われる。

ハッシュ表（ハッシュ法）の具体例

ハッシュ関数を「キーを7で割った余り」とすると、キー23は23 mod 7 = 2なので添字2の位置へ格納する。探索時も同じ計算をするだけで位置が分かるため、表の中を順に見ていく必要がない。

ハッシュ表（ハッシュ法）は試験でどう引っ掛けられる？

「常にO(1)」ではない。衝突が多発すると同じ位置に連なったデータを順にたどることになり、最悪はO(n)まで劣化する。また、ハッシュ表は順序を保持しないので、範囲検索や整列順の取り出しには向かない。異なるキーが同じ値になること自体は関数の欠陥ではなく、チェイン法（同じ位置に連結リストをぶら下げる）やオープンアドレス法（空きを探して置く）で処理する。

ハッシュ表（ハッシュ法）と関連する用語

• 配列
• 二分探索木
• 計算量とO記法（オーダ記法）

ハッシュ表（ハッシュ法）が出た過去問

• 表探索におけるハッシュ法の特徴はどれか。

  正解：キーの関数値によって格納場所を決める。

  要点：ハッシュ法はキーの関数値で格納位置を決め、衝突対策が要る

  ハッシュ法は、キーにハッシュ関数を適用して得た値から格納位置を直接決める方式である。キーを比較しながら探すのではなく計算で位置が求まるため、理想的にはデータ件数によらず一定時間で探索できる。ただし異なるキーが同じ位置に割り当てられる衝突（シノニム）は起こり得るので、チェイン法やオープンアドレス法などの対策が必要になる。

  出典：平成30年度 春期 基本情報技術者試験 午前 問7（IPA）

• 10進法で5桁の数a1 a2 a3 a4 a5を、ハッシュ法を用いて配列に格納したい。ハッシュ関数をmod(a1＋a2＋a3＋a4＋a5, 13)とし、求めたハ…

  正解：2

  要点：ハッシュ値は「桁の総和 mod 除数」で機械的に求める

  ハッシュ関数は各桁の数字の合計を13で割った余りと定義されている。54321の各桁は5、4、3、2、1なので合計は15、15を13で割ると商1・余り2となる。したがって格納位置は2である。

  出典：令和1年度 秋期 基本情報技術者試験 午前 問10（IPA）

• データ検索時に使用される、理想的なハッシュ法の説明として、適切なものはどれか。

  正解：データを特定のアルゴリズムによって変換した値を格納アドレスとして用いる、高速でスケーラビリティの高いデータ検索技術である。

  要点：ハッシュ法はキーを計算した値を格納位置に使う

  ハッシュ法は、キーの値を一定の計算式（ハッシュ関数）で変換し、得られた値を格納位置として直接使う方式である。理想的には1回の計算で目的の位置が定まるため、データ量が増えても探索時間がほとんど変わらない。衝突が起きにくい関数を選ぶことが性能維持の鍵になる。

  出典：令和1年度 春期 基本情報技術者試験 午前 問18（IPA）

• 10進法で5桁の数a1 a2 a3 a4 a5を、ハッシュ法を用いて配列に格納したい。ハッシュ関数をmod(a1+a2+a3+a4+a5, 13)とし、求めたハ…

  正解：2

  要点：ハッシュ値は各桁の和を除数で割った余りで求める

  ハッシュ関数は各桁の数字を足した合計を13で割った余りを返す。5桁の数の各桁を合計すると5＋4＋3＋2＋1で15になる。15を13で割ると商1・余り2なので、ハッシュ値は2となり、配列の位置2に格納される。

  出典：令和4年度 s 基本情報技術者試験 kamokuA 問7（IPA）

• キーが小文字のアルファベット1文字（a, b, …, z のいずれか）であるデータを、大きさが10のハッシュ表に格納する。ハッシュ関数として、アルファベットのA…

  正解：dとx

  要点：下1桁のハッシュは10文字離れた文字どうしが衝突する

  アルファベットのASCIIコードは連続しているので、下1桁は文字が10個進むごとに同じ値に戻る。つまりアルファベット順で10文字離れた文字どうしがハッシュ値が等しくなり衝突する。dとxはd、e、…、xと数えてちょうど20文字離れているため下1桁が一致し、衝突が起こる。

  出典：令和6年度 （公開問題） 基本情報技術者試験 kamokuA 問2（IPA）