オープンアドレス法とは？

オープンアドレス法の意味

ハッシュの衝突が起きたとき、別の空いている格納位置を規則に従って探し、そこへ格納する方法。空き位置の探し方には、次の位置を順に見る線形探査や、間隔を2乗で広げる方式などがある。ポインタが不要で配列だけで実装できる。

オープンアドレス法の具体例

位置5が埋まっていれば6、6も埋まっていれば7…と空きを探して格納する（線形探査）。探索時も同じ順序で空き位置に当たるまで調べる。配列の8割程度まで埋まると探索回数が急増するため、余裕を持ったサイズ設計が必要になる。

オープンアドレス法は試験でどう引っ掛けられる？

削除が単純でない点が要注意。データをただ消して空きにすると、その先に格納されたデータへ到達できなくなるため「削除済み」の印を残す必要がある。また格納件数は配列サイズを超えられない。

オープンアドレス法と関連する用語

• チェイン法
• シノニム
• ハッシュ関数

オープンアドレス法が出た過去問

• 格納アドレスが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）