webentwicklung-frage-antwort-db.com.de

Welche Bedeutung hat der Lastfaktor in HashMap?

HashMap hat zwei wichtige Eigenschaften: size und load factor. Ich habe die Java Dokumentation durchgesehen und es steht 0.75f ist der anfängliche Lastfaktor. Aber ich kann die tatsächliche Verwendung nicht finden.

Kann jemand beschreiben, in welchen verschiedenen Szenarien der Auslastungsfaktor eingestellt werden muss und welche idealen Beispielwerte für verschiedene Fälle vorliegen?

211
Priyank Doshi

Die Dokumentation erklärt es ziemlich gut:

Eine Instanz von HashMap verfügt über zwei Parameter, die sich auf die Leistung auswirken: Anfangskapazität und Lastfaktor. Die Kapazität ist die Anzahl der Buckets in der Hash-Tabelle, und die Anfangskapazität ist einfach die Kapazität zum Zeitpunkt der Erstellung der Hash-Tabelle. Der Ladefaktor ist ein Maß dafür, wie voll die Hash-Tabelle werden darf, bevor ihre Kapazität automatisch erhöht wird. Wenn die Anzahl der Einträge in der Hash-Tabelle das Produkt aus Ladefaktor und aktueller Kapazität überschreitet, wird die Hash-Tabelle erneut verarbeitet (dh interne Datenstrukturen werden neu erstellt), sodass die Hash-Tabelle ungefähr die doppelte Anzahl von Buckets enthält.

In der Regel bietet der Standardlastfaktor (.75) einen guten Kompromiss zwischen Zeit- und Raumkosten. Höhere Werte verringern den Speicherplatzaufwand, erhöhen jedoch die Suchkosten (dies spiegelt sich in den meisten Operationen der HashMap-Klasse wider, einschließlich get und put). Die erwartete Anzahl von Einträgen in der Karte und ihr Auslastungsfaktor sollten beim Einstellen ihrer anfänglichen Kapazität berücksichtigt werden, um die Anzahl von Wiederaufbereitungsvorgängen zu minimieren. Wenn die anfängliche Kapazität größer ist als die maximale Anzahl von Einträgen geteilt durch den Auslastungsfaktor, werden niemals Wiederaufbereitungsvorgänge durchgeführt.

Wie bei allen Leistungsoptimierungen ist es ratsam, eine vorzeitige Optimierung zu vermeiden (d. H. Ohne genaue Angaben zu den Engpässen).

242
NPE

Die Standard-Anfangskapazität der HashMap -Aufnahme beträgt 16 und der Auslastungsfaktor 0,75f (d. H. 75% der aktuellen Kartengröße). Der Ladefaktor gibt an, auf welcher Ebene die Kapazität HashMap verdoppelt werden soll.

Zum Beispiel Produkt aus Kapazität und Lastfaktor als 16 * 0.75 = 12. Dies bedeutet, dass nach dem Speichern des 12. Schlüssel-Wert-Paares in HashMap dessen Kapazität 32 wird.

134
user2791282

Nach meinen Berechnungen liegt der "perfekte" Belastungsfaktor tatsächlich näher bei log 2 (~ 0,7). Obwohl ein geringerer Lastfaktor zu einer besseren Leistung führt. Ich denke, dass .75 wahrscheinlich aus einem Hut gezogen wurde.

Beweis:

Verkettung kann vermieden und Verzweigungsvorhersage genutzt werden, indem vorhergesagt wird, ob ein Bucket leer ist oder nicht. Ein Bucket ist wahrscheinlich leer, wenn die Wahrscheinlichkeit, dass er leer ist, 0,5 überschreitet.

Stellen wir uns die Größe und n die Anzahl der hinzugefügten Schlüssel vor. Nach dem Binomialsatz ist die Wahrscheinlichkeit, dass ein Bucket leer ist, wie folgt:

P(0) = C(n, 0) * (1/s)^0 * (1 - 1/s)^(n - 0)

Daher ist ein Eimer wahrscheinlich leer, wenn weniger als vorhanden sind

log(2)/log(s/(s - 1)) keys

Wenn s unendlich ist und die Anzahl der hinzugefügten Schlüssel P(0) = .5 ist, nähert sich n/s log (2) schnell:

lim (log(2)/log(s/(s - 1)))/s as s -> infinity = log(2) ~ 0.693...
34
HelloWorld

Was ist der Lastfaktor?

Die Menge an Kapazität, die ausgeschöpft werden soll, damit die HashMap ihre Kapazität erhöht?

Warum Auslastungsfaktor?

