HashMap初期化パラメーター（ロード/初期容量）

StackOverflow https://stackoverflow.com/questions/434989

  •  10-07-2019
  •  | 
  •  

質問

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

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

役に立ちましたか？

解決

負荷係数については、 HashMap javadoc ：

  

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

つまり、特定の最適化を行う場合を除き、負荷係数は .75 から変更しないでください。変更する必要があるのは初期容量だけで、 N の値に応じて設定します。つまり、（N / 0.75）+ 1 、またはそのエリアの何かを意味します。これにより、テーブルが常に十分に大きくなり、再ハッシュが発生しなくなります。

他のヒント

単体テストを実行しましたこれらの回答が正しかったかどうかを確認し、次を使用することが判明しました：

(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の答えは、（requiredCapacity / 0.75）が2のべき乗である場合を除き、すべての場合に正しいです。この場合、メモリを割り当てすぎます。
HashMapのコンストラクター自体は、maps配列に2の累乗のサイズを持たせたいという問題を処理するため、@ NotEdibleの答えは多くの場合メモリを使いすぎます。

Googleの guavaライブラリには機能があります予想されるアイテム数に最適化されたHashMapを作成します： newHashMapWithExpectedSize

ドキュメントから：

  

十分な「初期容量」でHashMapインスタンスを作成します。成長せずにexpectedSize要素を保持する必要があること...

また、小さい側にHashMapがあると、ハッシュの衝突が発生しやすくなり、ルックアップが遅くなる可能性があります。したがって、マップの速度を本当に気にし、そのサイズをあまり気にしないのであれば、保持する必要があるデータに対して少し大きすぎる値にする価値があるかもしれません。メモリは安価なので、通常、既知の数のアイテムに対してHashMapsを初期化します

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

お気軽に意見の相違を感じてください。実際、このアイデアを検証または破棄していただきたいと思います。

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

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

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

  

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

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

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

負荷係数は、あなたが知らなかった場合、マップの総容量の一部として、容量が増加するポイントです。

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

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

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

List および Map の初期化のほとんどの場合、次を使用して List または Map を作成しても安全ですサイズパラメータ。

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

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

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

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top