問題タブ [linear-probing]

データ構造クラスの割り当てを行っています。負荷率が.1、.2、.3、....、および.9の線形プロービングを調査するように依頼されました。テストの公式は次のとおりです。

線形プロービングを使用した平均プローブ長は、おおよそです

成功->（1 + 1 /（1-L）** 2）/ 2
または
失敗->（1 + 1（1-L））/2。

上記の式を使用して理論を見つける必要があります（式に負荷率をプラグインするだけです）。次に、経験を計算する必要があります（これを行う方法はよくわかりません）。これが残りの要件です

**負荷率ごとに、1〜50000（両端を含む）のランダムに生成された10,000個の正の整数が、「正しい」サイズのテーブルに挿入されます。「正しい」は、テストしている負荷率に厳密に基づいています。繰り返しが許可されています。ランダムに生成されたintの式が正しいことを確認してください。java.utilにはRandomというクラスがあります。これを使って！右側のテーブル（Lに基づく）に10,000 intがロードされたら、1〜50000の範囲で新しく生成されたランダムintを100回検索します。2つの数式のそれぞれの平均プローブ長を計算し、使用される分母を示します。したがって、各計算では、たとえば、.5負荷の各テストには、約20,000（プライムに調整）の>>サイズのテーブルがあり、同様に。の各テストもあります。

プログラムは、テストされたさまざまな負荷係数、各検索の平均プローブ（平均の計算に使用される2つの分母が100に加算されます）、および上記の式を使用した理論上の回答を表示して実行する必要があります。。**

経験的な成功を計算するにはどうすればよいですか？

これまでの私のコードは次のとおりです。

}

AVAILABLE線形プロービングには、アイテムが削除されたときに置き換えられるという特別な値があります。

そして、キーを挿入するときに、空のセル（これは単にセルがnull？）またはを含むセルを探します。AVAILABLE私が理解していないのは、空のセルnullが特別な値を持つのではなく、AVAILABLE単にセルnull？

使用することに対する利点は何AVAILABLEですか？

そこで、配列のみを使用して作成した HashTable 実装をここに用意し、コードを少し手伝いました。残念ながら、「get」または「put」メソッドの実行中に誰かが追加した行の 1 つがよくわかりません。以下のwhileループで正確に何が起こっているのでしょうか? リニアプロービングの方法ですよね？また、ループがチェックしている条件をチェックするのはなぜですか?

具体的には、

完全なリファレンスとして、以下に Java クラス全体を示します。

ありがとうございました。

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

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

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

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

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

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

線形プローブ衝突解決法を使用して、ハッシュ テーブルの適切な削除関数を作成しようとしています。

ハッシュ テーブルからいくつかのレコードを削除するテスターを実行します。特定の時点で、検索機能が削除する要素を見つけることができません。ただし、それはまだテーブルにあるはずです。remove() で再ハッシュを間違った方法で行っていると思います。

クラスHashTableには membertable型の構造体の配列が含まれますRecord

これも私の検索機能で、うまく機能しているように見えますが、間違っている可能性があります

線形プローブのために正しい方法で削除を行っているかどうかを判断するのを手伝ってもらえますか?

1 つの String 配列の 1 つの次元と 2 次元の int 配列を使用してハッシュ テーブルを作成しています。私は衝突検出に線形プロービングを使用しており、衝突が検出された場合、単語の hashCode がインデックスではなくなることに気付いたとき、このプログラムを実際に処理していました。後で使用するためにそのインデックスを保存するにはどうすればよいですか?

整数のみを取るダブルハッシュテーブルを書いています。

SetData() を使用してテーブルにデータを挿入しようとしています

サイズが 100 のテーブルに 100 個の整数アイテムを配置した後、テーブルにはいくつかのインデックスが空白のままになっていることが示されます。最悪のケースであるO（N）がかかります。私の質問は、検索時間の最悪の場合でも、アイテムを空のスペースなしでテーブルに挿入する必要があるということですよね? 関数の問題が見つかりません。

追加の質問。ハッシュにはよく知られたアルゴリズムがあり、二重ハッシュの目的は可能な限り衝突を少なくすることであり、H2(T) は H1(T) のバックアップです。しかし、よく知られているハッシュ アルゴリズム (MD5、SHA など、セキュリティについては話していません。よく知られているアルゴリズムにすぎません) の方が高速で分散性が高いのであれば、なぜ二重ハッシュが必要なのですか?

ありがとう！

特定のリスト内のどのインデックスが、そのインデックスがハッシュテーブルに割り当てられる前に必要な最大数のプローブを提供するかを見つけようとしています。次のようなリストがあります。

[4、9、12、3、7、26、16、20、11]

そして、そのリストのどの値が最長のプローブ シーケンスを作成するかを把握する必要があります。私はかなり長い間これに固執しており、どんな助けでも大歓迎です。