HashMap ist eine Kartenschnittstellen -Implementierung, die auf Hash -Tabellen basiert und alle optionalen Zuordnungsvorgänge bereitstellt und Nullwerte und Nullkonstruktion, außerhalb der Synchronisation und keine Garantie für die Kartierung der Reihenfolge ermöglicht. Lassen Sie uns das Implementierungsprinzip von HashMap aufzeichnen.
HashMap Interner Speicher
In HashMap werden alle Schlüsselwertpaarbeziehungen gespeichert, indem eine Reihe von Instantane-Variablen-Tabellen (auch als Bucket bezeichnet) aufrechterhalten wird. Der Eimer ist eine Reihe von Eingangsobjekten. Die Eimergröße kann bei Bedarf geändert werden, und die Länge muss eine Leistung von 2 sein. Der folgende Code:
/ *** Ein leeres Eintrags -Array, der Standardwert des Bucket*/ static endgültige Eintrag <?,?> [] Leere_table = {}; / *** Bucket, die Größe bei Bedarf ändern, muss aber eine Leistung von 2*/ transienten Eintrag <k, v> [] table = (Eintrag <k, v> []) leer_table;Anfangskapazität und Lastfaktor
HashMap verfügt über zwei Parameter, die die Leistung, die anfängliche Kapazität und den Lastfaktor beeinflussen. Die Kapazität ist die Anzahl der Eimer in der Hash -Tabelle, die anfängliche Kapazität ist nur die Kapazität der Hash -Tabelle, wenn sie erstellt wird, und der Lastfaktor ist eine Skala, in der die Hash -Tabelle vor der automatischen Erhöhung der Kapazität erreichen kann. Wenn die Anzahl der Einträge in der Hash -Tabelle das Produkt des Lastfaktors und die aktuelle Kapazität überschreitet, muss die Hash -Tabelle aufgeweckt werden (d. H. Die interne Datenstruktur wieder aufbauen), und die Rekonstruktion wird mit der doppelten Anzahl der aktuellen Kapazität erstellt. Die anfängliche Kapazität und der Lastfaktor können durch den Konstruktor eingestellt werden. Die Standardkapazität beträgt 16 Einträge, die maximale Kapazität 2^30 Einträge und der Standardlastfaktor 0,75
Ein Eimer ist wie ein Eimer, der Wasser speichert. Seine Standard -Anfangsspeicherkapazität beträgt 16 Einheiten Wasser. Wenn das Wasser auf 16*0,75 gegossen wird, wird die Kapazität zunächst auf 32 Einheiten erweitert, wenn die Daten beim nächsten Mal hinzugefügt werden. 0,75 ist der Lastfaktor, und die anfängliche Kapazität und der Lastfaktor können beim Erstellen eines Eimers festgelegt werden. Die maximale Kapazität eines Eimers beträgt 2 Einheiten Wasser bis zur Leistung von 30. Wenn die Anzahl der anfänglichen Kapazitätseinstellungen größer als die maximale Kapazität ist, muss die maximale Kapazität bestehen. Bei der Erweiterung wird es direkt zurückgegeben, wenn es größer oder gleich der maximalen Kapazität ist.
Das Folgende ist Teil des Quellcode von HashMap, der die Standardkapazität, den Lastfaktor und einige andere Konstanten definiert:
/ ** * Die standardmäßige Anfangskapazität muss die Leistung von 2. */ static Final Int default_initial_capacity = 1 << 4; // aka 16/ *** Maximale Kapazität, wenn die anfängliche Kapazität größer als die maximale Kapazität durch den Konstruktorparameter ist, wird die Kapazität auch als Anfangskapazität verwendet. / *** Der Standardlastfaktor kann durch den Konstruktor angegeben werden / *** Eine leere Array -Tabelle, wenn der Eimer nicht initialisiert wird / *** Bucket, speichert alle Schlüsselwertepaareinträge und kann bei Bedarf geändert werden, und die Länge muss eine Leistung von 2*/ transienten Eintrag <k, v> [] table = (Eintrag <k, v> []) leer_table; /*** Die Anzahl der Schlüsselwertpaare in der Karte beträgt die Größe +1 oder -1 jedes Mal, wenn sie hinzugefügt oder gelöscht wird. */ transiente int Größe; /** * Der kritische Wert des Lastwerts, der geändert werden muss, ist: (Kapazität * Lastfaktor). Nach jeder Größe wird die neue Kapazität mit der neuen Kapazität berechnet. * @serial */ // if table == leer_table dann ist dies die anfängliche Kapazität, bei der die // Tabelle beim Aufblasen erzeugt wird. int Schwelle; / ** * Lastfaktor, falls im Konstruktor angegeben, wird der Standardlastfaktor verwendet, * * @serial */ Final Float loadFactor; /** * Häufigkeit von HashMap -Strukturmodifikationen, ändern Sie die Anzahl der Karten in der HashMap oder ändern Sie die interne Struktur, wenn die Struktur geändert wird (z. B. die * Rehash -Methode * Rehash -Methode, die interne Datenstruktur wieder aufbauen). Dieses Feld wird in * Die Iteratoren verwendet, die auf der HashMap -Sammlungsansicht erzeugt werden, werden in schnell fehlgeschlagene */transiente int modcount verarbeitet.
Erstkapazitäts- und Lastfaktor -Leistungsanpassung
In der Regel sucht der Standardlastfaktor (0,75) einen Kompromiss in Zeit- und Raumkosten. Obwohl der Lastfaktor zu hoch ist, erhöht er auch die Abfragekosten (dies spiegelt sich in den meisten HashMap -Operationen wider, einschließlich Get and Put Operations). Bei der Festlegung der anfänglichen Kapazität sollte die Anzahl der auf der Karte und dessen Lastfaktors erforderlichen Einträge berücksichtigt werden, um die Anzahl der Rehash -Vorgänge zu minimieren. Wenn die anfängliche Kapazität größer ist als die maximale Anzahl von Einträgen geteilt durch den Lastfaktor, tritt der Rehash -Betrieb nicht auf.
Wenn viele Zuordnungsbeziehungen in einer HashMap -Instanz gespeichert werden sollen, wird die Erstellung einer ausreichend ausreichend ausreichend ausreichend ausreichenden Kapazität die Zuordnungsbeziehung in Bezug auf die Durchführung automatischer Rehash -Vorgänge bei Bedarf effizienter gespeichert, um die Kapazität der Tabelle zu erhöhen.
Im Folgenden ist der Code zum Wiederaufbau der HashMap -Datenstruktur:
void -Größe (int NewCapacity) {Eintrag [] oldTable = Tabelle; int oldCapacity = oldTable.length; if (OldCapacity == Maximum_Capacity) {// Wenn die Kapazität die maximale Grenze erreicht hat, setzen Sie den Lastwert und kehren Sie direkt in den Schwellenwert = Integer.max_value zurück; zurückkehren; } // Erstellen Sie eine neue Tabelle, um die Dateneingabe zu speichern [] newtable = new Entry [NewCapacity]; // Die Daten aus der alten Tabelle in die neue Tabelle übertragen, dauert dieser Schritt viel Zeit, um zu übertragen (newtable, inithashSeedasNeed (Newcapacity)); Tabelle = newtable; // Setzen Sie schließlich den Lastwert der nächsten Größe der Größe des Schwellenwerts = (int) math.min (NewCapacity * LoadFactor, Maximum_Capacity + 1);};};Hashmap -Konstruktionsmethode
Die vierte Baumethode besteht darin, eine neue HashMap mit einer vorhandenen Karte zu erstellen. Reden wir später darüber. Tatsächlich werden die ersten drei Baumethoden in der letzten dritten Methode mit zwei Parametern aufgerufen. Wenn keine Parameter übergeben werden, wird der Standardwert verwendet. Der Code ist wie folgt:
/** * konstruiert eine leere <tt> Hashmap </tt> mit der Standard -Anfangskapazität * (16) und dem Standardlastfaktor (0,75). */ public hashmap () {this (default_initial_capacity, default_load_factor); } /** * 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); } /** * konstruiert ein leeres <tt> Hashmap < /tt> mit der angegebenen Anfangsfähigkeit und Lastfaktor. * * @param initialCapacity Die anfängliche Kapazität * @param loadfactor Der Lastfaktor * @Throws illegalArgumentException Wenn die anfängliche Kapazität negativ ist if (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity; if (loadFactor <= 0 || float.isnan (loadFactor)) werfen neue illegalArgumentException ("illegaler Lastfaktor:" +loadfactor); this.loadfactor = loadFactor; Schwelle = initialCapacity; init (); }Wie aus den oben genannten Erscheinen ersichtlich ist, wird im Konstruktor, wenn die anfängliche Kapazität größer als die maximale Kapazität ist, die maximale Kapazität direkt ersetzt.
Methode setzen
Schauen wir uns als nächstes die wichtigeren Teile von HashMap an
/*** In dieser Karte sind der angegebene Wert und der angegebene Build zugeordnet. Wenn die Karte zuvor eine Zuordnungsbeziehung des Schlüssels enthält, wird der alte Wert ersetzt.** @Param gibt den zu assoziierten Schlüssel an* @param gibt den zu assoziierten Wert an* @return Der mit dem Schlüssel zugeordnete alte Wert. Wenn der Schlüssel keine Zuordnungsbeziehung hat, gibt es Null zurück (zurückgegebene Null -zurück). aufblaserbar (Schwellenwert); } if (key == null) return putFornullKey (Wert); int Hash = Hash (Schlüssel); int i = indexFor (Hash, Tabelle.length); für (Eintrag <k, v> e = table [i]; e! = null; e = e.next) {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 ++; AddEntry (Hash, Schlüssel, Wert, i); null zurückkehren; }1. In der Put -Methode bestimmen Sie zunächst zuerst, ob sich der Eimer im nicht initialisierten Zustand befindet. Wenn es nicht initialisiert wird, rufen Sie die aufblätterbare Methode auf, um es zu initialisieren, und bestimmen Sie dann, ob der Parameterschlüssel null ist. Wenn es null ist, rufen Sie Putfornullkey speziell an, um die Daten mit Key als Null zu setzen. Die PutfornullKey -Methode entspricht tatsächlich der folgenden Schritt 3, außer dass der Standardspeicherort der Daten mit Schlüssel als NULL das erste ist, dh das Standard -Index von 0 beträgt.
2. Wenn der Schlüssel nicht null ist, rufen Sie die Hash () -Methode auf, um den Hash -Wert des Schlüssels zu erhalten. Sie können die Position berechnen, an der der Schlüssel basierend auf dem Hash -Wert und der Länge des Eimers in den Eimer platziert werden kann.
3. Im Eintragsobjekt befindet sich ein Attribut, das eine einseitige Liste der verknüpften Liste bilden kann, um Elemente mit demselben Hash-Wert zu speichern. Wenn der Hash -Wert des Schlüssels berechnet wird, wird auch der Speicherort wiederholt. Beurteilen Sie einfach, ob das Element des Speicherorts und die nächste Attributliste des Elements genau dem Hash -Wert des angegebenen Schlüssels und der angegebenen Schlüssel entspricht. Wenn es eine völlig konsistente gibt, bedeutet dies, dass es bereits existiert, den alten Wert ersetzen und den alten Wert direkt als Rückgabewert zurückgeben.
4. Erhöhen Sie die Anzahl der strukturellen Modifikationen um 1
5. Rufen Sie die AddEntry-Methode auf, um das neue Schlüsselwertpaar zum HashMap hinzuzufügen. Die Addentity -Methode bestimmt zunächst, ob die aktuellen Eingabedaten größer oder gleich dem Lastwert (die Kapazität des Bucket * Lastfaktors) sind und die angegebene Position des Eimers nicht null ist. Wenn es bereits größer als und die angegebene Position nicht null ist, ist die Kapazität des Einstellungsschaufels doppelt so hoch wie die Stromkapazität. Die Kapazität des einstellenden Eimers wird auf die oben genannte Anpassungsverzeichnis für die anfängliche Kapazität und das Lastfaktor -Leistungsanpassungsverzeichnis verwiesen. Berechnen Sie den Hash -Wert neu und berechnen Sie den Speicherort. Rufen Sie CreateStry -Methode an, um sie im Eimer zu speichern
void addentry (int hash, k key, v -Wert, int bucketIndex) {if ((size> = threshold) && (null! Hash = (null! = Schlüssel)? Hash (Schlüssel): 0; bucketIndex = indexFor (Hash, Tabelle.length); } createEntry (Hash, Schlüssel, Wert, BucketIndex); } void createEntry (int Hash, K -Schlüssel, V -Wert, int bucketIndex) {Eintrag <k, v> e = table [bucketIndex]; Tabelle [bucketIndex] = neuer Eintrag <> (Hash, Schlüssel, Wert, e); Größe ++; } /*** Eintragskonstruktor -Methode zum Erstellen eines neuen Eintrags. */ Eintrag (int h, k k, v v, Eintrag <k, v> n) {value = v; Weiter = n; Key = k; Hash = H; }6. Erstellen Sie zuerst den Eintrag am angegebenen Ort und generieren Sie dann einen neuen Eintrag. Speichern Sie beim Generieren des Eintrags den ursprünglichen Eintrag in die nächste Eigenschaft des neu generierten Eintrags (siehe Eintragungskonstruktion) und ersetzen Sie den Eintrag am angegebenen Ort durch das neu generierte.
Denn beim Hinzufügen neuer Einträge muss der Hash -Wert berechnet werden, und wenn die Länge nicht ausreicht, muss die Länge angepasst werden. Wenn es im berechneten Speicherortelemente Elemente gibt, muss die verknüpfte Liste gespeichert werden, sodass die Effizienz der Verwendung von HashMap zum Hinzufügen neuer Vorgänge nicht zu hoch ist.
Methode erhalten
Schauen wir uns zunächst den Quellcode der GET -Methode an:
/*** Rückgabe des von dem angegebenen Schlüssels abgebildeten Werts; Wenn diese Karte keine Zuordnungsbeziehung für diesen Schlüssel enthält, bedeutet sie NULL *, die einen Nullwert zurückgibt, nicht unbedingt bedeutet, dass die Karte nicht die Zuordnung des Schlüssels enthält, und sie kann auch die Zuordnung in Null ändern. Sie können den enthaltenden Operation verwenden, um zwischen diesen beiden Situationen zu unterscheiden. Eintrag <k, v> Eintrag = GetEntry (Schlüssel); NULL zurückgeben == Eintrag? NULL: Eintrag.getValue (); } Endeintrag <k, v> getEntry (Objektschlüssel) {if (size == 0) {return null; } int Hash = (key == null)? 0: Hash (Schlüssel); für (Eintrag <k, v> e = table [indexFor (Hash, Tabelle.Length)]; e! = null; e = E.Next) {Objekt k; if (e.hash == Hash && ((k = E.Key) == Key || (Schlüssel! = NULL && key.equals (k)))) return e; } return null;}Die GET -Methode ist einfach zu implementieren. Im Folgenden sind einige Schritte aufgeführt:
Durch die Betrachtung des Quellcode von GET können wir feststellen, dass die GET -Methode den Speicherort über den Hash -Wert des Schlüssels und die Länge des Eimers berechnet. Grundsätzlich können Sie das Element finden, das Sie suchen. Selbst wenn Sie ein paar Schlüssel mit wiederholten Hash -Werten durchqueren, ist es sehr schnell. Da der Hash -Wert relativ einzigartig ist, ist HashMap sehr schnell zum Suchen.
Benutzerdefiniertes Objekt als Schlüssel zu HashMap
Klasse Benutzer {// ID -Nummer geschützt int idNumber; public user (int id) {idnumber = id; }} public class testuser {public static void main (String [] args) {map <Benutzer, String> map = new HashMap <Benutzer, String> (); für (int i = 0; i <5; i ++) {map.put (neuer Benutzer (i), "Name:"+i); } System.out.println ("Benutzer3 Name:" + map.get (neuer Benutzer (3))); }} Ausgabe: Benutzer3 Name: NULLWie oben erwähnt, kann bei Verwendung einer benutzerdefinierten Benutzerklasseninstanz als HashMap -Objekt beim Drucken der Name von User3 nicht gefunden werden, da die Benutzerklasse automatisch das Basisklassenobjekt erbt. Daher wird die HashCode -Methode des Objekts automatisch zur Generierung eines Hash -Werts verwendet und verwendet die Adresse des Objekts, um den Hash -Wert standardmäßig zu berechnen. Daher unterscheidet sich der Hash -Wert der ersten von neuen Benutzer (3) generierten ersten Instanz vom Hash -Wert der generierten zweiten Instanz. Wenn Sie jedoch nur die HashCode -Methode überschreiben müssen, funktioniert sie nicht ordnungsgemäß, es sei denn, Sie überschreiben die Equals -Methode gleichzeitig, es ist auch Teil des Objekts. HashMap verwendet Equals (), um festzustellen, ob die Stromschlüssel mit den in der Tabelle vorhandenen Schlüssel übereinstimmt. Sie können sich auf die oben genannte Methode erhalten.
Die richtige Methode Equals () muss die folgenden 5 Bedingungen erfüllen: --- Siehe "Java -Programmiergedanken" -Seite 489
Wieder : Das Standardobjekt.equals () ist nur die Adresse des Vergleichsobjekts, sodass ein neuer Benutzer (3) einem anderen neuen Benutzer (3) nicht entspricht. Wenn Sie Ihre eigene Klasse als Schlüssel zu HashMap verwenden möchten, müssen Sie sowohl HashCode () als auch Equals () überlasten.
Der folgende Code funktioniert normal:
Klasse Benutzer {// ID -Nummer geschützt int idNumber; public user (int id) {idnumber = id; } @Override public int HashCode () {return idNumber; } @Override public boolean Equals (Object obj) {return obj Instance von Benutzer && (idnumber == ((Benutzer) obj) .Idnumber); }} public class testuser {public static void main (String [] args) {map <Benutzer, String> map = new HashMap <Benutzer, String> (); für (int i = 0; i <5; i ++) {map.put (neuer Benutzer (i), "Name:"+i); } System.out.println ("Benutzer3 Name:" + map.get (neuer Benutzer (3))); }} Ausgabe: Benutzer3 Name: Name: 3Die oben genannte gibt IDNumber einfach als einzige Diskriminierung im HashCode zurück, und Benutzer können auch ihre eigenen Methoden gemäß ihrem eigenen Unternehmen implementieren. In der Equals -Methode prüft InstanceOF leise, ob das Objekt null ist. Wenn der Parameter links von Instanz von null ist, wird FALSE zurückgegeben. Wenn der Parameter von Equals () nicht null ist und der Typ korrekt ist, basiert der Vergleich auf der tatsächlichen IDNumber in jedem Objekt. Wie aus der Ausgabe ersichtlich ist, ist die aktuelle Methode korrekt.
Siehe:
"Java -Programmiergedanken"
JDK 1.6 Chinesische Hilfehandbuch
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels für das Studium oder die Arbeit eines jeden hilfreich sein wird. Ich hoffe auch, Wulin.com mehr zu unterstützen!