HashMap-Initialisierungsparameter (Laden / Anfangskapazität)

Question

Welche Werte sollte ich übergeben, um eine effiziente zu erstellen HashMap / HashMap basierte Strukturen für N Elemente?

In einem (n ArrayList, die effiziente Zahl ist N (N geht bereits von zukünftigem Wachstum aus).Was sollten die Parameter für a sein? HashMap?((int)(N * 0,75d), 0,75d)?Mehr?Weniger?Welche Auswirkung hat eine Änderung des Lastfaktors?

Answer 1

In Bezug auf den Belastungsfaktor, werde ich zitiere einfach aus dem

Answer 2

Ich lief einige Unit-Tests um zu sehen, ob diese Antworten richtig waren und es stellte sich heraus, dass die Verwendung:

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

als die Anfangskapazität gibt, was Sie wollen entweder eine HashMap oder Hashtable. Mit „was Sie wollen“ meine ich, dass requiredCapacity Elemente auf der Karte hinzugefügt wird das Array nicht dazu führen, die es Einwickeln, um die Größe und das Array wird nicht größer sein als erforderlich. Da die Standardladekapazität beträgt 0,75, eine HashMap Initialisierung wie so funktioniert:

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

Da ein HashSet ist effektiv nur ein Wrapper für eine HashMap, auch die gleiche Logik gilt es, das heißt Sie ein HashSet effizient wie dieses Konstrukt kann:

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

@Yuval Adams Antwort ist richtig für alle Fälle außer wo (requiredCapacity / 0.75) eine Potenz von 2, in diesem Fall ist es zu viel Speicher reserviert.
Antwort @ NotEdible der verbraucht zu viel Speicher in vielen Fällen als die HashMap Konstruktor sich mit den Fragen befasst, dass sie die Karten Array wollen eine Größe haben, die eine Potenz von 2 ist.

In der Guave Bibliotheken von Google gibt es eine Funktion das schafft eine HashMap für eine erwartete Anzahl der Elemente optimiert: newHashMapWithExpectedSize

aus der Dokumentation:

  

Erstellt ein HashMap Beispiel mit einer ausreichend hohen „Anfangskapazität“, dass es expectedSize Elemente ohne Wachstum halten sollte ...

Es ist auch bemerkenswert, dass auf der kleinen Seite eine HashMap mit Hash-Kollisionen wahrscheinlicher macht, die Lookup verlangsamen kann. Wenn Sie also wirklich um die Geschwindigkeit der Karte kümmern und weniger um seine Größe, könnte es wert sein macht es ein bisschen zu groß für die Daten benötigt, um es zu halten. Da der Speicher billig ist, initialisiere ich normalerweise HashMaps für eine bekannte Anzahl von Elementen mit

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

Sie können ferner in der Tat anderer Meinung zu sein, würde ich ganz gerne diese Idee überprüft haben, oder hinausgeworfen.

Die Antwort, die Yuval gegeben hat, ist nur für Hashtable richtig.HashMap verwendet Zweierpotenz-Buckets, daher ist Zarkonnen für HashMap tatsächlich richtig.Sie können dies anhand des Quellcodes überprüfen:

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

Obwohl der Ladefaktor von 0,75f zwischen Hashtable und HashMap immer noch derselbe ist, sollten Sie eine Anfangskapazität von n*2 verwenden, wobei n die Anzahl der Elemente ist, die Sie in der HashMap speichern möchten.Dadurch werden die schnellsten Get/Put-Geschwindigkeiten gewährleistet.

  

In einer Arraylist, die effiziente Anzahl N (N übernimmt bereits Zukunft wachsen).

Erm, nein es nicht, es sei denn, ich falsch verstehen, was Sie sagen hier. Wenn Sie eine ganze Zahl in die Arraylist Konstruktor übergeben, wird es eine zugrunde liegende Array von genau dieser Größe erstellen. Stellt sich heraus, Sie brauchen auch nur ein einziges zusätzliches Element, das Arraylist müssen die zugrunde liegende Array, um die Größe beim nächsten Anruf add (), so dass dieser Aufruf viel länger dauern, als es normalerweise tun würde.

Wenn auf der anderen Seite Sie sprechen Ihren Wert von N unter Berücksichtigung Wachstum - dann ja, wenn Sie den Wert nie über dieses dann Aufruf einer solchen Arraylist-Konstruktor gehen wird, ist angemessen garantieren. Und in diesem Fall, wie von Hank wies darauf hin, die analoge Konstruktor für eine Karte würde N und 1.0f sein. Dies sollte durchführen vernünftig, auch wenn Sie geschehen, N zu überschreiten (obwohl, wenn Sie erwarten, dass dies in regelmäßigen Abständen auftreten, können Sie in einer größeren Zahl für die Anfangsgröße übergeben möchten).

Der Ladefaktor, falls Sie sich nicht bewusst waren, ist der Punkt, an dem die Karte wird die Kapazität erhöht haben, als einen Bruchteil der Gesamtkapazität.

Bearbeiten : Yuval ist wahrscheinlich richtig, dass es eine bessere Idee ist der Ladefaktor um 0,75 für einen allgemeinen Zweck Karte zu verlassen. Ein Belastungsfaktor von 1,0 würde brillantes, wenn Sie Ihre Schlüssel sequenziellen Hashcodes hatte (wie sequentielle Integer-Schlüssel), aber für etwas anderes werden Sie wahrscheinlich laufen in Kollisionen mit den Hash-Buckets, was bedeutet, dass Lookups für einige Elemente länger dauern. Die Schaffung von mehr Eimern als unbedingt erforderlich ist, wird diese Chance einer Kollision zu verringern, was bedeutet, es in ihrem eigenen Eimer sind mehr Chance von Elementen ist und damit abrufbare in kürzester Zeit. Da die docs sagen, dies ist eine Zeit vs Raum Kompromiss. Wenn entweder Sie besonders wichtig ist (! Wie als vorzeitig Optimierung durch einen Profiler eher gezeigt) können Sie das betonen; andernfalls bleibt mit dem Standard.

Code HashMap Quelle Bezug helfen.

Wenn die Anzahl der Einträge erreicht Schwelle (Kapazität * Ladefaktor) wird Wiederkäuen automatisch. Das bedeutet, dass zu kleinem Ladefaktor häufig Wiederkäuen entstehen kann als Einträge wachsen.

Es ist sicher in den meisten Fällen von List und Map Initialisierung die List oder Map mit der folgenden Größen params zu machen.

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

Dies folgt die .75 Regel sowie ein wenig Overhead über die speichert * 2 oben beschriebener Vorgang.

Für sehr große HashMaps in kritischen Systemen, bei denen die Anfangskapazität vertun kann sehr problematisch sein, können Sie empirische Informationen benötigen, um zu bestimmen, wie am besten Ihre Karte zu initialisieren.

CollectionSpy ( collectionspy.com ) sind ein neuer Java-Profiler, die Sie im Handumdrehen sehen können die HashMaps sind in der Nähe Wiederkäuen benötigen, wie oft sie in der Vergangenheit wieder aufgewärmt wurden, und vieles mehr. Ein ideales Werkzeug sicher Anfangskapazität Argumente kapazitätsbasierten Container Konstrukteuren zu bestimmen.

Answer 3

Ich lief einige Unit-Tests um zu sehen, ob diese Antworten richtig waren und es stellte sich heraus, dass die Verwendung:

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

als die Anfangskapazität gibt, was Sie wollen entweder eine HashMap oder Hashtable. Mit „was Sie wollen“ meine ich, dass requiredCapacity Elemente auf der Karte hinzugefügt wird das Array nicht dazu führen, die es Einwickeln, um die Größe und das Array wird nicht größer sein als erforderlich. Da die Standardladekapazität beträgt 0,75, eine HashMap Initialisierung wie so funktioniert:

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

Da ein HashSet ist effektiv nur ein Wrapper für eine HashMap, auch die gleiche Logik gilt es, das heißt Sie ein HashSet effizient wie dieses Konstrukt kann:

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

@Yuval Adams Antwort ist richtig für alle Fälle außer wo (requiredCapacity / 0.75) eine Potenz von 2, in diesem Fall ist es zu viel Speicher reserviert.
Antwort @ NotEdible der verbraucht zu viel Speicher in vielen Fällen als die HashMap Konstruktor sich mit den Fragen befasst, dass sie die Karten Array wollen eine Größe haben, die eine Potenz von 2 ist.

Answer 4

In der Guave Bibliotheken von Google gibt es eine Funktion das schafft eine HashMap für eine erwartete Anzahl der Elemente optimiert: newHashMapWithExpectedSize

aus der Dokumentation:

  

Erstellt ein HashMap Beispiel mit einer ausreichend hohen „Anfangskapazität“, dass es expectedSize Elemente ohne Wachstum halten sollte ...

Answer 5

Es ist auch bemerkenswert, dass auf der kleinen Seite eine HashMap mit Hash-Kollisionen wahrscheinlicher macht, die Lookup verlangsamen kann. Wenn Sie also wirklich um die Geschwindigkeit der Karte kümmern und weniger um seine Größe, könnte es wert sein macht es ein bisschen zu groß für die Daten benötigt, um es zu halten. Da der Speicher billig ist, initialisiere ich normalerweise HashMaps für eine bekannte Anzahl von Elementen mit

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

Sie können ferner in der Tat anderer Meinung zu sein, würde ich ganz gerne diese Idee überprüft haben, oder hinausgeworfen.

Answer 6

Die Antwort, die Yuval gegeben hat, ist nur für Hashtable richtig.HashMap verwendet Zweierpotenz-Buckets, daher ist Zarkonnen für HashMap tatsächlich richtig.Sie können dies anhand des Quellcodes überprüfen:

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

Obwohl der Ladefaktor von 0,75f zwischen Hashtable und HashMap immer noch derselbe ist, sollten Sie eine Anfangskapazität von n*2 verwenden, wobei n die Anzahl der Elemente ist, die Sie in der HashMap speichern möchten.Dadurch werden die schnellsten Get/Put-Geschwindigkeiten gewährleistet.

Answer 7

  

In einer Arraylist, die effiziente Anzahl N (N übernimmt bereits Zukunft wachsen).

Erm, nein es nicht, es sei denn, ich falsch verstehen, was Sie sagen hier. Wenn Sie eine ganze Zahl in die Arraylist Konstruktor übergeben, wird es eine zugrunde liegende Array von genau dieser Größe erstellen. Stellt sich heraus, Sie brauchen auch nur ein einziges zusätzliches Element, das Arraylist müssen die zugrunde liegende Array, um die Größe beim nächsten Anruf add (), so dass dieser Aufruf viel länger dauern, als es normalerweise tun würde.

Wenn auf der anderen Seite Sie sprechen Ihren Wert von N unter Berücksichtigung Wachstum - dann ja, wenn Sie den Wert nie über dieses dann Aufruf einer solchen Arraylist-Konstruktor gehen wird, ist angemessen garantieren. Und in diesem Fall, wie von Hank wies darauf hin, die analoge Konstruktor für eine Karte würde N und 1.0f sein. Dies sollte durchführen vernünftig, auch wenn Sie geschehen, N zu überschreiten (obwohl, wenn Sie erwarten, dass dies in regelmäßigen Abständen auftreten, können Sie in einer größeren Zahl für die Anfangsgröße übergeben möchten).

Der Ladefaktor, falls Sie sich nicht bewusst waren, ist der Punkt, an dem die Karte wird die Kapazität erhöht haben, als einen Bruchteil der Gesamtkapazität.

Bearbeiten : Yuval ist wahrscheinlich richtig, dass es eine bessere Idee ist der Ladefaktor um 0,75 für einen allgemeinen Zweck Karte zu verlassen. Ein Belastungsfaktor von 1,0 würde brillantes, wenn Sie Ihre Schlüssel sequenziellen Hashcodes hatte (wie sequentielle Integer-Schlüssel), aber für etwas anderes werden Sie wahrscheinlich laufen in Kollisionen mit den Hash-Buckets, was bedeutet, dass Lookups für einige Elemente länger dauern. Die Schaffung von mehr Eimern als unbedingt erforderlich ist, wird diese Chance einer Kollision zu verringern, was bedeutet, es in ihrem eigenen Eimer sind mehr Chance von Elementen ist und damit abrufbare in kürzester Zeit. Da die docs sagen, dies ist eine Zeit vs Raum Kompromiss. Wenn entweder Sie besonders wichtig ist (! Wie als vorzeitig Optimierung durch einen Profiler eher gezeigt) können Sie das betonen; andernfalls bleibt mit dem Standard.

Answer 8

Code HashMap Quelle Bezug helfen.

Wenn die Anzahl der Einträge erreicht Schwelle (Kapazität * Ladefaktor) wird Wiederkäuen automatisch. Das bedeutet, dass zu kleinem Ladefaktor häufig Wiederkäuen entstehen kann als Einträge wachsen.

Answer 9

Es ist sicher in den meisten Fällen von List und Map Initialisierung die List oder Map mit der folgenden Größen params zu machen.

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

Dies folgt die .75 Regel sowie ein wenig Overhead über die speichert * 2 oben beschriebener Vorgang.

Answer 10

Für sehr große HashMaps in kritischen Systemen, bei denen die Anfangskapazität vertun kann sehr problematisch sein, können Sie empirische Informationen benötigen, um zu bestimmen, wie am besten Ihre Karte zu initialisieren.

CollectionSpy ( collectionspy.com ) sind ein neuer Java-Profiler, die Sie im Handumdrehen sehen können die HashMaps sind in der Nähe Wiederkäuen benötigen, wie oft sie in der Vergangenheit wieder aufgewärmt wurden, und vieles mehr. Ein ideales Werkzeug sicher Anfangskapazität Argumente kapazitätsbasierten Container Konstrukteuren zu bestimmen.