Von JavaDoc von HashMap:Warum würde ein höherer Ladefaktor in HashMap die Suchkosten erhöhen?
In der Regel bietet der Standardladefaktor (.75) einen guten Kompromiss zwischen Zeit und Raum Kosten. Höhere Werte verringern den Overhead für den Speicherplatz , erhöhen jedoch die Suchkosten (die in den meisten -Operationen der Klasse HashMap enthalten sind, einschließlich get und put).
Wenn wir einen höheren Wert haben, warum würde es die Suchkosten erhöhen?
der Hash-Tabelle Load Factor als
n/s definiert ist, das Verhältnis der Anzahl der gespeicherten Einträge n und der Größe s der Reihe von Eimern der Tabelle.
Hohe Leistung der Hash-Tabelle wird beibehalten, wenn die Anzahl der Kollisionen niedrig ist. Wenn der Lastfaktor hoch ist, steigt die Wahrscheinlichkeit von Kollisionen.
Ich dachte, es ist s/n und damit die Verwirrung. Siehe meinen Kommentar zu Paul Tomblin. Danke, dass du meine Zweifel beseitigt hast. – Geek
Es hat damit zu tun, wie eine HashTable unter der Haube implementiert wird, verwendet Hash-Codes und da der Algorithmus zur Berechnung Hash-Code nicht perfekt ist, können Sie einige Kollisionen haben, erhöhen Sie den Lastfaktor erhöhen die Wahrscheinlichkeit von Kollisionen und folglich die Nachschlag Leistung reduzieren ...
Standardlastfaktor (0,75).
If declare load factor as
1 the restructuring process only happens when number of elements are exceeding the capacity of the HashMap.
Hier sollten wir zuerst verstehen, was Kapazität und Ladefaktor bedeuten:
Kapazität: Dies ist die Anzahl der Schaufeln in jeder Hash-Tabelle zu einem bestimmten Zeitpunkt.
Belastungsfaktor: Der Lastfaktor ist ein Maß dafür, wie voll die Hash-Tabelle erhalten darf, bevor seine Kapazität
erhöht wird automatisch so mehr der Lastfaktor ist mehr besetzt ist, erhöht eine Hash-Tabelle, bevor die Kapazität bekommen könnte .
Der Belastungsfaktor 0,75 auf diese Weise kann die Formel (n/s unter Verwendung interpretiert werden, das Verhältnis der Anzahl der gespeicherten Einträge n und s die Größe des Arrays von Eimern der Tabelle.):
Angenommen, Sie haben 75 Werte, die Sie in Hash-Tabelle speichern müssen und Sie haben 100 leere Array-Blöcke, in denen sie gespeichert werden, hier wird die Wahrscheinlichkeit einer Kollision minimiert und der Ladefaktor beträgt 0,75.
Angenommen, Sie haben 75 Werte zu speichern und nur 10 leere Array-Blöcke (Auslastung Faktor 7,5) bedeutet dies, dass Sie Kollision haben und Kollisionslösung Techniken verwenden, die Ihre Suchzeit erhöhen wird.
Jetzt anders als Sie haben 75 Einträge und 1000 leere Array-Blöcke (Ladefaktor 0,075) Dies wird zu einer Menge leere Blöcke führen, die viel Platzverschwendung ist.
Daher ist die Daumenregel, wie der Wert des Ladefaktors wächst Ihre Suchzeit wird zunehmen, und wenn es nahe 0 geht, wird mehr Speicherplatz verschwendet.
Daher ist es eine Raumzeit tradeof.
Weitere Hash-Kollisionen. –
@PaulTomblin ist Ladefaktor = Bucket Größe/Anzahl der Tasten? Wenn dies der Fall ist, sollten die Kollisionen reduziert werden, da ein ansteigender Lastfaktor eine Erhöhung der Zahl in dem Zähler bedeutet, vorausgesetzt, dass die Anzahl der Schlüssel konstant bleibt. – Geek
prüfen diese [http://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap][1] [1]: http://stackoverflow.com/questions/10901752/what-is-the-significance-of-load-factor-in-hashmap – user1613360