問題タブ [quadratic-probing]

ハッシュテーブルの現在の実装は線形プロービングを使用しており、今度は2次プロービングに移行したいと思います（後でチェーン化とおそらくダブルハッシュにも移行します）。いくつかの記事、チュートリアル、ウィキペディアなどを読みましたが、まだ正確に何をすべきかわかりません。

線形プロービングは、基本的に1のステップがあり、それは簡単に実行できます。ハッシュテーブルから要素を検索、挿入、または削除するときは、ハッシュを計算する必要があり、そのために次のことを行います。

次に、検索、挿入、または削除中に、次のように空きバケットが見つかるまでテーブルをループします。

Quadratic Probingに関しては、「インデックス」ステップサイズの計算方法を変更する必要があると思いますが、それをどのように行うべきかわかりません。私はさまざまなコードを見てきましたが、それらはすべて多少異なります。

また、ハッシュ関数がそれに対応するように変更されたQuadratic Probingのいくつかの実装を見てきました（すべてではありません）。その変更は本当に必要ですか、それともハッシュ関数の変更を避けてQuadratic Probingを使用できますか？

編集： 以下のEli Benderskyによって指摘されたすべてを読んだ後、私は一般的な考えを得たと思います。http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspxのコードの一部は次のとおりです。

私が得られないことが2つあります...彼らは、二次プロービングは通常、を使用して行われると言いますc(i)=i^2。ただし、上記のコードでは、次のようなことを行っていますc(i)=(i^2-i)/2

私はこれを自分のコードに実装する準備ができていましたが、単純に次のようにします。

...ではなく：

どちらかといえば、私はします：

...他のコード例が2つに分かれているのを見たからです。理由はわかりませんが...

1）なぜステップを引くのですか？
2）なぜ2でダイビングするのですか？

ハッシュテーブルに挿入するのに本当に助けが必要です。私は今それを完全に理解しているわけではありません。誰かが二次および線形プロービングを素人の言葉で説明できますか？

これは私が取り組んでいるコードです。私は誰かにそれをするように頼んでいません、私は本当に全体の概念を学ぶのを手伝う必要があります

どんな助けでも大歓迎です。

これは宿題の質問ですが、何かが欠けていると思います。それは尋ねます：

線形プロービングで実装されたハッシュ テーブルを埋めるm 個のキーのシーケンスを提供し、それを埋める時間が最小になるようにします。

その後

mキーの別のシーケンスを提供しますが、それを埋める時間が最大になるようにします。ハッシュ テーブルが 2 次プロービングを実装している場合は、これら 2 つの質問を繰り返します。

ハッシュ テーブルのサイズがmであると仮定することしかできません。これは、指定された唯一の数値であり、負荷係数を説明する前にハッシュ テーブルのサイズを指定するためにその文字を使用してきたためです。しかし、シーケンスをテーブルにハッシュするハッシュ関数を知らずに、最初のシーケンスを実行することは考えられません。

たとえば、すべてのエントリを同じインデックスにハッシュするなど、不適切なハッシュ関数である場合、シーケンスがどのように見えるかに関係なく、それを埋めるための最小時間と最大時間の両方に O(n) 時間がかかります。そして、平均的なケースでは、ハッシュ関数は問題ないと仮定しますが、そのハッシュ関数がテーブルを埋めるのにかかる時間をどのように知ることができますか?

これらの質問は、ハッシュされたシーケンスよりもハッシュ関数にリンクされているのではないでしょうか?

2 番目の質問については、ハッシュ関数に関係なく、同じキーがm回繰り返されるサイズmのシーケンスが最大時間を提供すると仮定できます。これは、2 番目のエントリから線形プローブが発生するためです。O(n)時間かかると思います。あれは正しいですか？

最近、ハッシュテーブルについて学んでいます。コリジョン レゾリューションの例がいくつかありますが、そのうちの 1 つは二次プロービングです。なぜ二次プロービングを使用するのでしょうか? 彼は、ハッシュ テーブルが常に半分以下になることを知っていますか? もしそうなら、なぜ彼はそもそもそんなに大きなテーブルを使うのですか?

二次プローブ アルゴリズムと線形プローブ アルゴリズムを区別するのに問題があります。概念的な説明を読んでいると、最後に試したインデックスに I^2 が繰り返し追加されているのがわかります。ここではどうですか？リニアプロービングはこれを何に変えますか? 私が読んでいることから、以下の方法は二次プロービングを実装しています。

特定のハッシュ値に対して、線形プローブによって生成されるインデックスは次のとおりです。

h、h+1、h+2、h+3など。

特定のハッシュ値に対して、二次プロービングによって生成されるインデックスは次のとおりです。

h、h+1、h+4、h+9など。

線形の場合はクラスターが形成されますが、二次の場合はクラスターが形成されません。

しかし、両方のプロセス（メソッド）が挿入または検索に同じ数のステップを必要とする場合、二次は線形よりも効率的です。ありがとう！

59 個の要素 (各要素の値は整数) を持つハッシュ テーブルがあるとします。インデックス 15 は空白で、テーブルの残りの部分はデータでいっぱいです。挿入したい数によっては、二次プロービング式が要素 15 にヒットすることはありません。

数値 199 を挿入するとします (以下で使用している hashFunc() 関数を使用して 22 にハッシュする必要があります)。

線形プロービングが二次プロービングと同じくらい優れているのは、どのような負荷率ですか? 二次方程式が勝ち始めるのはいつですか?

二次プローブを使用してオープン ハッシュ テーブルを実装しています。私のデータベースは java String[] です (私のオブジェクトはstring のみに制限されています)。削除には遅延削除を使用しますが、非常に効率的に実装したいと考えています。まったく新しいフラグの配列 (アクティブ/空/削除済み) を保持するよりもエレガントなソリューションがあると確信しています。

削除するときに既知の定数文字列 (たとえば ""、空の文字列) を割り当て、必要に応じてセルの内容をその文字列自体のポインターと比較することを考えました (String.equals の代わりに == を使用)。そうすれば、セルが削除されたことがわかりますが、アクティブなセルは、定数を指すことはないため、あらゆる種類の文字列 (空のものを含む) を保持できます。

私の考えに問題はありますか？

テンプレートを使用するハッシュマップを作成しようとしています。テンプレートは、ハッシュ関数 (hash ( int key, int size ) の形式) とプローブ関数 (probing および probe ( int key, int size ) の場合は probe ( int i ) の形式) を取ります。ダブルハッシュの場合. 私の言っていることを理解していただければ幸いです. これが私のメインです:

ご覧のとおり、プローブ関数として 2 つの異なるポインター関数型を渡しています。ダブルハッシュの場合、「Hash2」がプローブ関数として渡されます。これは、ヘッダー ファイル (つまり、クラス宣言、ノード宣言、および挿入メソッド) からのスニッパーです。

私の挿入メソッドの "double_hash_ 条件の "else" 部分は、もちろん同じプローブ、テンプレート関数を 2 つの異なる引数番号で呼び出しているため、エラーにフラグを立てています。理由を知っています.私はこれに対する解決策を求めています-または回避策.ありがとう.