本当はむずかしいハッシュテーブル - sumiiの日記
ハッシュテーブルの実装方法に関する問題。
解の1つはすぐに分かった。
すでにコメントにもあったように同じハッシュ値だった要素の1つが削除されると、検索で見つからなくなってしまうことがあるというもの。h[i],h[(i+1)%B]に追加された場合、h[i]が削除されるとh[(i+1)%B]の要素が検索されない。
また、ハッシュ値が同じでh[i],h[(i+1)%B]に追加された後、さらに追加される要素のハッシュ値が(i+1)%Bと同じになった場合にも問題が起きる。
とりあえず見つかったのはハッシュ値が同じになったときに問題が起きるというもの。
解決方法としては削除したときにハッシュテーブルの内容を空にするのではなく、削除されたという情報を入れて、同じハッシュ値で登録された要素があるというのを分かるようにすることかな。
この問題を考えていて実感したはのハッシュテーブルについての理解不足。ハッシュテーブルの実装方法についてはもちろん、ハッシュ値の求め方とか、そもそもハッシュテーブルはどのような場合に使うと有効なのかとか、ちゃんと理解できていない。
追記
コメントを頂いたので、さっそく具体的にコードを書いてみようと思ったが、ハッシュ値の計算ってどうやるのかとか、テスト用のデータってどう用意すればいいのだろうかとか分からないことだらけ。
ランダムなデータや一定範囲全部のデータで試すことはすぐにできそうだが、実装したものが実用上問題ないと判断できるテストってどうすればいいんだろう。
