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?
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).
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.
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...
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.
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.
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.
Das vollständige Verständnis des Lastfaktors und des Nachwaschens ist hier
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: 
Bild ist von hier aufgenommen:
https://javabypatel.blogspot.com/2015/10/what-is-load-factor-and-rehashing-in-hashmap.html