Der Auslastungsfaktor beträgt standardmäßig 0,75 der Anfangskapazität (16), daher sind 25% der Eimer frei, bevor die Kapazität erhöht wird. Dies führt dazu, dass viele neue Eimer mit neuen Hashcodes direkt nach der Erhöhung der Kapazität existieren Anzahl der Eimer.

Warum sollten Sie jetzt viele kostenlose Eimer behalten und wie wirkt sich das Beibehalten von kostenlosen Eimern auf die Leistung aus?

Wenn Sie den Ladefaktor auf 1,0 einstellen, kann etwas sehr Interessantes passieren.

Angenommen, Sie fügen Ihrer Hashmap ein Objekt x mit dem Hashcode 888 hinzu. In Ihrer Hashmap ist der Bucket, der den Hashcode darstellt, frei, also wird das Objekt x zum Bucket hinzugefügt, aber sagen Sie jetzt erneut, ob Sie es sind Wenn Sie ein weiteres Objekt hinzufügen, dessen hashCode ebenfalls 888 ist, wird Ihr Objekt y mit Sicherheit hinzugefügt, ABER am Ende des Buckets (da die Buckets nichts anderes als eine LinkedList-Implementierung sind, in der Schlüssel, Wert & next ​​gespeichert sind) hat einen Leistungseffekt! Da Ihr Objekt y im Kopf des Buckets nicht mehr vorhanden ist, wenn Sie eine Suche durchführen, wird die benötigte Zeit nicht O (1) sein, diesmal hängt es davon ab Wie viele Artikel befinden sich im selben Eimer? Dies wird übrigens als Hash-Kollision bezeichnet und tritt sogar dann auf, wenn Ihr Ladefaktor kleiner als 1 ist.

Korrelation zwischen Performance, Hash-Kollision & Ladefaktor?

geringerer Ladefaktor = mehr freie Schaufeln = weniger Kollisionsgefahr = hohe Leistung = hoher Platzbedarf.

Korrigiere mich, wenn ich irgendwo falsch liege.

25
Sujal Mandal

Aus der Dokumentation :

Der Ladefaktor ist ein Maß dafür, wie voll die Hash-Tabelle werden darf, bevor ihre Kapazität automatisch erhöht wird

Es hängt wirklich von Ihren speziellen Anforderungen ab, es gibt keine "Faustregel" für die Angabe eines anfänglichen Belastungsfaktors.

17
Óscar López

Wenn die Eimer zu voll werden, müssen wir durchschauen

eine sehr lange verknüpfte Liste.

Und das ist eine Art, den Punkt zu besiegen.

Hier ist ein Beispiel, in dem ich vier Eimer habe.

Ich habe bisher Elefanten und Dachs in meinem HashSet.

Das ist eine ziemlich gute Situation, oder?

Jedes Element hat null oder ein Element.

Jetzt fügen wir zwei weitere Elemente in unser HashSet ein.

     buckets      elements
      -------      -------
        0          elephant
        1          otter
         2          badger
         3           cat

Das ist auch nicht schlecht.

Jeder Eimer hat nur ein Element. Also, wenn ich wissen will, enthält das Panda?

Ich kann sehr schnell auf Eimer Nummer 1 schauen und das ist es nicht

dort und

Ich wusste, dass es nicht in unserer Sammlung ist.

Wenn ich wissen will, ob es Katze enthält, schaue ich auf Eimer

nummer 3,

Ich finde Katze, ich weiß sehr schnell, ob es in unserer ist

sammlung.

Was ist, wenn ich Koala hinzufüge, nun, das ist nicht so schlimm.

             buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala 
         2          badger
         3           cat

Vielleicht jetzt statt in Eimer Nummer 1 nur anschauen

ein Element,

Ich muss mir zwei ansehen.

Aber zumindest muss ich nicht auf Elefanten, Dachs und ... schauen

katze.

Wenn ich wieder nach Panda suche, kann es nur im Eimer sein

nummer 1 und

Ich muss nichts anderes anschauen als Otter und

koala.

Aber jetzt lege ich Alligator in Eimer Nummer 1 und du kannst

vielleicht sehen, wohin das führt.

Das, wenn Eimer Nummer 1 immer größer und größer wird

größer, dann muss ich im Grunde alle durchschauen

diese Elemente zu finden

etwas, das in Eimer Nummer 1 sein sollte.

            buckets      elements
      -------      -------
        0          elephant
        1          otter -> koala ->alligator
         2          badger
         3           cat

Wenn ich anfange, Zeichenfolgen zu anderen Buckets hinzuzufügen,

richtig, das Problem wird immer größer

