Open Address

オープンアドレス法にお けるデータ探索の方法 オープンアドレス法では、以下のいずれかの条件になるまで、 再ハッシュを行って探索を続けます。(以下の条件のいずれかになると探索を終了します)

  • 該当するデータが見つ かった
  • 「空」のバケットに移動した
  • ハッシュテーブルを一巡した

オープンアドレス法では、ハッシュテーブルのサイズ分だけのデータを格納することができます。

ハッシュテーブルにおけるオープンアドレス法の実装

オープンアドレス法の削除処理の注意事項

オープンアドレス法では、同じハッシュ値を持つデータを削除する場合に工夫が必要です。同じハッ シュ値を持つ複数のデータを格納している状態で、本来のハッシュ値の値を「削除」と扱ってしまうと、他のデータを見つけることができなくなるからです。

そこで、オープンアドレス法では、データの状態を

  • 空(カラ) 「ー」 ・・・ 初期状態。一度も使われたことのないバケッ ト。
  • 削除済み「☆」 ・・・ データを保持したことがあ るが、削除されている状態のバケット
  • データあり

の3つの状態で管理します。ここで重要なのは、「空」と「削除済み」とは意味が違うということで す。