HashMap ist auch eine Sammlung, die wir viel verwenden. Es handelt sich um eine Implementierung der Kartenschnittstelle basierend auf Hash-Tabellen und existiert in Form eines Schlüsselwerts. In HashMap wird der Schlüsselwert immer als Ganzes verarbeitet. Das System berechnet den Speicherort des Schlüsselwerts basierend auf dem Hash-Algorithmus. Wir können den Wert immer schnell über den Schlüssel speichern und abrufen. Lassen Sie uns den Zugriff auf HashMap analysieren.
1. Definition
HashMap implementiert die Kartenschnittstelle und erbt AbstractMap. Die Kartenschnittstelle definiert die Regeln für die Schlüsselzuordnung auf Werte, und die AbstractMap -Klasse bietet die Backbone -Implementierung der Kartenschnittstelle, um die zur Implementierung dieser Schnittstelle erforderlichen Arbeiten zu minimieren. Tatsächlich hat die AbstractMap -Klasse MAP implementiert. Ich denke, es sollte klarer sein, Map LZ hier zu markieren!
öffentliche Klasse Hashmap <K, V> erweitert AbstractMap <K, V> implementiert MAP <K, V>, klonbar, serialisierbar
2. Konstruktorfunktion
HashMap liefert drei Konstruktoren:
HashMap (): Konstruktiert eine leere HashMap mit der Standard -Anfangskapazität (16) und dem Standardlastfaktor (0,75).
HashMap (int initialCapacity): Konstruktiert einen leeren HashMap mit angegebener Anfangskapazität und Standardlastfaktor (0,75).
HashMap (intit initialCapacity, Float -Lastfaktor): Konstruktiert eine leere HashMap mit angegebener Anfangskapazität und Lastfaktor.
Hier werden zwei Parameter erwähnt: anfängliche Kapazität, Lastfaktor. Diese beiden Parameter sind wichtige Parameter, die die Leistung von HashMap beeinflussen. Die Kapazität repräsentiert die Anzahl der Eimer in der Hash -Tabelle. Die anfängliche Kapazität ist die Kapazität beim Erstellen einer Hash -Tabelle. Der Ladefaktor ist eine Skala, die die Hash -Tabelle erreichen kann, bevor die Kapazität automatisch zunimmt. Es misst den Nutzungsgrad eines Hash -Tabellenraums. Je größer der Lastfaktor angibt, desto höher ist der Belastungsgrad der Hash -Tabelle und umgekehrt. Für Hash -Tabellen, die mit der verknüpften Listenmethode unter Verwendung einer verknüpften Listenmethode ein Element finden, ist O (1+A). Wenn der Lastfaktor größer ist, wird der Speicherplatz daher vollständiger genutzt, aber die Folge ist eine Abnahme der Suchseffizienz. Wenn der Lastfaktor zu klein ist, sind die Daten der Hash -Tabelle zu spärlich, was zu schwerwiegenden Abfällen am Raum führt. Der Standardlastfaktor des Systems beträgt 0,75 und wir müssen es im Allgemeinen nicht ändern.
HashMap ist eine Datenstruktur, die den schnellen Zugriff unterstützt. Um seine Leistung zu verstehen, müssen Sie seine Datenstruktur verstehen.
III. Datenstruktur
Wir wissen, dass die beiden am häufigsten verwendeten Strukturen in Java Arrays und simulierte Zeiger sind (Referenzen). Fast alle Datenstrukturen können in Kombination mit diesen beiden implementiert werden, und das gleiche gilt für HashMap. Tatsächlich ist HashMap ein "verknüpfter Listen -Hash", wie folgt seiner Datenstruktur:
Aus der obigen Abbildung können wir sehen, ob die zugrunde liegende Implementierung von HashMap oder ein Array ist, aber jedes Element im Array ist eine Kette. Die Parameter initialCapacity repräsentiert die Länge des Arrays. Das Folgende ist der Quellcode des Hashmap -Konstruktors:
public hashmap (int initialCapacity, float loadfactor) {// Die Anfangskapazität kann nicht <0 sein, wenn (initialCapacity <0) neue IllegalArgumentException ("illegale Anfangskapazität:" + initialCapacity); // Anfangskapazität kann nicht> maximaler Kapazitätswert, die maximale Kapazität von HashMap 2^30, wenn (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity; // Lastfaktor kann nicht <0 sein, wenn (loadFactor <= 0 || float.isnan (loadFactor)) neue IllegalArgumentException ("Illegal Lastfaktor:" + loadfactor) werfen; // Berechnen Sie den N-Power-Wert der kleinsten 2 größer als initiale Kapazität. int Kapazität = 1; während (Kapazität <initialCapacity) Kapazität << = 1; this.loadfactor = loadFactor; // Legen Sie die Kapazitätsgrenze von HashMap fest. Wenn die Kapazität von HashMap diese Grenze erreicht, wird der Kapazitätserweiterungsvorgang durch einen Schwellenwert = (int) (Kapazität * Lastfaktor) durchgeführt. // Initialisieren Sie die Tabellenarray -Tabelle = neuer Eintrag [Kapazität]; init (); } Wie aus dem Quellcode hervorgeht, wird jedes Mal ein Tabellenarray initialisiert, wenn ein neuer HashMap erstellt wird. Das Element des Tabellenarrays ist ein Eintragsknoten.
statischer Klasseneintrag <k, v> implementiert map.Entry <k, v> {endgültig k key; V Wert; Eintrag <k, v> Weiter; endgültig int hash; /*** Erstellt einen neuen Eintrag. */ Eintrag (int h, k k, v v, Eintrag <k, v> n) {value = v; Weiter = n; Key = k; Hash = H; } .....}Unter ihnen ist der Eintrag die innere Klasse von HashMap, die den Schlüsselschlüssel, den Wertwert, der nächste Knoten und den Hash -Wert enthält. Das ist sehr wichtig. Genau deshalb bildet die Eintragselemente die Elemente des Tabellenarrays als verknüpfte Liste.
Das obige Analyse der Datenstruktur von HashMap analysiert kurz und untersucht, wie HashMap einen schnellen Zugriff implementiert.
4. Speicherimplementierung: Put (Schlüssel, vlaue)
Schauen wir uns zunächst den Quellcode an
public v put (k key, v value) {// Wenn der Schlüssel null ist, rufen Sie die Putfornullkey -Methode auf, um die erste Position von Null und Tabelle zu speichern. Aus diesem Grund ermöglicht HashMap null, wenn (key == null) putfornullkey (Wert) zurückgeben; // Berechnen Sie den Hash -Wert des Schlüssels int Hash = Hash (key.hashCode ()); ----- (1) // Berechnen Sie die Position des Schlüsselhash-Werts im Tabellenarray int i = indexFor (Hash, Tabelle.Length); ----- (2) // von i iterieren und den Ort finden, an dem der Schlüssel für (Eintrag <k, v> e = Tabelle [i]; e! = Null; e = e.Next) {Objekt k; // Beurteilen Sie, ob der gleiche Hash -Wert in der Kette vorhanden ist (der Schlüssel ist der gleiche) // Wenn dieselbe existiert, überschreiben Sie den Wert direkt und geben Sie den alten Wert zurück, wenn (e.hash == Hash && ((k = e.Key) == Key || key.equals (k)) {v oldValue = E. value; // alter Wert = neuer Wert E.Value = Wert; E. recordaccess (this); kehren Sie OldValue zurück; // alten Wert zurückgeben}} // Erhöhen Sie die Anzahl der Modifikationen durch 1 ModCount ++; // Taste und Wert zum I -Position Addentry (Hash, Schlüssel, Wert, i) hinzufügen; null zurückkehren; }Über den Quellcode können wir deutlich erkennen, dass der Prozess von HashMap -Speicherndaten lautet: Ermitteln Sie zuerst, ob der Schlüssel null ist. Wenn es null ist, rufen Sie direkt die PutfornullKey -Methode an. Wenn es nicht leer ist, berechnen Sie zuerst den Hash -Wert des Schlüssels und suchen Sie dann nach der Indexposition im Tabellenarray gemäß dem Hash -Wert. Wenn an dieser Position ein Element vorhanden ist, vergleichen Sie, ob der gleiche Schlüssel vorhanden ist. Wenn es existiert, überschreiben Sie den Wert des ursprünglichen Schlüssels, sonst speichern Sie das Element am Kopf der Kette (das erste gespeicherte Element wird am Ende der Kette platziert). Wenn die Tabelle dort keine Elemente enthält, wird sie direkt gespeichert. Dieser Prozess scheint einfach zu sein, hat aber tatsächlich tiefe Insider -Informationen. Es gibt mehrere Punkte wie folgt:
1. Schauen wir uns zuerst die Iteration an. Der Grund für die Iteration hier ist, die Existenz des gleichen Schlüsselwerts zu verhindern. Wenn festgestellt wird, dass zwei Hash -Werte (Schlüssel) gleich sind, besteht die Verarbeitungsmethode von HashMap darin, den alten Wert durch den neuen Wert zu ersetzen. Der Schlüssel wird hier nicht verarbeitet, was erklärt, dass es in HashMap keine zwei identischen Schlüssel gibt.
2. In Ansicht (1) und (2). Dies ist die Essenz von Hashmap. Erstens gibt es die Hash -Methode, die eine reine mathematische Berechnung ist, die den Hash -Wert von H berechnen soll.
static int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }Wir wissen, dass für Hashmap -Tabellen die Datenverteilung gleichmäßig sein muss (es ist am besten, nur ein Element für jedes Element zu haben, damit sie direkt gefunden werden kann). Es kann nicht zu eng oder zu locker sein. Zu eng führt zu einer langsamen Abfragegeschwindigkeit, und zu locker verschwendet Platz. Wie können wir nach der Berechnung des Hash -Werts sicherstellen, dass die Tabellenelemente gleich verteilt sind? Wir werden uns an die Schimmelpilze denken, aber da die Schimmelpilzerfassung viel verbraucht, behandelt HashMap sie so: Rufen Sie die Indexfor -Methode an.
static int indexfor (int h, int länge) {return H & (Länge-1); }Die Länge des zugrunde liegenden Arrays von Hashmap liegt immer am N-Strom von 2 und existiert im Konstruktor: Kapazität << = 1; Dies kann immer sicherstellen, dass die Länge des zugrunde liegenden Arrays von Hashmap in der N -Leistung von 2. liegt. Wenn die Länge von 2, H & (Länge - 1) ist, entspricht der Länge des Längens und die Geschwindigkeit ist viel schneller als direkt. Dies ist eine Optimierung von HashMap in Bezug auf Geschwindigkeit. Warum es 2 bis zur n -ten Macht ist, ist die folgende Erklärung.
Kehren wir zurück zur Indexfor -Methode, die nur eine Anweisung enthält: H & (Länge - 1). Zusätzlich zu dem obigen Modulbetrieb hat dieser Satz auch eine sehr wichtige Verantwortung: gleichmäßige Tischdaten zu verteilen und den Platz vollständig zu nutzen.
Hier gehen wir davon aus, dass die Länge 16 (2^n) und 15 und H 5, 6 und 7 beträgt.
Wenn n = 15, sind die Ergebnisse von 6 und 7 gleich, was bedeutet, dass ihre in der Tabelle gespeicherten Standorte gleich sind, dh eine Kollision auftritt, und 6 und 7 bilden eine verknüpfte Liste an einem Ort, was zu einer Abnahme der Abfragendrehzahl führt. Es ist wahr, dass hier nur drei Zahlen analysiert werden, aber nicht viele. Schauen wir uns also 0-15 an.
Aus dem obigen Diagramm sehen wir insgesamt 8 Kollisionen und gleichzeitig stellen wir fest, dass der verschwendete Raum sehr groß ist, ohne dass in 1, 3, 5, 7, 9, 11, 13 und 15 Orte, dh keine Daten gespeichert sind. Dies liegt daran, dass bei der Ausführung und des Betriebs mit 14 das letzte Stück des Ergebniss, das sie erzielen, immer 0 beträgt. Das heißt, es ist unmöglich, Daten an den Stellen von 0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111 und 1111 zu speichern. Der Raum wird reduziert und die Wahrscheinlichkeit einer Kollision wird weiter erhöht, was zu einem langsamen Geschwindigkeitsgeschwindigkeit führt. Wenn Länge = 16, ist die Länge 1 = 15 1111. Bei der Durchführung des niedrigen Bits und des Betriebs ist der Wert immer der gleiche wie der ursprüngliche Hash-Wert, und bei der Durchführung des hohen Bit-Betriebs entspricht sein Wert seinem Wert mit niedrigem Bit. Wenn also Länge = 2^n ist, ist die Kollisionswahrscheinlichkeit zwischen verschiedenen Hash -Werten relativ gering, wodurch die Daten gleichmäßig im Tabellenarray verteilt sind und die Abfragegeschwindigkeit schneller ist.
Hier überprüfen wir den Put-Prozess: Wenn wir einem HashMap ein Paar Schlüsselwerte hinzufügen möchten, berechnet das System zuerst den Hash-Wert des Schlüssels und bestätigt dann den in der Tabelle gespeicherten Ort basierend auf dem Hash-Wert. Wenn an dieser Position kein Element vorhanden ist, fügen Sie es direkt ein. Andernfalls iterieren Sie die Liste der Elemente zu diesem Zeitpunkt und vergleichen Sie den Hash -Wert seines Schlüssels entsprechend. Wenn die beiden Hash -Werte gleich sind und die Schlüsselwerte gleich sind (E.Hash == Hash && ((k = E.Key) == Key || Key.equals (k))), wird der Wert des ursprünglichen Knotens mit dem Wert des neuen Eintrags überschrieben. Wenn die beiden Hash -Werte gleich sind, die Schlüsselwerte nicht gleich sind, fügen Sie den Knoten in den Kopfzeile der verknüpften Liste ein. Für den spezifischen Implementierungsprozess siehe die AddEntry -Methode wie folgt:
void addentry (int hash, k key, v -Wert, int bucketIndex) {// den Eintragseintrag <k, v> e = table [bucketIndex]; // den neu erstellten Eintrag in den BucketIndex -Index einfügen und den neuen Einstiegspunkt in die ursprüngliche Eintragstabelle [bucketIndex] = neuer Eintrag <k, v> (Hash, Schlüssel, Wert, E) lassen; // Wenn die Anzahl der Elemente im HashMap die Grenze überschreitet, ist die Kapazität doppelt so groß, wenn (Größe ++> = Schwelle) Größe (2 * Tabelle.Length); }In dieser Methode sind zwei Punkte zu beachten:
Eine ist die Generation von Ketten. Dies ist ein sehr elegantes Design. Das System fügt dem BucketIndex immer ein neues Eingabobjekt hinzu. Wenn bei BucketIndex ein Objekt vorhanden ist, verweist das neu hinzugefügte Eingabefiel auf das ursprüngliche Eingabefiel und bildet eine Einstiegskette. Wenn es bei BucketIndex jedoch kein Eingabefiel gibt, dh e == null, dann zeigt das neu hinzugefügte Einstiegsobjekt auf NULL, und es wird keine Einstiegskette generiert.
2. Kapazitätserweiterung.
Wenn die Anzahl der Elemente in HashMap zunimmt, wird die Kollisionswahrscheinlichkeit immer größer und die Länge der erzeugten Linkliste wird immer länger. Dies wirkt sich unweigerlich auf die Geschwindigkeit von Hashmap aus. Um die Effizienz von HashMap zu gewährleisten, muss das System die Kapazität zu einem bestimmten kritischen Punkt erweitern. Dieser kritische Punkt ist, wenn die Anzahl der Elemente in HashMap gleich der Tabellenarraylänge* -Lastfaktor ist. Die Skalierung ist jedoch ein sehr zeitaufwändiger Prozess, da das Standort dieser Daten im neuen Tabellenarray neu berechnet und kopiert werden muss. Wenn wir also die Anzahl der Elemente in HashMap vorhergesagt haben, kann die Anzahl der voreingestellten Elemente die Leistung von HashMap effektiv verbessern.
5. Implementierung lesen: Get (Schlüssel)
Im Vergleich zur Lagerung von HashMap ist das Rückzug relativ einfach. Suchen Sie den Eintrag im Index im Tabellenarray über den Hash -Wert des Schlüssels und geben Sie dann den dem Schlüssel entsprechenden Wert zurück.
public v get (Object Key) {// if null, rufen Sie die GetFornullKey -Methode auf, um den entsprechenden Wert zurückzugeben, wenn (key == null) GetFornullKey () zurückgeben; // Berechnen Sie seinen Hash -Code basierend auf dem HashCode -Wert des Schlüssels int Hash = Hash (key.hashCode ()); // den Wert am angegebenen Index im Tabellenarray für (Eintrag <k, v> e = table [indexFor (Hash, Tabelle.Length)] herausnehmen; e! = Null; e = e.next) {Objekt k; // Wenn der durchsuchte Taste der gesuchte Schlüssel übereinstimmt, geben Sie den entsprechenden Wert zurück, wenn (e.hash == Hash && ((k = E.Key) == Key || key.equals (k))) E.Value zurückgeben; } return null; } Hier ist der Wert, der auf der Grundlage des Schlüssels schnell abgerufen werden kann, nicht nur untrennbar mit der Datenstruktur von HashMap untrennbar unternommen, sondern hat auch viel mit dem Eintritt zu tun. Wie bereits erwähnt, speichert HashMap den Schlüssel und den Wert nicht separat im gespeicherten Verfahren, sondern wird als Ganzesschlüsselwert verarbeitet. Gleichzeitig entspricht der Wert nur dem Anhang des Schlüssels. Während des Speichervorgangs bestimmt das System den Speicherort des Eintrags im Tabellenarray basierend auf dem HashCode des Schlüssels, und beim Abrufen wird das entsprechende Eingangsobjekt auch gemäß dem HashCode des Schlüssels herausgenommen.
Original -Link: http://www.cnblogs.com/chenssy/p/3521565.html
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.