einzelner Eimer.

Wie verhindern wir, dass unsere Eimer zu voll werden?

Die Lösung hier ist das

          "the HashSet can automatically

        resize the number of buckets."

Es gibt das HashSet erkennt, dass die Eimer bekommen

zu voll.

Es verliert den Vorteil dieser einmaligen Suche

elemente.

Und es werden einfach mehr Eimer erstellt (im Allgemeinen doppelt so hoch wie zuvor) und

dann legen Sie die Elemente in den richtigen Eimer.

Hier ist also unsere grundlegende HashSet-Implementierung mit separaten

verkettung. Jetzt erstelle ich ein "HashSet mit eigener Größenänderung".

Dieses HashSet wird erkennen, dass die Eimer sind

zu voll und

es braucht mehr Eimer.

loadFactor ist ein weiteres Feld in unserer HashSet-Klasse.

loadFactor repräsentiert die durchschnittliche Anzahl der Elemente pro

eimer,

oberhalb dessen wollen wir die Größe ändern.

loadFactor ist ein Gleichgewicht zwischen Raum und Zeit.

Wenn die Eimer zu voll werden, ändern wir die Größe.

Das braucht natürlich Zeit, aber

es kann uns auf der Straße Zeit sparen, wenn die Eimer a sind

etwas mehr leer.

Schauen wir uns ein Beispiel an.

Hier ist ein HashSet, wir haben bisher vier Elemente hinzugefügt.

Elefant, Hund, Katze und Fisch.

          buckets      elements
      -------      -------
        0          
        1          elephant
         2          cat ->dog
         3           fish
          4         
           5

An dieser Stelle habe ich beschlossen, dass der loadFactor die

schwelle,

die durchschnittliche Anzahl der Elemente pro Bucket, für die ich in Ordnung bin

mit, ist 0,75.

Die Anzahl der Buckets ist buckets.length (6) und

zu diesem Zeitpunkt hat unser HashSet vier Elemente, also das

aktuelle Größe ist 4.

Wir werden unsere HashSet-Größe ändern, das heißt, wir werden mehr Eimer hinzufügen,

wenn die durchschnittliche Anzahl der Elemente pro Bucket übersteigt

der loadFactor.

Dies ist der Fall, wenn die aktuelle Größe geteilt durch buckets.length ist

größer als loadFactor.

Zu diesem Zeitpunkt die durchschnittliche Anzahl der Elemente pro Bucket

ist 4 geteilt durch 6.

4 Elemente, 6 Eimer, das sind 0,67.

Das ist weniger als der von mir festgelegte Schwellenwert von 0,75, also sind wir

in Ordnung.

Wir müssen die Größe nicht ändern.

Aber jetzt sagen wir mal wir fügen Waldmurmeltier hinzu.

                  buckets      elements
      -------      -------
        0          
        1          elephant
         2        woodchuck-> cat ->dog
         3           fish
          4         
           5

Waldmurmeltier würde in Eimer Nummer 3 enden.

Zu diesem Zeitpunkt ist die aktuelle Größe 5.

Und jetzt die durchschnittliche Anzahl der Elemente pro Bucket

ist die currentSize geteilt durch buckets.length.

Das sind 5 Elemente geteilt durch 6 Eimer, das ist 0,83.

Und das übersteigt den loadFactor von 0,75.

Um dieses Problem anzugehen, um die

eimer vielleicht ein bisschen

mehr leer, so dass Operationen wie festzustellen, ob ein

eimer enthält

ein Element wird etwas weniger komplex sein, ich möchte die Größe ändern

mein HashSet.

Das Ändern der Größe des HashSets erfolgt in zwei Schritten.

Zuerst werde ich die Anzahl der Eimer verdoppeln, ich hatte 6 Eimer,

jetzt habe ich 12 Eimer.

Beachten Sie hier, dass der loadFactor, den ich auf 0.75 gesetzt habe, derselbe bleibt.

Aber die Anzahl der Eimer geändert ist 12,

die Anzahl der gleich gebliebenen Elemente beträgt 5.

5 geteilt durch 12 ist ungefähr 0,42, das liegt weit unter unserer

ladefaktor,

also sind wir jetzt in Ordnung.

Aber wir sind noch nicht fertig, weil einige dieser Elemente enthalten sind

der falsche Eimer jetzt.

Zum Beispiel Elefant.

Elefant war in Eimer Nummer 2, weil die Anzahl der

zeichen im Elefanten

war 8.

Wir haben 6 Eimer, 8 minus 6 ist 2.

Deshalb landete es auf Platz 2.

