【応用情報技術者試験】オープンアドレス法

オープンアドレス法とは、ハッシュテーブルでハッシュ値（格納アドレス）が重複（衝突）した際に、別の空きアドレスを探索してデータを格納する手法です。連結リストを使わずテーブル内に直接格納し、衝突時は「再ハッシュ（Rehashing）」と呼ばれる処理で、線形探索（隣を探す）や二次探索（段階的に離れた場所を探す）、二重ハッシュ（別の関数で探す）などを用いて空き場所を見つけます。 

オープンアドレス法の仕組み

• 基本的な流れ:
  1. キーからハッシュ値を計算し、アドレスを決定する。
  2. そのアドレスが空いていればデータを格納。
  3. 空いていなければ、再ハッシュ関数を使って次候補のアドレスを計算する。
  4. 空きが見つかるまでこのプロセスを繰り返す。
• 主な再ハッシュ（プロービング）方法:
  • 線形探索法 : (h(k) + 1), (h(k) + 2), … と隣接するアドレスを順に探す。実装は簡単だが、データが偏る（クラスタリング）しやすい。
  • 二次探索法 : (h(k) + 1^2), (h(k) + 2^2), … と二次関数的に離れたアドレスを探す。線形探索よりクラスタリングを緩和できる。
  • 二重ハッシュ法 : 別のハッシュ関数 h'(k) を用いて (h(k) + 1 * h'(k)), (h(k) + 2 * h'(k)) と探す。クラスタリングが起こりにくく効率的。
• 利点: 連結リストを使わないため、メモリ効率が良い（ポインタなどのオーバーヘッドがない）。
• 欠点: ハッシュテーブルのサイズ以上にデータを格納できず、満杯になりやすい。削除時の処理（削除済みマーク）が複雑になる。