java - HashMap における負荷係数の重要性は何ですか?

Question

HashMapには と の 2 つの重要なプロパティがsizeありload factorます。Javaのドキュメントを調べたところ0.75f、初期負荷係数であると書かれています。しかし、私はそれの実際の使用を見つけることができません。

負荷率を設定する必要があるさまざまなシナリオと、さまざまなケースでの理想的な値の例を誰かが説明できますか?

Answer 1

ドキュメントはそれをかなりよく説明しています：

HashMap のインスタンスには、そのパフォーマンスに影響を与える 2 つのパラメーターがあります。初期容量と負荷係数です。容量はハッシュ テーブル内のバケットの数であり、初期容量は単にハッシュ テーブルが作成された時点の容量です。負荷率は、容量が自動的に増加する前に、ハッシュ テーブルがどれだけいっぱいになることができるかの尺度です。ハッシュ テーブルのエントリ数が負荷係数と現在の容量の積を超えると、ハッシュ テーブルが再ハッシュされ (つまり、内部データ構造が再構築され)、ハッシュ テーブルのバケット数が約 2 倍になります。

原則として、デフォルトの負荷係数 (.75) は、時間とスペースのコストの間の適切なトレードオフを提供します。値を大きくすると、領域のオーバーヘッドは減少しますが、ルックアップ コストが増加します (get と put を含む HashMap クラスのほとんどの操作に反映されます)。再ハッシュ操作の回数を最小限に抑えるために、初期容量を設定するときは、マップ内の予想エントリ数とその負荷係数を考慮する必要があります。初期容量がエントリの最大数を負荷係数で割った値よりも大きい場合、再ハッシュ操作は発生しません。

すべてのパフォーマンスの最適化と同様に、時期尚早に最適化することを避けることをお勧めします (つまり、ボトルネックがどこにあるかについての確かなデータがない場合)。

Answer 2

テイクのデフォルトの初期容量HashMapは 16 で、負荷係数は 0.75f (つまり、現在のマップ サイズの 75%) です。HashMap負荷率は、容量を 2 倍にする必要があるレベルを表します。

たとえば、容量と負荷率の積は16 * 0.75 = 12です。これは、12 番目のキーと値のペアを に格納した後HashMap、その容量が 32 になることを表します。

Answer 3

負荷率とは？

HashMap がその容量を増やすために使い果たされる容量の量は?

なぜ負荷率?

負荷率はデフォルトで初期容量 (16) の 0.75 であるため、容量が増加する前にバケットの 25% が空きます。バケットの数。

では、多くの空きバケットを保持する必要がある理由と、空きバケットを保持することによるパフォーマンスへの影響は何ですか?

負荷係数を 1.0 に設定すると、非常に興味深いことが起こる可能性があります。

hashCode が 888 であるハッシュマップにオブジェクト x を追加するとします。ハッシュマップでは、ハッシュコードを表すバケットは free であるため、オブジェクト xがバケットに追加されますが、hashCode が別のオブジェクト y を追加する場合は、もう一度言います。また 888 、オブジェクト y は確かにバケットの最後に追加されます (バケットはキー、値、および next を格納する linkedList 実装に他ならないため) これはパフォーマンスに影響を与えます! ルックアップを実行すると、オブジェクト yがバケットの先頭に存在しなくなるため、所要時間はO(1)になりません。今回は、同じバケットにあるアイテムの数によって異なります。ちなみに、これはハッシュ衝突と呼ばれ、負荷係数が 1 未満の場合でも発生します。

パフォーマンス、ハッシュ衝突、負荷要因の相関関係は?

負荷率が低い= 空きバケットが多い =衝突の可能性が低い= パフォーマンスが高い = 必要なスペースが大きい。

どこか間違っている場合は修正してください。

Answer 4

ドキュメントから：

負荷率は、容量が自動的に増加する前に、ハッシュ テーブルがどれだけいっぱいになることができるかの尺度です。

それは実際には特定の要件に依存します。初期負荷係数を指定するための「経験則」はありません。