Aber jetzt, da wir 12 Eimer haben, ist 8 Mod 12 8, also

elefant gehört nicht mehr in Eimer Nummer 2.

Elefant gehört in Eimer Nummer 8.

Was ist mit Waldmurmeltier?

Woodchuck war derjenige, der dieses ganze Problem auslöste.

Waldmurmeltier landete in Eimer Nummer 3.

Weil 9 mod 6 3 ist.

Aber jetzt machen wir 9 mod 12.

9 mod 12 ist 9, Murmeltier geht zu Eimer Nummer 9.

Und Sie sehen den Vorteil von all dem.

Der Eimer Nummer 3 hat jetzt nur zwei Elemente, während er zuvor 3 hatte.

Also hier ist unser Code,

wo wir unser HashSet mit separater Verkettung hatten

hat keine Größenänderung vorgenommen.

Hier ist eine neue Implementierung, bei der wir die Größenänderung verwenden.

Der größte Teil dieses Codes ist derselbe.

wir werden noch feststellen, ob es die enthält

wert bereits.

Wenn nicht, werden wir herausfinden, welcher Eimer es ist

sollte in und gehen

fügen Sie es dann zu diesem Bucket hinzu, und fügen Sie es dieser LinkedList hinzu.

Jetzt erhöhen wir das Feld currentSize.

currentSize war das Feld, das die Nummer verfolgte

von Elementen in unserem HashSet.

Wir werden es erhöhen und dann schauen

bei der durchschnittlichen Belastung,

die durchschnittliche Anzahl der Elemente pro Bucket.

Wir werden diese Aufteilung hier unten machen.

Wir müssen hier ein bisschen Casting machen, um sicherzugehen

dass wir ein Doppel bekommen.

Und dann vergleichen wir diese durchschnittliche Belastung mit dem Feld

das habe ich als eingestellt

0,75, als ich dieses HashSet erstellte

der loadFactor.

Wenn die durchschnittliche Last größer als der loadFactor ist,

das bedeutet, dass zu viele Elemente pro Bucket vorhanden sind

durchschnitt, und ich muss wieder einsetzen.

Hier ist unsere Implementierung der Methode zum erneuten Einfügen

alle Elemente.

Zuerst erstelle ich eine lokale Variable mit dem Namen oldBuckets.

Das bezieht sich auf die Eimer, wie sie derzeit stehen

bevor ich anfange, alles in der Größe zu ändern.

Hinweis: Ich erstelle noch kein neues Array verknüpfter Listen.

Ich benenne nur Eimer in oldBuckets um.

Denken Sie jetzt daran, Eimer waren ein Feld in unserer Klasse, ich gehe

erstellen Sie jetzt ein neues Array

von verknüpften Listen, aber dies wird doppelt so viele Elemente haben

wie beim ersten mal.

Jetzt muss ich tatsächlich das Wiedereinsetzen tun,

Ich werde alle alten Eimer durchgehen.

Jedes Element in oldBuckets ist eine LinkedList von Zeichenfolgen

das ist ein Eimer.

Ich werde durch diesen Eimer gehen und jedes Element in das bekommen

eimer.

Und jetzt werde ich es wieder in die newBuckets einsetzen.

Ich werde seinen Hashcode bekommen.

Ich werde herausfinden, um welchen Index es sich handelt.

Und jetzt bekomme ich den neuen Eimer, die neue LinkedList von

streicher und

Ich werde es zu diesem neuen Eimer hinzufügen.

Zusammenfassend sind HashSets, wie wir gesehen haben, Arrays von Linked

Listen oder Eimer.

Ein HashSet, dessen Größe sich selbst ändert, kann mit einem Verhältnis oder realisiert werden

Ich würde eine Tabellengröße von n * 1,5 oder n + (n >> 1) wählen, dies würde einen Lastfaktor von .66666 ~ ohne Unterteilung ergeben, was auf den meisten Systemen langsam ist, insbesondere auf tragbaren Systemen, in denen es keine Unterteilung gibt die Hardware.

1

Das vollständige Verständnis des Lastfaktors und des Nachwaschens ist hier

0
shatakshi

Für HashMap DEFAULT_INITIAL_CAPACITY = 16 und DEFAULT_LOAD_FACTOR = 0.75f ​​ bedeutet dies, dass MAX Anzahl ALLER Einträge in der HashMap = 16 * 0,75 = 12 . Wenn das dreizehnte Element hinzugefügt wird, wird die Kapazität (Arraygröße) von HashMap verdoppelt! Perfekte Illustration beantwortet diese Frage: enter image description here Bild ist von hier aufgenommen:

https://javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html

0
provisota