チェイン法とは？

チェイン法の意味

ハッシュの衝突対策として、同じ格納位置になったデータを連結リストでつないで保持する方法。各位置はリストの先頭へのポインタを持つ。格納件数が配列サイズを超えても登録でき、削除も単純にリストから外すだけで済む点が長所。

チェイン法の具体例

位置5にキー25が入っている状態でキー35が来たら、25の後ろに35をつなぐ。探索時は位置5のリストを先頭からたどり、目的のキーと一致する要素を探す。リストの平均長が2なら比較は平均2回程度で、件数が偏るほど遅くなる。

チェイン法は試験でどう引っ掛けられる？

「配列がいっぱいになると登録できない」のはオープンアドレス法であり、チェイン法はポインタ用の領域さえあれば登録できる。ただしポインタのぶん記憶領域が増える点、リストが長くなるとO(n)に近づく点が問われる。

チェイン法と関連する用語

• オープンアドレス法
• シノニム
• 連結リスト

チェイン法が出た過去問

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

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

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

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

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