ハッシュインデックスとは？

ハッシュインデックスの意味

キーにハッシュ関数を適用して得た値から格納位置を直接算出する方式。

ハッシュインデックスの具体例

会員番号をハッシュ関数にかけ、算出したバケットを直接読みに行く。

ハッシュインデックスは試験でどう引っ掛けられる？

等価検索は非常に速いが、値の順序が失われるため範囲検索や整列には使えない。異なるキーが同じ位置に割り当てられる衝突（シノニム）への対処（連鎖法・オープンアドレス法）が必要。

ハッシュインデックスと関連する用語

• B+木
• シノニム

ハッシュインデックスが出た過去問

• 格納アドレスが1～6の範囲の直接編成ファイルにおいて，次の条件でデータを格納した場合，アドレス1に格納されているデータのキー値はどれか。〔条件〕(1) キー値が…

  正解：13

  要点：直接編成の衝突はオープンアドレス法で次の空き番地へ回る

  キー値を5で割った余りに1を加えるので、3→4番地、4→5番地に格納される。次の8は余り3で4番地が埋まっており、5も埋まっているため6番地に入る。続く13も同じく4番地が指定されるが4・5・6が埋まっているため、最終アドレスの次である1番地に格納される。

  出典：平成28年度 秋期 基本情報技術者試験 午前 問20（IPA）

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

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

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

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

  出典：平成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）