Welche Bedeutung hat der Lastfaktor in HashMap?

HashMaphat zwei wichtige Eigenschaften: sizeund load factor. Ich habe die Java-Dokumentation durchgesehen und es heißt0.75f ist der anfängliche Ladefaktor. Aber ich kann die tatsächliche Verwendung nicht finden.

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

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 Auslastungsfaktor. 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 Auslastungsfaktor 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 dem Auslastungsfaktor und der aktuellen Kapazität überschreitet, wird die Hash-Tabelle erneut aufbereitet (dh interne Datenstrukturen werden neu erstellt), sodass die Hash-Tabelle ungefähr doppelt so viele 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 (was sich in den meisten Operationen der HashMap-Klasse widerspiegelt, einschließlich get und put). Die erwartete Anzahl von Einträgen in der Karte und ihr Auslastungsfaktor sollten bei der Einstellung der Anfangskapazität berücksichtigt werden, um die Anzahl der Wiederaufbereitungsvorgänge zu minimieren. Wenn die anfängliche Kapazität größer ist als die maximale Anzahl von Einträgen geteilt durch den Lastfaktor, werden niemals Wiederaufbereitungsvorgänge durchgeführt.

Wie bei allen Leistungsoptimierungen ist es eine gute Idee, eine vorzeitige Optimierung zu vermeiden (dh ohne harte Daten darüber, wo die Engpässe liegen).

Die Standard-Anfangskapazität der HashMapTakes beträgt 16 und der Lastfaktor 0,75 f (dh 75% der aktuellen Kartengröße). Der Lastfaktor gibt an, auf welcher Ebene die HashMapKapazität 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 die HashMapKapazität 32 beträgt.

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

Beweis:

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

Lassen Sie uns die Größe und n die Anzahl der hinzugefügten Schlüssel darstellen. Unter Verwendung des Binomialsatzes ist die Wahrscheinlichkeit, dass ein Eimer 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 so ist, dass P (0) = 0,5 ist, nähert sich n / s schnell log (2):

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

Was ist der Lastfaktor?

Wie viel Kapazität muss erschöpft sein, damit die HashMap ihre Kapazität erhöht?

Warum Lastfaktor?

Der Auslastungsfaktor beträgt standardmäßig 0,75 der ursprünglichen Kapazität (16), daher sind 25% der Buckets frei, bevor die Kapazität erhöht wird. Dadurch werden viele neue Buckets mit neuen Hashcodes angezeigt, die darauf hinweisen, dass sie unmittelbar nach der Erhöhung der Kapazität vorhanden sind Anzahl der Eimer.

Warum sollten Sie nun viele freie Eimer behalten und wie wirkt sich das Halten von freien Eimern auf die Leistung aus?

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

Angenommen, Sie fügen Ihrer Hashmap ein Objekt x hinzu, dessen Hashcode 888 ist. In Ihrer Hashmap ist der Bucket, der den Hashcode darstellt, frei, sodass das Objekt x zum Bucket hinzugefügt wird. Sagen Sie jetzt erneut, ob Sie ein anderes Objekt y hinzufügen, dessen Hashcode lautet Auch 888, dann wird Ihr Objekt y mit Sicherheit hinzugefügt, ABER am Ende des Buckets ( da die Buckets nichts anderes als die LinkedList-Implementierung sind, in der Schlüssel, Wert und Weiter gespeichert werden ). Dies hat nun Auswirkungen auf die Leistung! Da Ihr Objekt y bei einer Suche nicht mehr im Kopf des Eimers vorhanden ist, beträgt die benötigte Zeit nicht O (1).Diesmal hängt es davon ab, wie viele Artikel sich im selben Eimer befinden. Dies wird übrigens als Hash-Kollision bezeichnet und geschieht sogar, wenn Ihr Ladefaktor weniger als 1 beträgt.

Korrelation zwischen Leistung, Hash-Kollision und Ladefaktor?

Niedrigerer Auslastungsfaktor = mehr freie Schaufeln = weniger Kollisionsgefahr = hohe Leistung = hoher Platzbedarf.

Korrigieren Sie mich, wenn ich irgendwo falsch liege.

Aus der Dokumentation :

Der Auslastungsfaktor 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 Lastfaktors.

Für HashMap DEFAULT_INITIAL_CAPACITY = 16 und DEFAULT_LOAD_FACTOR = 0.75f bedeutet dies, dass die maximale Anzahl aller Einträge in der HashMap = 16 * 0.75 = 12 ist . Wenn das dreizehnte Element hinzugefügt wird, wird die Kapazität (Arraygröße) von HashMap verdoppelt! Perfekte Illustration beantwortete diese Frage: Das Bild stammt von hier:

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

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

eine sehr lange verknüpfte Liste.

Und das ist eine Art Niederlage.

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

Katze.

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

Nummer 1 und

Ich muss nichts anderes als Otter und anschauen

Koala.

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

Sehen Sie vielleicht, wohin das führt.

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

