Open Address
オープンアドレス法にお けるデータ探索の方法 オープンアドレス法では、以下のいずれかの条件になるまで、 再ハッシュを行って探索を続けます。(以下の条件のいずれかになると探索を終了します)
- 該当するデータが見つ かった
- 「空」のバケットに移動した
- ハッシュテーブルを一巡した
オープンアドレス法では、ハッシュテーブルのサイズ分だけのデータを格納することができます。
ハッシュテーブルにおけるオープンアドレス法の実装
オープンアドレス法の削除処理の注意事項
オープンアドレス法の削除処理の注意事項
オープンアドレス法では、同じハッシュ値を持つデータを削除する場合に工夫が必要です。同じハッ シュ値を持つ複数のデータを格納している状態で、本来のハッシュ値の値を「削除」と扱ってしまうと、他のデータを見つけることができなくなるからです。
そこで、オープンアドレス法では、データの状態を
- 空(カラ) 「ー」 ・・・ 初期状態。一度も使われたことのないバケッ ト。
- 削除済み「☆」 ・・・ データを保持したことがあ るが、削除されている状態のバケット
- データあり
の3つの状態で管理します。ここで重要なのは、「空」と「削除済み」とは意味が違うということで す。