質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

Q&A

解決済

1回答

2526閲覧

オープンアドレス法のハッシュの探索(削除)アルゴリズムの応用問題がわかりません。

asapan

総合スコア60

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

ハッシュ

ハッシュは、高速にデータ検索を行うアルゴリズムのことです。

0グッド

0クリップ

投稿2019/06/19 05:05

前提・実現したいこと

アルゴリズムの勉強をしていて、ハッシュ法のオープンアドレス法で、削除済みフラグを用いない削除方法を
考えたアルゴリズムの問題があるのですが考えてもいまいちわからず答えもないので詰まっています。お力をお貸しください。

詳細

具体的に以下の画像の設問2以降の、問8からがわかりません。
(問1,2,3,4,5,6は今回の質問に直接関係ありませんが多少目を通していただけるとヒントになるのかもしれません。)

イメージ説明

このアルゴリズムはオープンアドレス法ですが削除済みというフラグを使えないので、削除した個所をそのままにできない(削除フラグを使わないと正しく探索ができなくなる)ので、削除した個所に別のところからずらして来る(衝突でずらして格納してきたデータを、削除によって空いたところに戻すようなイメージ)ようなアルゴリズムだと考えました。それで

問8-1は「TABLE[i]」
問8-2は「D1」が答えかなと思いました。
問9は「set r <- h(KEY[i])」となっているのでハッシュの値ですが、D3-2のifの条件文から推測するに削除位置より”前”(”前”はiに+1していく方向とする)に本来格納されるべきキーが衝突によってずれて後ろに格納されたものかどうかを判定するキーの値、という風に考えました。
問10は循環するハッシュテーブルの図(循環の線形リストみたいな図になりました)を描いてみたのですが、D3-2の意味を説明というのはわかりませんでした

よろしくお願いいたします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

イメージしたアルゴリズムは合っていると思います。
答えは推測ですが

8-1: ←KEY[i]
8-2: D1
※D4は「衝突でずらして格納してきたデータを、削除によって空いたところに戻す」という部分です。
ずれていたKEY[i]を削除した位置Table[j]に入れます

9:KEY[i]が衝突しなかったときの挿入位置
※単純にハッシュ関数で返ってくる値の意味を問うているように見えます

10:iとjの間にrがあるか(i=rは可、j=rは不可)を判定しています。
rがiとjの間に有る場合KEY[i]の移動は発生しません。
iとjの間とは以下のような範囲を表します(循環構造書いたなら分かるとおもいますが

||i|||j||||||
|:--|:--|:--|:--:|--:|
||←|−|−|→|

|||||j||||i||
|:--|:--|:--|:--:|--:|
|−|−|−|−|→||||←|−|

投稿2019/06/19 06:40

hellomartha

総合スコア329

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

asapan

2019/06/19 09:58

ご回答ありがとうございます。 8-1: ←KEY[i] は確かにそうですね、TABLE[i]は手元の紙から移し間違えておりました。 9に関しては少し複雑に考えすぎていたようですね...。確かに仰る通りな気がします。 全て理解ができました、本当にありがとうございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問