1 つの String 配列の 1 つの次元と 2 次元の int 配列を使用してハッシュ テーブルを作成しています。私は衝突検出に線形プロービングを使用しており、衝突が検出された場合、単語の hashCode がインデックスではなくなることに気付いたとき、このプログラムを実際に処理していました。後で使用するためにそのインデックスを保存するにはどうすればよいですか?
2 に答える
1
オープン アドレッシングでは、リニア プローブは衝突を解決するためだけに使用されるわけではありません。また、検索対象のキーを検索するためにも使用されます。常にハッシュ コードから派生したインデックスから開始し、探しているものが見つかるか、空のスロットまたは別のハッシュ コードのエントリに到達するまで先に進みます。これは、キーが見つかるまでチェーンをたどる必要がある別のチェーンとまったく違いはありません。
于 2015-04-02T17:38:30.763 に答える
1
これは、線形プロービングの欠点の 1 つです。衝突が発生した場合は、次に利用可能なインデックスに移動する必要がありますが、次の要素が探しているものであることが保証されないため、複雑さが O(n) になり、予想される O(1 ）。インデックスごとにバケットを用意することを検討してください。衝突が発生した場合でも、適切なインデックスを取得できる場合は、たとえば LinkedList を反復処理して、探している値を見つける必要があります。
リニア プローブは、ストレージが限られているデバイスに適しています。デスクトップでプログラムを作成している場合は、バケット アプローチまたは公式用語のセパレート チェーンをお勧めします。お役に立てれば
于 2015-04-02T16:35:18.200 に答える