37

N 個のアイテムに対して効率的なHashMap/ベースの構造を作成するには、どの値を渡す必要がありますか?HashMap

ではArrayList、効率的な数は N です (N は将来の成長を既に想定しています)。のパラメータは何HashMapですか? ((int)(N * 0.75d), 0.75d)? もっと？以下？負荷率を変更するとどのような影響がありますか?

4

9 に答える 9

39

負荷率については、HashMap javadocから引用します。

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

.75つまり、実行する特定の最適化がない限り、負荷率を から変更しないでください。初期容量は、変更したい唯一のものであり、N値に応じて設定します-意味(N / 0.75) + 1、またはその領域の何か。これにより、テーブルが常に十分な大きさになり、再ハッシュが発生しなくなります。

于 2009-01-12T10:12:37.667 に答える
21

これらの答えが正しいかどうかを確認するためにいくつかの単体テストを実行しましたが、次を使用していることがわかりました。

(int) Math.ceil(requiredCapacity / loadFactor);

初期容量は、HashMapまたはのいずれかに必要なものを提供するためHashtableです。「必要なもの」とはrequiredCapacity、マップに要素を追加しても、ラップしている配列のサイズが変更されず、配列が必要以上に大きくならないことを意味します。デフォルトの負荷容量は0.75なので、次のようにHashMapを初期化すると機能します。

... = new HashMap<KeyType, ValueType>((int) Math.ceil(requiredCapacity / 0.75));

HashSetは事実上HashMapの単なるラッパーであるため、同じロジックがそこにも適用されます。つまり、次のようにHashSetを効率的に構築できます。

.... = new HashSet<TypeToStore>((int) Math.ceil(requiredCapacity / 0.75));

@Yuval Adamの答えは、が2の累乗である場合を除いて、すべての場合に正しいです(requiredCapacity / 0.75)。この場合、割り当てられるメモリが多すぎます。
@NotEdibleの答えは、多くの場合、メモリを使いすぎます。これは、HashMapのコンストラクター自体が、マップ配列のサイズを2の累乗にするという問題を処理するためです。

于 2012-08-15T14:06:38.997 に答える
6

また、HashMap を小さくすると、ハッシュの衝突が発生する可能性が高くなり、ルックアップが遅くなる可能性があることも注目に値します。したがって、マップのサイズよりも速度を重視する場合は、マップが保持する必要があるデータに対してマップを少し大きくしすぎることをお勧めします。メモリは安価なので、通常、既知の数のアイテムの HashMaps を次のように初期化します。

HashMap<Foo> myMap = new HashMap<Foo>(numberOfElements * 2);

実際、私はこの考えを検証するか捨ててもらいたいと思っています.

于 2009-01-12T10:19:35.763 に答える
4

Yuval の答えは、Hashtable に対してのみ正しいものです。HashMap は 2 の累乗のバケットを使用するため、HashMap については Zarkonnen が実際に正しいです。これはソース コードから確認できます。

  // Find a power of 2 >= initialCapacity
  int capacity = 1;
  while (capacity < initialCapacity)
  capacity <<= 1;

したがって、0.75f の負荷係数は Hashtable と HashMap の間で同じですが、初期容量 n*2 を使用する必要があります。n は、HashMap に格納する予定の要素の数です。これにより、最速の get/put 速度が保証されます。

于 2009-11-25T15:02:39.697 に答える
2

HashMap のソース コードを参照すると役立ちます。

エントリ数がしきい値 (容量 * 負荷率) に達すると、再ハッシュが自動的に行われます。つまり、負荷係数が小さすぎると、エントリが大きくなるにつれて頻繁に再ハッシュが発生する可能性があります。

于 2009-02-25T02:02:08.413 に答える
2

初期化のほとんどの場合、次のサイズ パラメータを使用してListorを作成しても安全です。MapListMap

List<T>(numElements + (numElements / 2));
Map<T,T>(numElements + (numElements / 2));

これは.75* 2ルールに従い、上記の操作のオーバーヘッドを少し節約します。

于 2010-07-27T16:03:17.737 に答える
1

初期容量を間違えることが非常に問題となる可能性がある重要なシステムの非常に大きなHashMapの場合、マップを初期化する最善の方法を決定するための経験的情報が必要になる場合があります。

CollectionSpy（collectionspy.com）は、新しいJavaプロファイラーであり、HashMapが再ハッシュの必要性に近づいていること、過去に再ハッシュされた回数などを一瞬で確認できます。容量ベースのコンテナーコンストラクターに対する安全な初期容量引数を決定するための理想的なツール。

于 2009-07-03T19:24:55.437 に答える
1

ArrayList では、効率的な数は N です (N は将来の成長を既に想定しています)。

ええと、あなたがここで言っていることを誤解しない限り、そうではありません。整数を Arraylist コンストラクターに渡すと、正確にそのサイズの基になる配列が作成されます。余分な要素が 1 つでも必要であることが判明した場合、次に add() を呼び出すときに、ArrayList は基になる配列のサイズを変更する必要があり、この呼び出しに通常よりもはるかに長い時間がかかります。

一方、成長を考慮して N の値について話している場合は、値がこれを超えないことを保証できる場合は、そのような Arraylist コンストラクターを呼び出すことが適切です。この場合、ハンクが指摘したように、マップの類似のコンストラクターは N と 1.0f になります。これは、たまたま N を超えたとしても、適切に機能するはずです (ただし、これが定期的に発生することが予想される場合は、初期サイズとしてより大きな数を渡すことをお勧めします)。

ご存じないかもしれませんが、負荷係数は、マップの容量が増加するポイントであり、総容量の割合です。

編集: Yuval はおそらく、汎用マップの負荷係数を約 0.75 のままにしておく方がよい考えであることは正しいでしょう。キーに連続したハッシュコード (連続した整数キーなど) がある場合、負荷係数 1.0 は見事に機能しますが、それ以外の場合は、ハッシュ バケットとの衝突が発生する可能性が高く、一部の要素のルックアップに時間がかかることを意味します。厳密に必要な数よりも多くのバケットを作成すると、この衝突の可能性が減少します。つまり、要素が独自のバケットに存在する可能性が高くなり、最短時間で取得できるようになります。ドキュメントが言うように、これは時間とスペースのトレードオフです。いずれかが特に重要である場合 (時期尚早に最適化するのではなく、プロファイラーによって示されるように)、それを強調することができます。それ以外の場合は、デフォルトのままにしてください。

于 2009-01-12T10:18:33.347 に答える