größer, dann muss ich im Grunde alles durchsehen

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 mit jedem 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."

Dort erkennt das HashSet, dass die Eimer bekommen

zu voll.

Es verliert diesen Vorteil dieser Suche

Elemente.

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

Legen Sie dann die Elemente in den richtigen Eimer.

Hier ist unsere grundlegende HashSet-Implementierung mit separaten

Verkettung. Jetzt werde ich ein "HashSet mit Größenänderung" erstellen.

Dieses HashSet wird erkennen, dass die Eimer sind

zu voll werden und

es braucht mehr Eimer.

loadFactor ist ein weiteres Feld in unserer HashSet-Klasse.

loadFactor repräsentiert die durchschnittliche Anzahl von Elementen pro

Eimer,

über dem wir die Größe ändern möchten.

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 Zeit sparen, wenn die Eimer a sind

etwas leerer.

Sehen 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

Zu diesem Zeitpunkt habe ich beschlossen, dass der loadFactor, der

Schwelle,

Die durchschnittliche Anzahl von Elementen pro Eimer, für die ich in Ordnung bin

mit ist 0,75.

Die Anzahl der Eimer beträgt buckets.length (6) und

Zu diesem Zeitpunkt hat unser HashSet vier Elemente, also die

aktuelle Größe ist 4.

Wir werden die Größe unseres HashSets ändern, dh wir werden weitere Buckets hinzufügen.

wenn die durchschnittliche Anzahl von Elementen pro Bucket überschreitet

der loadFactor.

In diesem Fall wird die aktuelle Größe durch Buckets geteilt

größer als loadFactor.

Zu diesem Zeitpunkt die durchschnittliche Anzahl von Elementen 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

in Ordnung.

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

Aber jetzt nehmen wir an, 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 landen.

Zu diesem Zeitpunkt beträgt die aktuelle Größe 5.

Und jetzt die durchschnittliche Anzahl von Elementen pro Eimer

ist die aktuelle Größe geteilt durch buckets.length.

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

Und dies übersteigt den loadFactor von 0,75.

Um dieses Problem anzugehen, um das zu machen

Eimer vielleicht ein wenig

leerer, so dass Operationen wie das Bestimmen, ob a

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 HashSet erfolgt in zwei Schritten.

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

Jetzt werde ich 12 Eimer haben.

Beachten Sie hier, dass der loadFactor, den ich auf 0,75 gesetzt habe, gleich bleibt.

Aber die Anzahl der geänderten Eimer beträgt 12,

Die Anzahl der Elemente blieb gleich, beträgt 5.

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

Ladefaktor,

Also sind wir jetzt in Ordnung.

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

der falsche Eimer jetzt.

Zum Beispiel Elefant.

Elefant war in Eimer Nummer 2, weil die Nummer von

Zeichen in Elefant

war 8.

Wir haben 6 Eimer, 8 minus 6 ist 2.

Deshalb landete es auf Platz 2.

Aber jetzt, wo 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?

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

Woodchuck landete in Eimer Nummer 3.

Weil 9 mod 6 3 ist.

Aber jetzt machen wir 9 Mod 12.

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

Und Sie sehen den Vorteil von all dem.

Jetzt hat Eimer Nummer 3 nur noch 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 der gleiche,

Wir werden immer noch feststellen, ob es das enthält

Wert bereits.

Wenn dies nicht der Fall ist, werden wir herausfinden, welcher Eimer es ist

sollte in und gehen

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

Jetzt erhöhen wir das Feld currentSize.

currentSize war das Feld, in dem die Nummer verfolgt wurde

von Elementen in unserem HashSet.

Wir werden es erhöhen und dann schauen

bei der durchschnittlichen Belastung,

die durchschnittliche Anzahl von Elementen 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 zum Beispiel dieses HashSet erstellt habe

der loadFactor.

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

Das bedeutet, dass zu viele Elemente pro Eimer vorhanden sind

Durchschnitt, und ich muss wieder einfügen.

Hier ist unsere Implementierung der Methode zum erneuten Einfügen

alle Elemente.

Zuerst erstelle ich eine lokale Variable namens oldBuckets.

Das bezieht sich auf die Eimer, wie sie derzeit stehen

bevor ich anfange, die Größe zu ändern.

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

Ich benenne Eimer nur in oldBuckets um.

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

um jetzt ein neues Array zu erstellen

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

wie beim ersten Mal.

Jetzt muss ich das Wiedereinsetzen tatsächlich durchführen,

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 darin bekommen

Eimer.

Und jetzt werde ich es wieder in die newBuckets einfügen.

Ich werde seinen Hashcode bekommen.

Ich werde herausfinden, um welchen Index es sich handelt.

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

Saiten und

Ich werde es diesem neuen Eimer hinzufügen.

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

Listen oder Eimer.

Ein sich selbst änderndes HashSet kann mit einem bestimmten Verhältnis oder realisieren

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