»HASHMAP -
Vorteile: Super schnelle Abfragegeschwindigkeit und Datenstrukturen, die O (1) Zeitkomplexität erreichen können, ist HashMap. Dynamische Speicherdaten mit variabler Länge (relativ zu Arrays).
Nachteile: Der Hash -Wert muss extra berechnet werden, und wenn er nicht ordnungsgemäß behandelt wird, nimmt er zusätzlichen Platz ein.
»Wie man Hashmap verwendet -
Normalerweise verwenden wir Hashmap wie folgt
Karte <Integer, String> Maps = New HashMap <Integer, String> (); Maps.put (1, "a"); Maps.put (2, "B");
Der obige Code erstellt eine neue Hashmap und fügt zwei Daten ein. Die grundlegenden Datentypen werden hier nicht akzeptiert, um K und V zu machen.
Wenn Sie dies schreiben, wird es Probleme geben:
Karte <int, double> maps = new HashMap <int, double> ();
Warum benutzen wir so? Bitte beachten Sie den Quellcode:
öffentliche Klasse Hashmap <K, V> erweitert AbstractMap <K, V> implementiert MAP <K, V>, klonbar, serialisierbar
Dies ist die Definition der HashMap -Implementierungsklasse.
—HasMap ist eine dynamisch variable Datenstruktur-Datenstruktur-
Bei der Verwendung von HashMap stellen wir häufig die HashMap -Initialisierungskapazität fest:
Karte <String, String> rm = new Hashmap <String, String> (2)
Oder verwenden Sie die Werkzeugklassenkarten von Guava, um einfach eine Sammlung zu erstellen und den Wert mit der entsprechenden Größe zu initialisieren.
MAP <String, Object> map = Maps.NewHasMapWitHExpectSize (7);
Warum also so so verwenden? Schauen wir uns ihren Quellkonstruktor an.
Konstruktor ohne Parameter:
public HashMap () {this.loadfactor = default_load_factor; threshold = (int) (default_initial_capacity * default_load_factor); Tabelle = neuer Eintrag [default_initial_capacity]; init (); } public hashmap () {
this.loadfactor = default_load_factor;
threshold = (int) (default_initial_capacity * default_load_factor);
Tabelle = neuer Eintrag [default_initial_capacity];
init ();
}
/** * konstruiert eine leere <tt> Hashmap </tt> mit der angegebenen Anfangsfähigkeit * und dem Standardlastfaktor (0,75). * * @param initialCapacity die anfängliche Kapazität. * @throws illegalArgumentException Wenn die anfängliche Kapazität negativ ist. */ public HashMap (int initialCapacity) {this (initialCapacity, default_load_factor); }Erläuterung von Substantiven:
Default_load_factor // Standard -Ladefaktor, 0,75, falls nicht angegeben. Default_initial_capacity // Standard -Initialisierungskapazität, Standard ist 16 Schwellenwert // Der Wert des Schwellenwerts (Yu) wird basierend auf dem Lastfaktor und der Initialisierungskapazität berechnet. <span style = "color: rgb (54, 46, 43); Schriftfamilie:" Microsoft Yahei ";"> Schwellenwert bedeutet, dass die Größe der Größenoperation durchgeführt wird, wenn die Größe von Hashmap größer als der Schwellenwert ist.
Wir wissen also, dass wir, wenn wir den parameterlosen Konstruktor aufrufen, ein Array von 16 Kapazitäten erhalten.
Die Frage ist also: Was ist, wenn die anfängliche Kapazität nicht ausreicht?
Arrays sind feste Länge, wie Daten mit fester Länge verwendet werden, um Daten unsicherer Länge darzustellen? Die Antwort ist, eine längere zu finden, die die Effizienz bei der Größenänderung verringert. Wir empfehlen daher, beim Initialisieren eine zuverlässige Kapazität zuverlässig zu erhalten.
»HASHMAP -Put -Methode -
public v put (k key, v value) {if (key == null) // Wenn der Schlüssel leer ist, gibt ein Unterschied zwischen HashMap und Hashtable Putfornullkey (Wert) zurück; int hash = hash (key.hashcode ()); // den Hash -Wert basierend auf dem HashCode des Schlüssels int i = indexFor (Hash, Tabelle.length) rahmen; // Rahmen Sie das Array -Index ein, das auf dem Hash -Wert für (Eintrag <k, v> e = table [i]; e! = Null; e = E.Next) {// das gesamte für die Schleife implementiert wird, dass k existiert, ein V -Objekt k; if (e.hash == Hash && ((k = E.Key) == Key || key.equals (k))) {v oldValue = e.Value; E. value = Wert; E. recordaccess (this); kehren Sie OldValue zurück; }} modCount ++; // Counter AddEntry (Hash, Schlüssel, Wert, i); // zu Array return null hinzufügen; }Wenn die eingefügten Daten die vorhandene Kapazität überschreiten, wird sie ausgeführt
AddEntry (Hash, Schlüssel, Wert, i);
void addentry (int Hash, K -Schlüssel, V -Wert, int bucketIndex) {Eintrag <k, v> e = table [bucketIndex]; Tabelle [bucketIndex] = neuer Eintrag <k, v> (Hash, Schlüssel, Wert, e); if (Größe ++> = Schwelle) <span style = "color:#ff0000;"> <strong> Größe (2 * table.Length);};};Wenn die aktuelle Größe ++> Schwellenwert angezeigt wird, wird die aktuelle Größe zweimal erweitert und die Größe (2*Tabelle.Length) ausgeführt. Wie erweitern sie sich?
void -Größe (int NewCapacity) {Eintrag [] oldTable = Tabelle; int oldCapacity = oldTable.length; if (oldcapacity == maximum_capacity) {threshold = integer.max_value; zurückkehren; } Eintrag [] newtable = neuer Eintrag [NewCapacity]; <span style = "color: rgb (51, 51, 51); Schriftfamilie: Arial;"> Neu Ein neues Array, </span> <strong> <span style = "color:#ff0000;"> Transfer (newtable); shreshold = (int) (newCapacity * loadFactor); // die Kapazität neu berechnen}Wie wird die Übertragung des Transferarrays übertragen?
void Transfer (Eintrag [] newtable) {Eintrag [] Src = Tabelle; int newcapacity = newtable.length; für (int j = 0; j <src.length; j ++) {Eintrag <k, v> e = src [j]; if (e! = null) {src [j] = null; do {Eintrag <k, v> next = e.Next; int i = <strong> <span style = "color:#ff0000;"> indexfor (e.hash, newCapacity); // den Index basierend auf der Hash -Wertkapazität </span> </strong> e.Next = newtable [i] neu berechnen; newtable [i] = e; E = Weiter; } while (e! = null); }}}»Die Anzahl der zusätzlichen Hinrichtungen der Hashmap-Erweiterung-
Wenn wir also eine Hashmap mit 1000 Elementen hinzufügen möchten, wie viele zusätzliche Berechnungen müssen ich berechnen, wenn wir den Standardwert verwenden?
Wenn es größer als 16*0,75 = 12 ist, muss es 12 Mal neu berechnet werden
Wenn es größer als 16*2*0,75 = 24 ist, sind weitere 24 Berechnungen erforderlich.
...
Wenn es größer als 16*N*0,75 = 768 ist, sind weitere 768 Berechnungen erforderlich.
Also haben wir 12+24+48+…+768 -mal im Expansionsprozess berechnet
Daher wird dringend empfohlen, die Anfangsgröße manuell anzugeben, wenn wir den Umfang des Projekts wie folgt kennen:
Karte <Integer, String> Maps = New HashMap <Integer, String> (1000);
Zusammenfassung: Aus diesem Grund wird die Ausführungseffizienz von HashMap stark reduziert, wenn sie die Anfangskapazität während der Verwendung überschreitet.
In diesem Artikel geht es um die Verwendung von HashMap in diesem Artikel über die Analyse von Java -Quellcode. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!