19

サイズがmaxthreshold値を超えた場合、ハッシュマップまたはハッシュテーブルで再ハッシュプロセスはどのように実行されますか？

すべてのペアがバケットの新しい配列にコピーされただけですか？

編集：

再ハッシュした後、（リンクリスト内の）同じバケット内の要素はどうなりますか？つまり、再ハッシュした後も同じバケットに残りますか？

4

3 に答える 3

22

問題の最大しきい値は負荷率と呼ばれます。

負荷率は約0.75にすることをお勧めします。負荷率は（m / n）として定義されます。ここで、nはハッシュテーブルの合計サイズであり、mは、基になるデータ構造のサイズの増分が必要になる前に挿入できるエントリの優先数です。

再ハッシュは、次の2つの場合に実行できます。

  1. 現在のm'/n比が負荷率を超えて増加した場合

  2. M'/ n比は非常に低い値、たとえば0.1に低下します

どちらの場合も、m'は現在のエントリ数です。また、どちらの場合も、現在のエントリをより大きなまたはより小さなハッシュテーブルにシフトする必要があります。

質問のコンテキストでは、再ハッシュは、エントリにハッシュ関数を適用して、エントリを別のハッシュテーブルに移動するプロセスです。以前使用していたハッシュ関数を使用することも、まったく新しい関数を使用することもできます。

注意：衝突が発生した場合も再ハッシュが行われます。（これは衝突を処理する方法でもあります。）

さらにコンテキストと詳細なディスカッションを追加するには、私のブログHashingBasicsにアクセスしてください。

于 2012-05-23T13:23:13.463 に答える
16

マップ内の要素数が最大しきい値に達すると、ハッシュ マップの再ハッシュが行われます。

通常、負荷係数の値は 0.75 で、デフォルトの初期容量値は 16 です。要素の数が容量の 0.75 倍に達するか超えると、マップの再ハッシュが行われます。この場合、要素数が 12 の場合、再ハッシュが発生します。(0.75 * 16 = 12)

再ハッシュが発生すると、新しいハッシュ関数または同じハッシュ関数を使用できますが、値が存在するバケットが変わる可能性があります。基本的に、再ハッシュが発生すると、バケットの数は約 2 倍になるため、値を配置する必要がある新しいインデックスが変更されます。

再ハッシュ中、各バケットのリンクされたリストの順序が逆になります。これは、HashMap が新しい要素を末尾に追加せず、新しい要素を先頭に追加するために発生します。そのため、再ハッシュが発生すると、各要素を読み取り、それを新しいバケットの先頭に挿入し、新しいマップの先頭に古いマップから次の要素を追加し続けるため、リンクされたリストが逆転します。

複数のスレッドが同じハッシュ マップを処理している場合、無限ループが発生する可能性があります。

上記のケースで無限ループがどのように発生するかを示す詳細な説明は、ここにあります: http://mailinator.blogspot.hu/2009/06/beautiful-race-condition.html

マップに挿入された要素をキーでソートする必要がある場合は、TreeMap を使用できます。ただし、キーの順序が問題にならない場合は、HashMap の方が効率的です。

于 2015-03-02T14:03:00.747 に答える
11

ハッシュ – 再ハッシュと競合状態

基本的に、ハッシュ マップの作成中に、コレクションはデフォルトの容量 (2^4、つまり 16) を割り当てます。要素がマップに追加される後の段階と、特定の段階の後、最初に定義された容量に近づくと、パフォーマンスを維持するために再ハッシュが必要になります。

コレクション用に定義された LoadFactor があり (.75 が適切と言われています)、これは時間と空間の適切なインデックスを指定します。

  • 負荷係数が大きい => スペース消費量が少ないが、ルックアップ数が多い
  • 小さな負荷率 => 必要な要素数と比較して大きなスペース消費。

Java 仕様では、適切な負荷係数の値は .75 であることが示唆されています

したがって、ハッシュに 10 個の要素を保存する最大要件があるとします。次に、Good Loadfactor .75 = コレクションに 7 個の要素を追加した後に再ハッシュが発生することを考慮します。この場合、要件が 7 に達しない場合、再ハッシュは発生しません。

ハッシュマップに格納される要素が非常に多い場合は、十分な容量を持つ HashMap を作成することを常にお勧めします。これは、自動再ハッシュを実行させるよりも効率的です。

RACE 条件 : 特定のバケットのリンク リストに格納されている内部要素の再ハッシュを実行中。順番が逆になります。2 つのスレッドが同時に競合状態に遭遇したと仮定すると、順序が変更されたため、トラバーサル中に 2 番目のスレッドが無限ループに入る可能性があります。

于 2014-08-08T19:44:28.173 に答える