Lagerstruktur
Erstens wird Hashmap basierend auf einer Hash -Tabelle gespeichert. Es gibt ein Array darin. Wenn ein Element gespeichert werden soll, berechnen Sie zunächst den Hash -Wert seines Schlüssels und finden Sie das entsprechende Index des Elements im Array basierend auf dem Hash -Wert. Wenn an dieser Position kein Element vorhanden ist, geben Sie das aktuelle Element direkt ein. Wenn es ein Element gibt (in Erinnerung bleiben), verbinden Sie das aktuelle Element mit der Vorderseite des Elements A und geben Sie das aktuelle Element in das Array ein. In HashMap speichert das Array also den ersten Knoten der verlinkten Liste. Unten finden Sie ein Bild von Baidu Encyclopedia:
Wie in der obigen Abbildung gezeigt, handelt es sich bei jedem Element um ein Eingabefiel, wobei der Schlüssel und der Wert des Elements gespeichert sind, und es gibt einen Zeiger, mit dem auf das nächste Objekt verweist. Alle Schlüssel mit dem gleichen Hash -Wert (dh Konflikt) streiten sie mit einer verknüpften Liste miteinander zusammen, nämlich die Zipper -Methode.
Interne Variablen
// Standardkapazität statische endgültige int default_initial_capacity = 16; // Maximale Kapazität statische endgültige int maximum_capacity = 1 << 30; // Standard-Lastfaktor statische endgültige float default_load_factor = 0,75f; // Hast-Tabelle Transient-Eintrag <k, v> [] // Number der Taste-Val-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Intue-Größe; Lastfaktor des Hash -Array Final Float Loadfactor;
In den obigen Variablen bezieht sich die Kapazität auf die Länge der Hash -Tabelle, dh die Größe der Tabelle, und die Standardeinstellung beträgt 16. Der Lastfaktor -Lastfaktor ist der "vollständige Grad" der Hash -Tabelle, und die Dokumentation des JDK lautet: Folgendes:
Der Lastfaktor ist ein Maß dafür, wie voll die Hash -Tabelle ermöglicht wird, bevor seine Kapazität automatisch erhöht wird. Wenn die Anzahl der Einträge in der Hash -Tabelle das Produkt des Lastfaktors und die aktuelle Kapazität überschreitet, wird die Hash -Tabelle wieder aufgebaut (dh interne Datenstrukturen werden umgebaut), so dass die Hash -Tabelle ungefähr doppelt so viele Eimer -Anzahl enthält.
Die allgemeine Bedeutung ist: Der Ladefaktor ist das Maß dafür, wie voll die Hash -Tabelle vor der Ausdehnung installiert werden kann. Wenn die Anzahl der "Schlüsselwertpaare" in der Hash-Tabelle das Produkt der aktuellen Kapazität und den Ladefaktor überschreitet, wird die Hash-Tabelle Hashed (dh die interne Datenstruktur wieder aufgebaut) und die Kapazität der Hash-Tabelle wird etwa doppelt so hoch wie das ursprüngliche.
Wie aus der obigen Variablendefinition ersichtlich ist, beträgt der Standard -Ladefaktor default_load_factor 0,75. Je größer dieser Wert ist, desto höher ist die Raumnutzungsrate, aber die Abfragegeschwindigkeit (einschließlich des Get and Put) wird verlangsamt. Nach dem Verständnis des Ladefaktors kann es auch verstehen. Es entspricht tatsächlich dem Kapazitätsladungsfaktor.
Konstruktor
public hashmap (int initialCapacity, float loadfactor) {if (initialCapacity <0) neue illegalArgumentException ("illegale Anfangskapazität:" + initialCapacity); if (initialCapacity> maximum_capacity) initialCapacity = maximum_capacity; if (loadFactor <= 0 || float.isnan (loadFactor)) werfen neue illegalArgumentException ("illegaler Lastfaktor:" + loadfactor); // eine Leistung von 2> = initialCapacity int -Kapazität = 1 finden; während (Kapazität <initialCapacity) // die kleinste Leistung von 2 berechnen, die größer ist als die angegebene Kapazitätskapazität << = 1; this.loadfactor = loadFactor; threshold = (int) math.min (Kapazität * loadfactor, maximum_capacity + 1); Tabelle = neuer Eintrag [Kapazität]; // Raum für die Hash -Tabelle usealthashing = sun.misc.vm.isbooted () && (Kapazität> = Holder.Alternative_hashing_threshold); init ();}Es gibt mehrere Konstruktoren, und sie werden schließlich das oben genannte anrufen. Es akzeptiert zwei Parameter, eine ist die anfängliche Kapazität und der andere der Lastfaktor. Zu Beginn stellen wir zunächst fest, ob die Wertkombination legal ist und ob ein Problem vorhanden ist, wird eine Ausnahme ausgelöst. Wichtig ist die Berechnung der folgenden Kapazität, seine Logik besteht darin, die kleinste Leistung von 2 größer als die Initial -Capacity zu berechnen. In der Tat ist es, die Kapazität mehr als der angegebenen Anfangskapazität mehr oder gleich zu gestalten, aber dieser Wert muss ein exponentielles Vielfalt von 2 sein, was ein zentrales Problem darstellt. Der Grund dafür besteht hauptsächlich darin, Hash -Werte zu kartieren. Schauen wir uns zunächst die Hash -Methode in HashMap an:
endgültig int Hash (Objekt k) {int H = 0; if (uaealthashing) {if (kinstanceof String) {return sun.misc.hashing.stringhash32 ((String) k); } H = Hashseed; } h ^= k.hashcode (); // Diese Funktion stellt sicher, dass Hashcodes, die sich nur durch // konstante Multiplikatoren an jeder Bitposition unterscheiden, eine begrenzte // Anzahl von Kollisionen (ca. 8 bei Standardlastfaktor) haben. h ^ = (h >>> 20) ^ (h >>> 12); Rückgabe h ^ (h >>> 7) ^ (h >>> 4);Die Hash () -Methode berechnet den Hash -Wert des Schlüssels neu und verwendet relativ komplexe Bitoperationen. Ich kenne die spezifische Logik nicht. Wie auch immer, es ist definitiv eine bessere Methode, die Konflikte reduzieren kann oder so.
Der nachstehende Indexfor () ist das Index des Elements in der Hash -Tabelle basierend auf dem Hash -Wert. Im Allgemeinen verwenden Sie in einer Hash -Tabelle Hash -Werte, um die Tabellenlänge zu modulieren. Wenn die Länge (dh Kapazität) eine Leistung von 2 ist, ist H & (Länge-1) der gleiche Effekt. Darüber hinaus muss die Leistung von 2 eine gleichmäßige Zahl sein, dann ist es eine ungerade Zahl, und das letzte Bit des Binärs muss 1 sein. Dann kann das letzte Bit H & (Länge-1) 1 oder 0 sein, was gleichmäßig hashiert werden kann. Wenn die Länge eine ungerade Zahl ist, ist die Länge-1 eine gleichmäßige Zahl und das letzte Bit ist 0. Zu diesem Zeitpunkt ist das letzte Bit H & (Länge-1) nur 0, und alle resultierenden Indexs sind gleichmäßig, so dass die Hälfte des Raums verschwendet wird. Daher muss die Kapazität in HashMap eine Leistung von 2. sein.
Eingabefiel
Die Schlüsselwertpaare in HashMap werden in Einstiegsobjekte eingekapselt, bei denen es sich um eine interne Klasse in HashMap handelt. Schauen wir uns die Implementierung an:
statischer Klasseneintrag <k, v> implementiert map.Entry <k, v> {endgültig k key; V Wert; Eintrag <k, v> Weiter; int Hash; Eintrag (int H, k k, v v, Eintrag <k, v> n) {value = v; Weiter = n; Key = k; Hash = H; } public Final k getKey () {return key; } public final v getValue () {Rückgabewert; } public final v setValue (v newValue) {v oldValue = value; Wert = newValue; kehren Sie OldValue zurück; } public Final Boolean Equals (Objekt o) {if (! (o Instanceof map.Entry)) Return false; MAP.Entry e = (map.Entry) o; Objekt K1 = getKey (); Objekt k2 = e.getkey (); if (k1 == k2 || (k1! = null && k1.equals (k2))) {Objekt v1 = getValue (); Objekt v2 = e.getValue (); if (v1 == v2 || (v1! = null && v1.equals (v2)) return true; } return false; } public Final int hashCode () {return (key == null? 0: key.hashCode ()) ^ (value == null? 0: value.hashCode ()); } public Final String toString () {return getKey () + "=" + getValue (); } void recordAccess (Hashmap <k, v> m) {}}Die Implementierung dieser Klasse ist einfach und leicht zu verstehen. Methoden wie GetKey (), GetValue () werden für den Anruf bereitgestellt. Um die Gleichheit zu bestimmen, ist es notwendig, dass sowohl der Schlüssel als auch der Wert gleich sind.
Betrieb setzen
Setzen Sie zuerst vor, bevor Sie es erhalten. Schauen Sie sich zuerst die Put () -Methode an:
public v put (k key, v value) {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ückgeben;}Bestimmen Sie bei dieser Methode zunächst, ob der Schlüssel null ist. Wenn ja, rufen Sie PutFornullKey () -Methode auf, was bedeutet, dass HashMap den Schlüssel null ist (tatsächlich kann Wert sein). Wenn nicht NULL, berechnen Sie den Hash -Wert und erhalten Sie den Index in die Tabelle. Gehen Sie dann zur entsprechenden verknüpften Liste, um abzufragen, ob bereits der gleiche Schlüssel vorhanden ist. Wenn es bereits vorhanden ist, wird der Wert direkt aktualisiert. Andernfalls rufen Sie AddEntry () -Methoden für das Einfügen auf.
Schauen Sie sich die Methode putFornullkey () an:
private v putfornullkey (v value) {für (Eintrag <k, v> e = table [0]; e! = null; e = e.Next) {if (e.Key == null) {v oldValue = e.Value; E. value = Wert; E. recordaccess (this); kehren Sie OldValue zurück; }} modcount ++; AddEntry (0, Null, Wert, 0); Null zurückgeben;}Es ist ersichtlich, dass der Wert, wenn der Schlüssel null ist, der Wert aktualisiert wird, wenn er vorhanden ist, andernfalls addentry () zum Einfügen aufgerufen wird.
Im Folgenden ist die Implementierung der AddEntry () -Methode:
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 ++;}Bestimmen Sie zunächst, ob die Kapazität erweitert werden soll (Erweiterungskapazität wird den Einweiswert neu berechnen und das Element kopieren), dann das Array -Index berechnen und schließlich das Element mit der Header Insertion -Methode in createEntry () einfügen.
Betrieb erhalten
public v get (Objektschlüssel) {if (key == null) return getFornullKey (); Eintrag <k, v> Eintrag = GetEntry (Schlüssel); NULL zurückgeben == Eintrag? NULL: Eintrag.GetValue ();} private v getFornullkey () {für (Eintrag <k, v> e = table [0]; e! } return null;} endgültiger Eintrag <k, v> GetEntry (Objektschlüssel) {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;}Dies ist einfacher als put (). Sie müssen auch feststellen, ob der Schlüssel null ist, und dann die Traversal -Abfrage der verlinkten Liste.
Leistungsoptimierung
HashMap ist eine effiziente und universelle Datenstruktur, die in jedem Java -Programm überall zu sehen ist. Lassen Sie uns zuerst einige Grundkenntnisse vorstellen. Wie Sie vielleicht auch wissen, verwendet HashMap die SchlüsselhashCode () und Equals () -Stasten, um die Werte in verschiedene Eimer zu unterteilen. Die Anzahl der Eimer ist normalerweise etwas größer als die Anzahl der Datensätze in der Karte, so dass jeder Eimer weniger Werte (vorzugsweise eine) enthält. Beim Durchsuchen von Schlüsseln können wir schnell einen Eimer (mit HashCode () mit dem Modulo der Anzahl der Eimer) und des Objekts finden, nach dem wir in konstanter Zeit suchen.
Sie sollten all diese Dinge bereits wissen. Sie können auch wissen, dass Hash -Kollisionen katastrophale Auswirkungen auf die Leistung von HashMap haben können. Wenn mehrere HashCode () -Werte in denselben Eimer fallen, werden diese Werte in einer verknüpften Liste gespeichert. Im schlimmsten Fall werden alle Schlüssel in denselben Eimer zugeordnet, sodass der Hashmap in eine verknüpfte Liste entgeführt wird - die Suchzeit stammt von O (1) bis O (n). Lassen Sie uns zunächst die Leistung von HashMap in Java 7 und Java 8 unter normalen Umständen testen. Um das Verhalten der HashCode () -Methode zu kontrollieren, definieren wir eine Schlüsselklasse wie folgt:
Klassenschlüssel implementiert vergleichbar <Key> {private endgültige int value; key (int value) {this.value = value;}@oversidepublic int vergleicheto (key o) {return integer.comPare (this.value, O.Value);}@oversidepublic boolean (Object. Object. {if) {if (this ==). O.GetClass ()) return false; taste key = (taste) o; return value == key.value;}@oversidepublic int HashCode () {return value;}}Die Implementierung der Schlüsselklasse ist ziemlich Standard: Sie schreibt die Equals () -Methode um und bietet eine ziemlich anständige HashCode () -Methode. Um übermäßiges GC zu vermeiden, habe ich das unveränderliche Schlüsselobjekt zwischengespeichert, anstatt es jedes Mal wieder zu erstellen:
Klassenschlüssel implementiert vergleichbare <Key> {public class Keys {public static final int max_key = 10_000_000; Keys_Cache [Wert];}Jetzt können wir mit dem Testen beginnen. Unser Benchmark verwendet kontinuierliche Schlüsselwerte, um Hashmaps unterschiedlicher Größen zu erstellen (Multiplikator für 10 von 1 bis 1 Million). Im Test werden wir auch Schlüssel verwenden, um die Zeit für Hashmaps unterschiedlicher Größen zu suchen und zu messen:
importieren com.google.caliper.param; import com.google.caliper.runner; import com.google.caliper HashMap <> (mapsize); für (int i = 0; i <mapsize; ++ i) {map.put (keys.of (i), i);}} public void Timemapget (int reps) {für (int i = 0; i <reps; i ++) {map.get (keys.f.- ig.Interessanterweise ist Java 8 in diesem einfachen Hashmap.get () 20% schneller als Java 7. Die Gesamtleistung ist ebenfalls recht gut: Obwohl es in HashMap eine Million Rekorde gibt, dauerte eine einzelne Abfrage nur weniger als 10 Nanosekunden, was ungefähr 20 CPU -Zyklen auf meiner Maschine entspricht. Sehr schockierend! Aber das wollen wir nicht messen.
Angenommen, es gibt einen schlechten Schlüssel, es gibt immer den gleichen Wert zurück. Dies ist das schlimmste Szenario, und Sie sollten HashMap überhaupt nicht verwenden:
Klassenschlüssel implementiert vergleichbar <schlüssel> {//...@overridepublic int HashCode () {return 0;}}Die Ergebnisse von Java 7 werden erwartet. Wenn die Größe von Hashmap wächst, wird der Aufwand der Get () -Methode immer größer. Da sich alle Datensätze in der ultra-langen verlinkten Liste im selben Eimer befinden, muss die Hälfte der Liste durchsucht werden. Aus der Figur ist daher ersichtlich, dass seine zeitliche Komplexität O (n) ist.
Java 8 erzielt jedoch viel besser! Es ist eine Protokollkurve, daher ist seine Leistung besser Größenordnungen. Trotz des schlimmsten Falles von schweren Hash -Kollisionen hat dieselbe Benchmark eine zeitliche Komplexität in JDK8 von O (logn). Wenn Sie sich die Kurve von JDK 8 allein ansehen, wird sie klarer. Dies ist eine logarithmische lineare Verteilung:
Warum gibt es eine so großartige Leistungsverbesserung, obwohl das große O -Symbol hier verwendet wird (Big O beschreibt die asymptotische Obergrenze)? Tatsächlich wurde diese Optimierung in JEP-180 erwähnt. Wenn der Datensatz in einem Eimer zu groß ist (derzeit Treeify_Threshold = 8), ersetzt HashMap es dynamisch durch eine spezielle Treemap -Implementierung. Dies führt zu besseren Ergebnissen, O (logn), nicht schlecht o (n). Wie funktioniert es? Die Datensätze, die dem Schlüssel entsprechen, mit dem Konflikte vorhanden sind, werden einfach an eine verknüpfte Liste angehängt, und diese Datensätze können nur durch Traversal gefunden werden. Nachdem HashMap diesen Schwellenwert überschritten hat, beginnt sie jedoch, die Liste auf einen binären Baum zu verbessern, wobei der Hash -Wert als Zweigvariable des Baumes verwendet wird. Wenn die beiden Hash -Werte nicht gleich sind, aber auf denselben Eimer hinweisen, wird der größere in das rechte Teilbaum eingefügt. Wenn die Hash -Werte gleich sind, hofft HashMap, dass der Schlüsselwert am besten durch die vergleichbare Schnittstelle implementiert wird, damit er in der Reihenfolge eingefügt werden kann. Dies ist für den Schlüssel von Hashmap nicht erforderlich, ist aber natürlich das Beste, wenn es umgesetzt wird. Wenn diese Schnittstelle nicht implementiert ist, sollten Sie nicht erwarten, dass bei schweren Hash -Kollisionen Leistungsverbesserungen erzielt werden.
Wie nutzen diese Leistungsverbesserung? Beispielsweise kann ein böswilliges Programm, wenn es weiß, dass wir einen Hashing -Algorithmus verwenden, eine große Anzahl von Anfragen sendet, was zu schwerwiegenden Hash -Kollisionen führt. Anschließend kann der ständige Zugriff auf diese Schlüssel die Leistung des Servers erheblich beeinflussen, was zu einer Ablehnung des Dienstangriffs (DOS) führt. Der Sprung von O (n) nach O (logn) in JDK 8 kann ähnliche Angriffe effektiv verhindern und gleichzeitig die Vorhersagbarkeit der HashMap -Leistung verbessern. Ich hoffe, diese Verbesserung wird Ihren Chef schließlich davon überzeugen, sich auf ein Upgrade auf JDK 8 zuzustimmen.
Die für den Test verwendete Umgebung lautet: Intel Core i7-3635qm @ 2,4 GHz, 8 GB Speicher, SSD-Festplatte unter Verwendung von Standard-JVM-Parametern, die auf einem 64-Bit-Windows 8.1-System ausgeführt werden.
Zusammenfassen
Die grundlegende Implementierung von HashMap ist wie oben analysiert, und schließlich wird die Zusammenfassung erfolgt: