オープンアドレス法の欠点

質問

オープンアドレス法についての欠点に「データの物理的な削除ができない」というようなことが書いてあったのですが、なぜこのような欠点が生じるのですか？

また、削除する方法は全くないのですか？

質問が重なってしまいましたが、よろしくお願いします。

回答No.1

rinkun · ベストアンサー

ハッシュテーブルの話題ですよね。

オープンアドレス法ではハッシュ値が同じデータが衝突すると、後から登録するデータは別のハッシュ値を計算してその位置に登録します。
それで先に登録したデータを消したとすると、そのハッシュ値のエントリは空きになっているので、同じハッシュ値で後から登録したデータを検索しようとすると登録されていないことになってしまい検索できません。
これを避けるために実データを削除せずに削除マークだけつけるわけです。

なお、本当にデータを削除する場合はハッシュテーブルを再構築します。

お礼

そうです。ハッシュテーブルです。
とても理解しやすいご回答ありがとうございました。