Vorwort: Nach Java 8 werden viele neue Dinge hinzugefügt. Ich habe einige relevante Informationen online gefunden. Nachdem Hashmap missbraucht worden war, beschloss ich, das relevante Wissen für mich selbst zu klären. Dieser Artikel als Referenz im Bild und einige Inhalte: http://www.vevb.com/article/80446.htm
Die Speicherstruktur von HashMap ist in der Abbildung dargestellt: Wenn mehr als 8 Knoten auf einem Eimer vorhanden sind, ist die Speicherstruktur ein rot-schwarzer Baum und weniger als 8 ist eine einseitige verlinkte Liste.
1: Einige Eigenschaften von HashMap
öffentliche Klasse Hashmap <k, v> erweitert AbstractMap <K, V> implementiert MAP <K, V>, klonbar, serialisierbar {private statische endgültige lange Serialversionuid = 3624988820763181265L; // Die Standardkapazität ist 16statische Final -Int -Standard -Int -Maximum -Maximum -Dinit -Maximum -Maximum -Degelung. << 30; // Der Standard -Füllfaktor (die vorherigen Versionen wurden auch als Lastfaktor bezeichnet) statische endgültige Float default_load_factor = 0,75F; // Dies ist ein Schwellenwert. Wenn die Anzahl der verknüpften Listen auf dem Eimer größer als dieser Wert ist, wird er in einen roten und schwarzen Baum umgewandelt. Der Code der Put -Methode verwendet statische endgültige int treeify_threshold = 8; // Es ist auch der Schwellenwert. Wenn die Anzahl der verknüpften Listen auf dem Eimer geringer ist als dieser Wert, wird der Baum in eine verknüpfte Liste statische endgültige Int Unreefeif_threshold = 6; // In dem Quellcode -Kommentar gesagt, dass es sich um: Mindestkapazität des Baums ist mindestens 4 x Baumify_Thresh -Thresh -Threscen -Final -Int -min_treitierende und baumabend. von Elementen wird gespeichert, immer ein Vielfaches von 2 transienten Knoten <k, v> [] Tabelle; Transient Set <map.Entry <k, v >> Eintragset; // Die Anzahl der gespeicherten Elemente beachten Sie, dass dies nicht gleich der Länge des Arrays entspricht. Transient Int Größe; // Der Zähler für jede Expansion und Änderung der Kartenstruktur ist transient int modcount; // Der kritische Wert wird erweitert, wenn die tatsächliche Größe (Kapazität * Füllfaktor) den kritischen Wert überschreitet. Die Kapazität wird erweitert int.2: Hashmap -Konstruktionsmethode
// Konstruktor zur Angabe der anfänglichen Kapazität und des Füllfaktors öffentliches Hashmap (intiturinitur, float loadfactor) {// Die angegebene Anfangskapazität ist nicht negativ, wenn (initialCapacity <0) neue IllegalArgumentException (illegale Anfangskapazität (illegale anfängliche Kapazität). Maximum_Capacity; // Das Füllverhältnis ist positiv, wenn (loadfactor <= 0 || float.isnan (loadFactor)) neue IllegalArgumentException (illegaler Lastfaktor: +loadfactor) werfen; this.loadfactor = loadFactor; // Nach Angabe der Kapazität berechnet das Tabellenwert für die Methode den kritischen Wert. Wenn der Wert beim Einlegen der Daten überschritten wird, wird er erweitert. Der Wert ist definitiv ein Vielfaches von 2.// Die angegebene anfängliche Kapazität wurde nicht gespeichert, und es wird nur verwendet, um einen kritischen Wert zu erzeugen. Rechte n | = n >>> 1; n | = n >>> 2; n | = n >>> 4; n | = n >>> 8; n | = n >>> 16; // verschachtelte Rückgabe trigonometrischer Operatoren (n <0)? 1: (n> = maximum_capacity)? Maximum_Capacity: n + 1;} // Konstruktor 2Public HashMap (init initialCapacity) {this (initialCapacity, default_load_factor);} // Konstruktor 3Public Hashmap () {this.loadfactor = Default_load_factor; // Alle anderen Felder standardmäßig}3: Bestimmen Sie die Position des Elements im Array, wenn Sie erhalten und setzen
statische endgültige int Hash (Objektschlüssel) {int h; return (key == null)? 0: (h = key.hashcode ()) ^ (h >>> 16);}Um den Ort zu bestimmen
Der erste Schritt: Das erste ist, den Hash -Code des Schlüssels zu berechnen, der eine Int -Typ -Nummer ist. Die folgenden Kommentare von H >>> 16 Quellcode sagen: Um Hash -Kollisionen zu vermeiden, wird die hohe Position auf die niedrige Position verbreitet, die nach Berücksichtigung verschiedener Faktoren wie Geschwindigkeit und Leistung erfolgt.
Schritt 2: H ist der Hash-Code, Länge ist die Länge des Knotens [] -Array oben und dieselbe Operation H & (Länge-1). Da die Länge ein Vielfaches von 2 -1 ist, beträgt sein Binärcode 1 und das Ergebnis von 1 mit anderen Zahlen kann 0 oder 1 sein, um eine Gleichmäßigkeit nach dem Betrieb zu gewährleisten. Das heißt, die Hash -Methode sorgt für die Einheitlichkeit der Ergebnisse, die sehr wichtig ist und die Put und die Leistung von HashMap erheblich beeinflussen. Siehe das folgende Bild zum Vergleich:
Abbildung 3.1 sind asymmetrische Hash -Ergebnisse
Abbildung 3.2 ist das ausgewogene Hash -Ergebnis
In diesen beiden Grafiken gibt es nicht viele Daten. Wenn die verknüpfte Liste länger als 8 ist, wird sie in einen roten und schwarzen Baum umgewandelt. Es wäre zu dieser Zeit offensichtlicher. JDK8 war schon immer eine verknüpfte Liste. Die Komplexität der verknüpften Listenabfrage ist O (n) und die Komplexität von roten und schwarzen Bäumen aufgrund ihrer eigenen Eigenschaften ist O (log (n)). Wenn die Hash -Ergebnisse ungleichmäßig sind, wird dies die Komplexität der Operation stark beeinflussen. Es gibt ein <a <a href = "http://blog.chinanix.net/uid-26575352-id-3061918.html"> rot und schwarzer Baum grundlegende Knowledge-Blog </a> Es gibt ein weiteres Online-Beispiel, um zu verifizieren: Ein benutzerdefinierter Objekt wird verwendet, um die Schlüsseln zu erstellen und die Hader-Hader-Methode zu erstellen ().
public class MutableKeyTest {public static void main(String args[]){class MyKey {Integer i;public void setI(Integer i) {this.i = i;}public MyKey(Integer i) {this.i = i;}@Overridepublic int hashCode() {// If 1// return 1return i;}// object is stored as a key map, the equals method muss implementiert werden @Overridepublic boolean Equals (Object obj) {if (obj instanceof mykey) {return i.equals ((((mykey) obj) .i);} else {return false;}}} // meine Maschinenkonfiguration ist nicht hoch. if 25000 ist normal. = new Hashmap <> (25000,1); Datum begin = new Date (); für (int i = 0; i <20000; i ++) {map.put (neuer mykey (i), "test" + i);} Datum end = new Date (); System.out.Out.println ("time (ms)" + (end.getTime () - begin.4: Methode abrufen
public v get (Objektschlüssel) {Knoten <k, v> e; return (e = getNode (Hash (Schlüssel), Schlüssel)) == NULL? NULL: E. value;} endgültiger Knoten <k, v> getNode (int Hash, Objektschlüssel) {Knoten <k, v> [] Registerkarte; Knoten <k, v> zuerst, e; int n; K k; // Hash & (Länge -1) Holen Sie sich die Wurzelposition des roten und schwarzen Baums oder die Header der verlinkten Liste if ((tab = table)! key.equals (k))) return zuerst; if ((e = first.Next)! == Hash && ((k = E.Key) == Key || (Schlüssel!5: Suchen Sie den Eimer nach H & (Länge 1) und prüfen Sie, ob es sich um einen roten und schwarzen Baum oder eine verknüpfte Liste und PutVal handelt
public v put (k key, v value) {return putval (Hash (Schlüssel), Schlüssel, Wert, Falsch, True);} endgültig v putval (int hash, k key, v -Wert, boolean nur ifababSent, boolean evict) {Knoten <k, v> [] tab; Knoten <k, v> p; Int n, i; // Wenn die Registerkarte leer ist oder die Länge 0 ist, zuordnete Speicher -Größen () if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize ()). Länge; // (n - 1) & Hash findet die Putposition. Wenn es leer ist, putif direkt ((p = tab [i = (n - 1) & hash]) == null) tab [i] = newnode (Hash, Schlüssel, Wert, null); sonst {Knoten <k, v> e; K k; // Der Hash -Wert des ersten Knotens ist der gleiche und der Schlüsselwert wie der Einfügenschlüssel if (p.hash == Hash && ((k = P.Key) == Key || (Schlüssel! Nach Putval müssen Sie den gesamten Baum durchqueren. Wenn erforderlich, ändern Sie den Wert, um die Eigenschaften des roten und schwarzen Baumes e = (Treenode <k, v>) p) zu gewährleisten. Ende der Tabelle erstellen Sie dann einen neuen Knoten p.Next = newnode (Hash, Schlüssel, Wert, Null); // Nach dem Hinzufügen eines neuen Knotens, wenn die Anzahl der Knoten den Schwellenwert erreicht, konvertieren Sie die verknüpfte Liste in einen roten und schwarzen Baum, wenn (Bincount> = Treeify_Threshold - 1) // -1 für 1 -stresidif (tabin (tabin); Hash && ((k = E.Key) == Schlüssel || (Schlüssel! = NULL && key.equals (k))) break; Wert; Nachmittagsccess (e); Return OldValue;}} ++ modcount; if (++ Größe> Schwellenwert) Größe (); NachmittodeInSeration (evict); null return;}6: Größe der Größe der Größe
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) {if (oldcap> = maximum_capacity) {threshold = ganzzahl.MAX_VALUE; && oldcap> = default_initial_capacity) newthr = oldthr << 1; // Double Threshold} else if (Oldthr> 0) // Die anfängliche Kapazität wurde in ThresholdNewcap = Oldthr; else {// Null -Anfangsschwelle unter Verwendung von DefaultSnewcap = default_initial_capacity; * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node [newcap]; table = newtab; if (oldtab! Instanz von Treenode) ((Treenode <k, v>) e) .Split (this, newtab, j, oldcap); else {// ordernode <k, v> lohead = null, lotail = null; node <k, v> hihead = null, hitail = null; node <k, vlade {do {do {{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{{E., {e. {e. {e.next; {if (lotail == null) lohead = e; Elselotail.Next = e; lotail = e;} else {if (hitail == null) hihead = e; elendehitail.next = e; hitail = e;}} while ((e = next)! = null); !Das obige ist das relevante Wissen über die Analyse von Java8 HashMap über die vom Herausgeber vorgelegte Java8 -Hashmap. Ich hoffe, es wird für Sie hilfreich sein!