HashMap -Übersicht
HashMap ist eine asynchrone Implementierung der Kartenschnittstelle basierend auf der Hash -Tabelle. Diese Implementierung liefert alle optionalen Zuordnungsvorgänge und ermöglicht die Verwendung von Nullwerten und Nullschlüssel. Diese Klasse garantiert nicht die Reihenfolge der Zuordnungen, insbesondere garantiert sie nicht, dass die Bestellung anhält.
Die Datenstruktur von Hashmap
In der Java -Programmiersprache gibt es zwei grundlegende Strukturen, eine ist ein Array und der andere ist ein simulierter Zeiger (Referenz). Alle Datenstrukturen können mit diesen beiden Grundstrukturen konstruiert werden, und HashMap ist keine Ausnahme. HashMap ist eigentlich eine "verknüpfte Liste Hash" -Datenstruktur, dh die Struktur von Arrays und verknüpften Listen, jedoch in JDK1.8
Die Implementierung von rotem und schwarzem Baum wird hinzugefügt. Wenn die Länge der verknüpften Liste größer als 8 ist, wird sie in die Struktur des roten und schwarzen Baumes umgewandelt.
Wie aus der obigen Abbildung ersichtlich ist, verwendet HashMap die Kettenadressmethode in Java. Die Linkadressmethode ist einfach eine Kombination von Arrays und verknüpften Listen. In jedem Array -Element gibt es eine verknüpfte Listenstruktur. Wenn die Daten gehasht werden, wird das Array -Index erhalten und die Daten in die verknüpfte Liste der entsprechenden Indexelemente platziert.
*/ statische Klasse Knoten <k, v> implementiert map.Entry <k, v> {endgültig int hash; // verwendet, um die Position des Array -Index endgültigen K -Schlüssels zu lokalisieren; V Wert; Knoten <k, v> Weiter; // Nächster Knoten im verknüpften Listknoten (int Hash, k -Schlüssel, V -Wert, Knoten <k, v> Weiter) {this.hash = Hash; this.key = key; this.Value = Wert; this.Next = Weiter; }Der Knoten ist eine interne Klasse von HashMap, die die MAP.Entry-Schnittstelle implementiert, die im Wesentlichen eine Karte ist (Schlüsselwertpaar).
Manchmal sind zwei Schlüssel zu derselben Position positioniert, was darauf hinweist, dass eine Hash -Kollision aufgetreten ist. Je gleichmäßiger die Berechnungsergebnisse des Hash -Algorithmus sind, desto kleiner ist die Wahrscheinlichkeit der Hash -Kollision und je höher die Zugangseffizienz der Karte.
Es gibt ein sehr wichtiges Feld in der HashMap -Klasse, nämlich die Knoten -Tabelle, dh das Hash -Bucket -Array. Es ist offensichtlich eine Reihe von Knoten.
Wenn das Hash -Eimer -Array groß ist, wird selbst der arme Hash -Algorithmus mehr verstreut. Wenn das Array -Array -Array des Hash -Bucket Array klein ist, hat selbst ein guter Hash -Algorithmus mehr Kollisionen, sodass es notwendig ist, die Platzkosten und die Zeitkosten abzuwägen. In der Tat soll die Größe des Hash -Bucket -Arrays basierend auf der tatsächlichen Situation bestimmen, und auf dieser Grundlage wird der entworfene Hash -Algorithmus Hash -Kollisionen reduzieren. Wie können wir Karten kontrollieren, um die Wahrscheinlichkeit von Hash -Kollisionen klein zu machen, und Hash -Bucket -Arrays (Knoten [] Tabellen) nehmen weniger Platz ein? Die Antwort ist ein guter Hash -Algorithmus und eine Kapazitätserweiterungsmechanismus.
Bevor wir den Hash- und Expansionsprozess verstehen, müssen wir mehrere Bereiche von HashMap verstehen. Aus dem Standardkonstruktor von HashMaps Standardkonstruktor ist ersichtlich, dass der Konstruktor die folgenden Felder initialisiert, der Quellcode lautet wie folgt:
int Schwelle; // Der Schlüsselwert, der in Anspruch genommen werden kann, ist ultimativer Float-Loadfaktor. // Lastfaktor int modcount; int Größe;
Zunächst ist die Initialisierungslänge der Knoten-Tabelle [] (der Standardwert 16), der Lastfaktor ist der Lastfaktor (der Standardwert 0,75) und der Schwellenwert ist die Anzahl der Knoten (Schlüsselwertpaare) der maximalen Datenmenge, die Hashmap aufnehmen kann. Schwellenwert = Länge * Lastfaktor. Das heißt, nachdem das Array seine Länge definiert hat, desto größer ist der Lastfaktor, desto mehr Schlüsselwertpaare können es aufnehmen.
Basierend auf der Definitionsformel des Lastfaktors ist ersichtlich, dass der Schwellenwert die maximale Anzahl von Elementen ist, die gemäß diesem Lastfaktor und dieser Länge (Arraylänge) zulässig sind. Wenn diese Zahl dies überschreitet, ändern Sie die Größe (Vergrößerungskapazität). Die erweiterte Hashmap -Kapazität ist doppelt so hoch wie die vorherige Kapazität. Der Standardlastfaktor 0,75 ist eine ausgewogene Wahl für Platz- und Zeiteffizienz. Es wird empfohlen, dass Sie es nicht ändern, es sei denn, im Falle eines besonderen Zeitraums und im Hinblick auf den Speicherplatz und bei hoher Zeiteffizienzanforderungen kann der Wert des Lastfaktorlastfaktors verringert werden. Im Gegenteil, wenn der Speicherraum eng ist und die Zeiteffizienzanforderungen nicht hoch sind, kann der Wert des Lastfaktorlastfaktors erhöht werden, was größer als 1 sein kann.
Das Größenfeld ist tatsächlich leicht zu verstehen, es ist die Anzahl der Schlüsselwertpaare, die tatsächlich in HashMap existieren. Beachten Sie die Differenz zwischen der Länge der Tabelle und der Anzahl der Schwellenwerte, die die maximalen Schlüsselwertpaare aufnehmen. Das ModCount -Feld wird hauptsächlich verwendet, um die Anzahl der Änderungen in der internen Struktur von HashMap aufzuzeichnen, und wird hauptsächlich für den schnellen Versagen der Iteration verwendet. Um zu betonen, beziehen sich Änderungen in der internen Struktur auf Änderungen in der Struktur, z.
In HashMap muss die Länge des Hash -Bucket -Array -Tabelle in der N -Leistung von 2 liegen (muss eine zusammengesetzte Zahl sein). Dies ist ein unkonventionelles Design. Das konventionelle Design besteht darin, die Größe des Eimers als Primzahl zu entwerfen. Relativ gesehen ist die Wahrscheinlichkeit von Konflikten, die durch Primzahlen verursacht werden, kleiner als die von zusammengesetzten Zahlen. Weitere Beweise finden Sie unter //www.vevb.com/article/100911.htm. Der Hashtabelle initialisiert die Eimergröße auf 11, dh die Anwendung der als Primzahlen ausgelegten Eimergröße (das Hashtabelle kann nach der Ausdehnung nicht garantiert werden). HashMap nimmt dieses unkonventionelle Design an, hauptsächlich, um beim Modulo und der Expansion zu optimieren. Gleichzeitig fügt HashMap, um Konflikte zu reduzieren, auch den Prozess der hohen Beteiligung an der Computing hinzu, wenn die Position der Hash-Bucket-Indexposition gefunden wird.
Hier gibt es ein Problem. Selbst wenn der Lastfaktor und der Hash -Algorithmus vernünftig gestaltet sind, wird es unweigerlich eine Situation geben, in der der Reißverschluss zu lang ist. Sobald der Reißverschluss zu lang ist, wird dies die Leistung von HashMap ernsthaft beeinflussen. Daher wurde in der JDK1.8 -Version die Datenstruktur weiter optimiert und der rote und schwarze Baum eingeführt. Wenn die Länge der verlinkten Liste zu lang ist (die Standardeinstellung ist mehr als 8), wird die verknüpfte Liste in einen roten und schwarzen Baum umgewandelt. Die Eigenschaften von rotem und schwarzem Baum schneller Zugabe, Löschungen, Modifikationen und Suchanfragen werden verwendet, um die Leistung von HashMap zu verbessern. Einfügen, Löschen und Suche nach roten und schwarzen Bäumen werden verwendet, um Algorithmen wie roter und schwarzer Baum zu löschen, zu löschen und zu suchen.
Bestimmen Sie die Indexposition des Hash -Bucket -Arrays
Code -Implementierung:
// Methode 1: statische endgültige int Hash (Objektschlüssel) {//jdk1.8 & jdk1.7 int h; // H = key.hashCode () erhält den HashCode -Wert für den ersten Schritt // H ^ (h >>> 16) Nehmen Sie an der Operation des zweiten Schritts zurück (Key == NULL)? 0: (h = key.hashCode ()) ^ (h >>> 16);} // Methode 2: statische Indexfor (int H, int Länge) {//jdk1.7 Quellcode, JDK1.8 hat diese Methode nicht, aber das Implementierungsprinzip ist dieselbe Rückgabe-H & (Länge 1). // Der dritte Schritt macht den Modul -Betrieb}Der Hash-Algorithmus besteht hier im Wesentlichen drei Schritte: den HashCode-Wert des Schlüsselbetriebs, des hohen Bit-Betriebs und des Modulbetriebs.
Für ein bestimmtes Objekt, solange der HashCode () -Rendwert der gleiche ist, ist der von der Programmaufruf Methode eins berechnete Hash -Code immer der gleiche. Das erste, woran wir denken, ist, den Hash -Wert für die Arraylänge zu moduieren, damit die Verteilung der Elemente relativ gleichmäßig ist. Der Verbrauch von Moduloperationen ist jedoch relativ groß. Dies geschieht in HashMap: Rufen Sie die Methode zwei auf, um zu berechnen, welches Index das Objekt im Tabellenarray gespeichert werden soll.
Diese Methode ist sehr klug. Es erhält die gespeicherten Bits des Objekts über H & (Tabelle.Length -1), und die Länge des zugrunde liegenden Arrays von HashMap ist immer zur N -Leistung von 2, was die Optimierung von HashMap in Bezug auf Geschwindigkeit ist. Wenn die Länge immer mit der N-Leistung von 2 liegt, entspricht der H & (Länge-1) -Operation der Modulo Länge, dh H %Länge, aber eine höhere Effizienz als %.
Bei der Implementierung von JDK1.8 ist der Algorithmus für Hochbit-Operationen optimiert und die Implementierung von HashCode (H = K.hashcode ()) ^ (h >>> 16), was hauptsächlich aus der Geschwindigkeit, Effizienz und Qualität berücksichtigt wird. Dies kann sicherstellen, dass die Länge der Array-Tabelle relativ gering ist, sie auch sicherstellen kann, dass Bits an Hash-Berechnungen unter Berücksichtigung von hohen Liegestütze beteiligt sind, und es gibt keinen übermäßigen Overhead.
Hier ist ein Beispiel: N ist die Länge der Tabelle.
HashMap -Put -Methode -Implementierung
Die allgemeine Idee der Put -Funktion ist:
Der spezifische Code wird wie folgt implementiert:
public v put (k key, v value) {return putval (Hash (Schlüssel), Schlüssel, Wert, Falsch, True); } / ***Methode zum Generieren von Hash* / static endgültig int Hash (Objektschlüssel) {int h; return (key == null)? 0: (h = key.hashcode ()) ^ (h >>> 16); } endgültig v putval (int Hash, K -Schlüssel, V -Wert, nur boolean ifabSent, boolean evict) {Knoten <k, v> [] Registerkarte; Knoten <k, v> p; int n, ich; // Beurteilen Sie, ob die Tabelle leer ist, if ((tab = table) == null || (n = tab.length) == 0) n = (tab = dresize (). Länge; // Erstellen Sie ein neues Tabellenarray und erhalten Sie die Länge des Arrays // den Hash -Wert für den eingefügten Array -Index i gemäß dem Schlüsselwertschlüssel berechnen. Wenn Tabelle [i] == null, erstellen Sie direkt einen neuen Knoten und fügen Sie wenn ((p = tab [i = (n - 1) & Hash]) Tab [i] = newnode (Hash, Schlüssel, Wert, NULL); sonst {// Wenn der entsprechende Knoten einen Knoten <k, v> e hat; K k k; // Beurteilen Sie, ob das erste Element der Tabelle [i] der Schlüssel entspricht, wenn der gleiche der Wert überschreibt, wenn (p.hash == Hash && ((k = P.Key) == Key || (Key! = NULL && key.equals (k))) e = p; // Beurteile, ob Tabelle [i] ein Treenode ist, dh, ob Tabelle [i] ein rot-schwarzer Baum ist. Wenn es sich um einen rot-schwarzen Baum handelt, fügen Sie das Schlüsselwertpaar direkt in den Baum ein, wenn (p Instanz von TreeNode) e = ((Treenode <k, v>) p) .putreeval (diese, Tab, Hash, Schlüssel, Wert); // Diese Kette ist eine verknüpfte Liste else {// Durch die Tabelle [i] transipatieren, um festzustellen, ob die Länge der verlinkten Liste größer ist als baumify_threshold (der Standardwert beträgt 8). Wenn es größer als 8 ist, konvertieren Sie die verknüpfte Liste in einen rotschwarzen Baum und führen Sie den Einfügungsvorgang im rot-schwarzen Baum durch. Andernfalls wird der Einfügungsbetrieb der verlinkten Liste durchgeführt. Wenn festgestellt wird, dass der Schlüssel bereits einen direkten Überschreibwert während des Durchquellenprozesses hat; für (int bincount = 0;; ++ bincount) {if ((e = p.Next) == null) {P.Next = newnode (Hash, Schlüssel, Wert, NULL); if (bincount> = baumify_threshold - 1) // -1 für 1. baumifybin (tab, Hash); brechen; } if (e.hash == Hash && ((k = e.Key) == Key || (Schlüssel! = null && key.equals (k)))) break; p = e; }} // schreiben if (e! = Null) {// Bestehende Zuordnung für Schlüssel v oldValue = E. value; if (! Nur IfababSent || oldValue == null) E. value = Wert; Nachmittagscess (e); kehren Sie OldValue zurück; }} ++ modcount; // Bestimmen Sie nach erfolgreicher Einführung, ob die tatsächliche Anzahl der Schlüsselwertpaare den maximalen Kapazitätsschwellenwert überschreitet. Wenn es die Kapazität überschreitet, erweitern Sie, wenn (++ Größe> Schwellenwert) die Größe () der Größe (); Nachmittagseinsertion (Evict); null zurückkehren; }HashMap -Methode Implementierung erhalten
Die Idee ist wie folgt:
1. Der erste Knoten im Eimer, direkt getroffen;
2. Wenn es einen Konflikt gibt, verwenden
Wenn es sich um einen Baum handelt, suchen Sie im Baum durch Schlüssel.Eequals (k), o (logn);
Wenn es sich um eine verknüpfte Liste handelt, suchen Sie in der verknüpften Liste o (n) durch Key.equals (k).
public v Get (Objektschlüssel) {Knoten <k, v> e; return (e = getNode (Hash (Schlüssel), Schlüssel)) == NULL? NULL: E. value; } Final Node <k, v> getNode (int Hash, Objektschlüssel) {Knoten <k, v> [] Registerkarte; Knoten <k, v> zuerst, e; int n; K k k; if ((tab = table)! // verpasst if ((e = first.Next)! // Get do {if (e.hash == Hash && ((k = e.Key) == Key || (Key! = Null && key.equals (k))) return e; } while ((e = e.Next)! = null); }} return null; }Kapazitätserweiterungsmechanismus
Die Größenänderung bedeutet neu neu, die Kapazität neu zu berechnen und dem HashMap -Objekt ständig Elemente hinzuzufügen. Wenn das Array im HashMap -Objekt nicht mehr Elemente laden kann, muss das Objekt die Länge des Arrays erweitern, damit mehr Elemente geladen werden können. Natürlich können Arrays in Java nicht automatisch erweitert werden. Die Methode besteht darin, ein neues Array anstelle von vorhandenen Arrays mit geringer Kapazität zu verwenden, genau wie wir einen kleinen Eimer zum Füllen von Wasser verwenden. Wenn wir mehr Wasser füllen wollen, müssen wir es durch einen großen Eimer ersetzen.
Wir analysieren den Quellcode der Größe. Angesichts der Tatsache, dass JDK1.8 rote und schwarze Bäume integriert, ist es komplizierter. Um das Verständnis zu erleichtern, verwenden wir immer noch JDK1.7 -Code, was leichter zu verstehen ist. Es gibt kaum Unterschiede im Wesentlichen. Sprechen wir später über die spezifischen Unterschiede.
void -Größe (int NewCapacity) {// PAULE neue Kapazitätseintrag [] oldTable = Tabelle; // Verweisen Sie auf das Eintragsarray vor der Erweiterung int oldCapacity = oldTable.length; if (OldCapacity == Maximum_Capacity) {// Wenn die Arraygröße vor der Erweiterung den Maximum (2^30) Schwelle = Integer.max_Value erreicht hat; // den Schwellenwert an den Maximalwert von INT (2^31-1) ändern, damit die Kapazität in der zukünftigen Rendite nicht erweitert wird. } Eintrag [] newtable = neuer Eintrag [NewCapacity]; // eine neue Eintragsarray -Übertragung initialisieren (Newtable); //! ! Daten in die neue Eintragsarray -Tabelle übertragen = newtable; // HashMaps Tabellenattribut bezieht sich auf den neuen Eintrags -Array -Schwellenwert = (int) (NewCapacity * LoadFactor); // den Schwellenwert ändern}Hier verwenden wir ein Array mit einer größeren Kapazität anstelle eines vorhandenen Arrays mit geringerer Kapazität. Die Methode Transfer () kopiert die Elemente des ursprünglichen Eintragsarrays in das neue Eintragsarray.
void Transfer (Eintrag [] newtable) {Eintrag [] Src = Tabelle; // src bezieht sich auf das alte Eintragsarray int newcapacity = newtable.length; für (int j = 0; j <src.length; j ++) {// Ruhe durch den alten Eintrags -Array -Eintrag <k, v> e = src [j]; // Holen Sie sich jedes Element des alten Eintragsarrays if (e! = Null) {src [j] = null; // Die Objektreferenz des alten Eintragsarrays (nach der für die für die Schleife, bezieht sich das alte Eintragsarray nicht mehr auf Objekte) do {Eintrag <k, v> next = e.Next; int i = indexFor (e.hash, newcapacity); //! ! Berechnen Sie die Position jedes Elements im Array e.Next = newtable [i]; // tag [1] newtable [i] = e; // das Element auf das Array E = Weiter setzen; // Zugriff auf das Element in der nächsten Einstiegskette} wobei (e! = Null); }}}Der Verweis auf Newtable [i] wird E.Next zugeordnet, was bedeutet, dass die Header -Insertionsmethode einer einzelnen verknüpften Liste verwendet wird. Neue Elemente an derselben Position werden immer am Kopf der verlinkten Liste platziert. Auf diese Weise werden die in einem Index platzierten Elemente schließlich am Ende der Einstiegskette platziert (wenn ein Hash -Konflikt auftritt). Dies unterscheidet sich von JDK1.8, was im Folgenden ausführlich erklärt wird. Elemente in derselben Einstiegskette im alten Array können nach Neuberechnung der Indexposition an verschiedenen Positionen im Neuarray platziert werden.
Hier ist ein Beispiel, um den Kapazitätserweiterungsprozess zu veranschaulichen. Angenommen, unser Hash -Algorithmus verwendet einfach einen Schlüsselmod, um die Größe der Tabelle zu erhalten (dh die Länge des Arrays). Die Größe der Hash -Bucket -Array -Tabelle = 2, so dass der Schlüssel = 3, 7, 5 und die Put -Reihenfolge 5, 7 und 3. Nach Mod 2 beträgt der Konflikt in Tabelle [1]. Hier wird angenommen, dass der Lastfaktor-Lastfaktor = 1, dh wenn die tatsächliche Größe des Schlüsselwertpaares größer ist als die tatsächliche Größe der Tabelle, wird es erweitert. Die nächsten drei Schritte sind der Prozess der Größe des Hash -Bucket -Arrays auf 4 und dann alle Knoten.
Lassen Sie uns erklären, welche Optimierungen in JDK1.8 vorgenommen wurden. Nach der Beobachtung können wir feststellen, dass wir eine Leistung von zwei Expansionen anwenden (unter Bezugnahme auf die Länge des zweifachen Originals), sodass die Position des Elements entweder in der ursprünglichen Position liegt oder die Position der Kraft von zwei an der ursprünglichen Position erneut bewegt. Wenn Sie sich die folgende Abbildung ansehen, können Sie die Bedeutung dieses Satzes verstehen. n ist die Länge des Tisches. Abbildung (a) stellt ein Beispiel für die Indexposition der beiden Schlüssel dar, die die Indexposition des Key1 und Key2 vor der Ausdehnung bestimmen. Abbildung (b) stellt ein Beispiel für die Indexposition des Key1 und Key2 nach der Ausdehnung dar. Wo Hash1 das Ergebnis von Hash- und Hochbit-Betrieb ist, das KEY1 entspricht.
Nachdem das Element den Hash neu berechnet hat, da N 2-mal wird, ist der Maskenbereich von N-1 am Höhepunkt 1 Bit (rot), sodass sich der neue Index so ändert:
Wenn wir HashMap erweitern, müssen wir den Hash nicht wie die Implementierung von JDK1.7 neu berechnen. Wir müssen nur sehen, ob das zum ursprünglichen Hash -Wert hinzugefügte Bit 1 oder 0 beträgt. Wenn es 0 ist, hat sich der Index nicht geändert. Wenn es 1 ist, wird der Index "Original Index + OldCap". Sie können die folgende Abbildung als Diagramm der Größe mit 16 Expansion auf 32 sehen:
Dieses Design ist in der Tat sehr clever, was nicht nur die Zeit spart, um den Hash -Wert neu zu berechnen, sondern auch, da das neu hinzugefügte 1 -Bit 0 oder 1 als zufällig angesehen werden kann, sodass der Größenvorgang die vorherigen widersprüchlichen Knoten gleichmäßig an den neuen Eimer verteilt. Dies ist der neue Optimierungspunkt von JDK1.8. Es ist ein wenig Aufmerksamkeit auf den Unterschied. Wenn in JDK1.7, wenn alte verknüpfte Listen neue verknüpfte Listen migrieren, sind die verknüpften Listen -Listen, wenn die Array -Indexposition der neuen Tabelle gleich ist, die verknüpften Listenelemente invertiert werden, aber wie aus der obigen Abbildung angezeigt wird, wird JDK1.8 nicht invertiert. Interessierte Schüler können den Größenquellencode von JDK1.8 studieren, was sehr gut ist, wie folgt:
Final Node <k, v> [] resize () {Knoten <k, v> [] oldtab = table; int oldcap = (oldtab == null)? 0: Oldtab.length; int Oldthr = Schwelle; Int Newcap, newthr = 0; if (OldCap> 0) {// Wenn der Maximalwert überschreitet, wird er nicht mehr erweitert. Daher muss ich mit Ihnen kollidieren, wenn (oldcap> = maximum_capacity) {threshold = integer.max_value; kehre Oldtab zurück; } // Wenn der Maximalwert nicht überschritten wird, wird er auf das 2 -fache des Originals if ((newcap = oldcap << 1) <maximum_capacity && oldcap> = default_initial_capacity) newthr = alte thr << 1; // Double Threshold} else wenn (Oldthr> 0) // die anfängliche Kapazität in Schwellenwert newcap = Oldthr platziert wurde; else {// Null -Initial -Schwellenwert bedeutet die Verwendung von Standards NewCap = default_initial_capacity; newthr = (int) (default_load_factor * default_initial_capacity); } // Berechnen Sie die neue Größe der Größe der Größe, wenn (newthr == 0) {float ft = (float) newcap * loadFactor; newthr = (newcap <maximum_capacity && ft <(float) maximum_capacity? (int) ft: ganzEger.max_value); } threshold = newhr; @SuppressWarnings ({"rawttypes", "deaktiviert"}) Knoten <k, v> [] newtab = (Knoten <k, v> []) neuer Knoten [NewCap]; Tabelle = Newtab; if (oldtab! if ((e = oldtab [j])! = null) {OldTab [j] = null; if (e.Next == null) newtab [e.hash & (newcap - 1)] = e; sonst if (e Instanz von Treenode) ((Treenode <k, v>) e) .Split (this, Newtab, J, OldCap); sonst {// Bestellknoten <k, v> lohead = null, lotail = null; Knoten <k, v> hihead = null, hitail = null; Knoten <k, v> Weiter; do {next = e.Next; // Original index if ((e.hash & oldcap) == 0) {if (lotail == null) lohead = e; sonst lotail.next = e; lotail = e; } // Original index + oldcap else {if (hitail == null) hihead = e; sonst hitail.next = e; Hitail = e; }} while ((e = next)! = null); // den ursprünglichen Index in den Bucket eingeben, wenn (lotail! = Null) {lotail.next = null; newtab [j] = lohead; } // Geben Sie den ursprünglichen Index + OldCap in den Bucket if (hitail! = Null) {hitail.next = null; Newtab [J + OldCap] = Hihead; }}}}} return Newtab;}Zusammenfassen
Wir können jetzt zu Beginn mehrere Fragen beantworten, um unser Verständnis von HashMap zu vertiefen:
1. Wann wird Hashmap verwendet? Was sind seine Eigenschaften?
Es basiert auf der Implementierung der Kartenschnittstelle. Beim Speichern von Schlüsselwertpaaren kann es Null-Schlüsselwerte empfangen, was asynchron ist. HashMap speichert Eintrag (Hash, Schlüssel, Wert, nächste) Objekte.
2. Wissen Sie, wie HashMap funktioniert?
Durch die Hash -Methode werden Objekte durch Put and Get gespeichert und erhalten. Wenn wir ein Objekt speichern, ruft bei der Übergabe von K/V an die Put -Methode HashCode auf, um den Hash zu berechnen, um den Bucket -Standort zu erhalten und es weiter zu speichern. HashMap passt automatisch die Kapazität gemäß dem aktuellen Eimer -Beruf an (wenn sie die Lastfacotr überschreitet, ist die Größe der Größe doppelt so hoch wie das ursprüngliche). Wenn wir das Objekt erhalten, übergeben wir K an die Erlangung von HashCode, um Hash zu berechnen, um die Bucket-Position zu erhalten, und ruft die Equals () -Methode weiter, um das Schlüsselwertpaar zu bestimmen. Wenn eine Kollision auftritt, organisiert HashMap die Elemente, die Kollisionskonflikte über die verknüpfte Liste erzeugen. Wenn in Java 8 die Elemente, die in einem Eimer kollidieren, eine bestimmte Grenze überschreiten (die Standardeinstellung 8), wird ein rot -schwarzer Baum verwendet, um die verknüpfte Liste zu ersetzen, um die Geschwindigkeit zu erhöhen.
3.. Kennen Sie die Prinzipien von Get and Send? Was sind die Funktionen von Equals () und HashCode ()?
Durch Hashing des HashCode () des Schlüssels und des Berechnens des Index (N-1 & Hash) wird die Position der Eimer erhalten. Wenn eine Kollision auftritt, verwenden Sie die Methode der Schlüssel.equals (), um nach dem entsprechenden Knoten in der verknüpften Liste oder in der verknüpften Liste zu suchen
4. Kennen Sie die Implementierung von Hash? Warum muss ich das tun?
Bei der Implementierung von Java 1.8 wird es über den hohen 16-Bit-x-or-niedrigen 16-Bit von HashCode () implementiert: (h = k.hashcode ()) ^ (h >>> 16), was hauptsächlich aus Geschwindigkeit, Effizienz und Qualität berücksichtigt wird. Dies kann sicherstellen, dass der N des Eimers relativ gering ist, es auch sicherstellen kann, dass sowohl hohe als auch niedrige Bits an der Hash -Berechnung beteiligt sind und es keinen übermäßigen Aufwand gibt.
5. Was ist, wenn die Größe von HashMap die durch den Lastfaktor definierte Kapazität überschreitet?
Wenn der Lastfaktor überschritten wird (Standard 0,75), wird eine HashMap mit der doppelten ursprünglichen Länge geändert und die Hash -Methode erneut aufgerufen.
Das Cheat -Blatt über Java -Sammlungen wird wie folgt beschrieben:
Das mit dem Eintrag [] -Array implementierte Hash -Bucket -Array und der Hash -Wert des Schlüssels kann verwendet werden, um das Array -Index zu erhalten.
Wenn ein Element einfügt, wenn zwei Schlüssel in denselben Eimer fallen (zum Beispiel nach den Hash-Werten 1 und 17 Modulo 16, gehören beide zum ersten Hash-Bucket), verwendet der Eintrag eine nächste Eigenschaft, um mehrere Einträge in einer Einweg-Verknüpfungsliste zu implementieren, und der Eintrag, der in die Bucket-Punkte neben dem aktuellen Eintrag des Eimers eingeht.
Wenn Sie nach einem Schlüssel mit einem Hash -Wert von 17 suchen, suchen Sie zuerst den ersten Hash -Eimer, dann alle Elemente im Eimer mit einer verknüpften Liste durch und vergleichen Sie ihre Schlüsselwerte einzeln.
Wenn die Anzahl der Eingaben 75% der Eimer erreicht (viele Artikel besagen, dass die Anzahl der verwendeten Eimer 75% erreicht. Laut dem Code wird das Bucket -Array jedoch exponentiell erweitert und der gesamte ursprüngliche Eintrag wird neu zugewiesen, sodass es am besten einen geschätzten Wert hier hat.
Die Bitoperation (Hash & (ArrayLength-1)) ist schneller, sodass die Größe des Arrays immer auf die N-Leistung von 2 liegt. Wenn Sie einen Anfangswert wie 17 angeben, wird er in 32 konvertiert. Der Standard-Anfangswert, wenn das Element zuerst platziert wird, beträgt 16.
Iterator () durchquert entlang des Hash -Bucket -Arrays, das wie ein außergewöhnliches Aussehen aussieht.
6. Was passiert, wenn der HashCode von zwei Objekten gleich ist?
Da der HashCode gleich ist, ist ihre Eimerposition gleich und es wird eine "Kollision" passieren. Da HashMap eine verknüpfte Liste verwendet, um Objekte zu speichern, wird dieser Eintrag (das MAP.Entry-Objekt, das Schlüsselwertpaare enthält) in der verlinkten Liste gespeichert.
7. Wenn der HashCode von zwei Schlüssel gleich ist, wie erhalten Sie das Wertobjekt?
Nach dem Finden des Bucket -Standorts wird die Methode der Schlüsseln.Equals () aufgerufen, um den richtigen Knoten in der verknüpften Liste zu finden und schließlich das zu findene Wertobjekt zu finden. Bei der Gestaltung des Schlüsseltyps von HashMap werden daher das Auftreten von Kollisionen verringert und die Effizienz verbessert, wenn ein unveränderliches Objekt als endgültig und die entsprechenden Equals () und Hashcode () -Methoden angewendet wird. Immutabilität kann Hashcodes für verschiedene Schlüssel zwischenspeichern, was die Geschwindigkeit des gesamten Objekts erhöht. Die Verwendung von Wrapper -Klassen wie String und Interger als Schlüssel ist eine sehr gute Wahl.
8. Was ist, wenn die Größe von HashMap die durch den Lastfaktor definierte Kapazität überschreitet?
Die Standardlastfaktorgröße beträgt 0,75. Das heißt, wenn eine Karte 75% Eimer füllt, wie andere Sammlungsklassen (wie ArrayList usw.), wird ein Eimer -Array, das doppelt so groß ist wie die Größe des ursprünglichen Hashmap, erstellt, um die Größe der Karte zu ändern und das ursprüngliche Objekt in das neue Bucket -Array zu setzen. Dieser Vorgang wird als Aufermaschinen bezeichnet, da er die Hash -Methode aufruft
9. Verstehst du, was an der Größenänderung von HashMap falsch ist?
Bei der Größenänderung von HashMap gibt es tatsächlich bedingte Konkurrenz, denn wenn beide Threads feststellen, dass Hashmap die Größe der Größe verändert werden muss, werden sie gleichzeitig versuchen, die Größe zu ändern. Während der Größe des Größengrößenverfahrens wird die Reihenfolge der in der verknüpften Liste gespeicherten Elemente umgekehrt, da HashMap beim Umzug in die neue Bucket -Position die Elemente nicht am Ende der verknüpften Liste, sondern am Kopf nicht platziert. Wenn eine bedingte Konkurrenz auftritt, gibt es einen Teufelskreis. Daher verwenden wir in einer gleichzeitigen Umgebung CurrentHasMap, um HashMap zu ersetzen
10. Warum sind Wrapper -Klassen wie String und Interger als Schlüssel geeignet?
Da String unveränderlich und endgültig ist und die Methoden Equals () und HashCode () umgeschrieben wurden. Andere Wrapper -Klassen haben ebenfalls diese Funktion. Unmutabilität ist erforderlich, da Sie zur Berechnung von HashCode () verhindern müssen, dass sich der Schlüsselwert ändert. Wenn der Schlüsselwert beim Einsetzen und Erhalten einen anderen HashCode zurückgibt, können Sie das gewünschte Objekt nicht von der HashMap finden. Die Unveränderlichkeit hat andere Vorteile wie die Sicherheit von Threads. Wenn Sie garantieren können, dass der HashCode nur durch das endgültige Deklarieren eines Feldes unverändert bleibt, dann tun Sie dies bitte. Da die Methoden Equals () und HashCode () beim Erhalten von Objekten verwendet werden, ist es sehr wichtig, diese beiden Methoden korrekt neu zu schreiben. Wenn zwei ungleiche Objekte verschiedene Hashcodes zurückgeben, ist die Wahrscheinlichkeit einer Kollision kleiner, was die Leistung von HashMap verbessert
Danke fürs Lesen, ich hoffe, es kann Ihnen helfen. Vielen Dank für Ihre Unterstützung für diese Seite!