Die meisten Java -Entwickler verwenden MAP, insbesondere HashMap. HashMap ist eine einfache, aber leistungsstarke Möglichkeit, Daten zu speichern und zu erhalten. Aber wie viele Entwickler wissen, wie HashMap intern funktioniert? Vor ein paar Tagen habe ich viel Quellcode von Java.util.hasmap (einschließlich Java 7 und Java 8) gelesen, um ein tiefes Verständnis dieser grundlegenden Datenstruktur zu erlangen. In diesem Beitrag werde ich die Implementierung von java.util.hashmap erläutern, die neuen Funktionen in der Implementierung von Java 8 beschreiben und bei der Verwendung von HashMap Leistung, Speicher und einige bekannte Probleme diskutieren.
Interner Speicher
Die Java -Hashmap -Klasse implementiert die Karte <K, v> Schnittstelle. Die Hauptmethoden in dieser Schnittstelle umfassen:
V Put (K -Schlüssel, V -Wert) V GET (Objektschlüssel) v entfernen (Objektschlüssel) Boolean enthält KEY (Objektschlüssel)
HashMap verwendet einen internen Klasseneintrag <k, v>, um Daten zu speichern. Diese innere Klasse ist ein einfaches Schlüsselwertpaar mit zwei zusätzlichen Daten:
Ein Verweis auf einen anderen Eintrag, damit HashMap Objekte wie Linklisten speichern kann.
Ein Hash -Wert, der verwendet wird, um den Schlüssel darzustellen. Das Speichern dieses Wertes kann verhindern, dass HashMap den Hash -Wert regeneriert, der dem Schlüssel jedes Mal entspricht, wenn er benötigt wird.
Hier ist ein Teil des Codes für Eintrag <k, v> unter Java 7:
Statische Klasseneingabe <k, v> implementiert map.Entry <k, v> {endgültiger K -Schlüssel; V -Wert; Eintrag <k, v> Weiter; int Hash;…}HashMap speichert Daten in mehreren unidirektionalen Listen (manchmal auch als Buckets oder Container -Orbins bezeichnet). Alle Listen sind in einem Eintragsarray (Eintrag <k, v> [] Array) registriert, und die Standardlänge dieses internen Arrays beträgt 16.
Die folgende Abbildung beschreibt die interne Speicherung einer HashMap -Instanz, die ein Array von nullbaren Objekten enthält. Jedes Objekt ist mit einem anderen Objekt verbunden und bildet somit eine verknüpfte Liste.
Alle Schlüssel mit dem gleichen Hash -Wert werden in derselben verknüpften Liste (Eimer) platziert. Tasten mit unterschiedlichen Hashes können im selben Eimer enden.
Wenn der Benutzer aufruft (K -Schlüssel, V -Wert) oder GET (Objektschlüssel), berechnet das Programm den Index des Eimers, in dem sich das Objekt befinden sollte. Das Programm iteriert dann über die entsprechende Liste, um das Eintragsobjekt mit demselben Schlüssel zu finden (mit der Equals () -Methode des Schlüssels).
Im Falle des Aufrufens von Get () gibt das Programm das dem Wert entsprechende Eintragsobjekt zurück (falls das Eintragsobjekt existiert).
Damit der Aufruf (k-Schlüssel, v-Wert) der Eintragsobjekt vorhanden ist, ersetzt das Programm den Wert durch einen neuen Wert, da das Programm ansonsten einen neuen Eintrag (Schlüssel und Wert im Parameter) am Kopf der One-Way-Linked-Liste erstellt.
Der Index des Bucket (verknüpfte Liste) wird durch 3 Schritte der Karte erzeugt:
Holen Sie sich zuerst den Hash -Code des Schlüssels.
Das Programm wiederholt den Hash -Code, um schlechte Hash -Funktionen für Schlüssel zu blockieren, da dies das Potenzial hat, alle Daten auf denselben Index (Bucket) des internen Arrays zu setzen.
Das Programm nimmt den doppelten Hash -Code auf und verwendet eine Bitmaske der Arraylänge (mindestens 1) dafür. Dieser Vorgang stellt sicher, dass der Index nicht größer ist als die Größe des Arrays. Sie können es sich als kalkulierte optimierte Modulfunktion vorstellen.
Hier ist der Quellcode zum Generieren des Index:
// Die "Rehash" -Funktion in Java 7, die den Hashcode des keystatischen Int Hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); zurück h ^ (h >>> 7) ^ (h >>> 4); 0: (h = key.hashCode ()) ^ (h >>> 16);} // Die Funktion, die den Index aus dem wiederhergestellten Hashstatic Int indexfor (int h, int länge) {return H & (Länge-1);};} zurückgibt;}Um effizienter zu arbeiten, muss die Größe des inneren Arrays eine Kraft von 2 sein. Lassen Sie uns sehen, warum:
Unter der Annahme, dass die Länge des Arrays 17 beträgt, beträgt der Wert der Maske 16 (Arraylänge-1). Die binäre Darstellung von 16 beträgt 0… 010000, so dass für jeden Wert H das Ergebnis von "H & 16" 16 oder 0 beträgt. Dies bedeutet, dass Arrays mit Länge 17 nur auf zwei Eimer angewendet werden können: Einer ist 0 und der andere ist 16, was nicht sehr effizient ist. Wenn Sie jedoch die Länge des Arrays auf eine Leistung von 2 festlegen, beispielsweise 16, funktioniert die bitweise Indexierung auf "H & 15". Die binäre Darstellung von 15 beträgt 0… 001111, und die Wertausgabe nach der Indexformel kann zwischen 0 und 15 liegen, so dass ein Array von Länge 16 vollständig verwendet werden kann. Zum Beispiel:
Wenn H = 952, ist seine binäre Darstellung 0..01110111000 und der entsprechende Index ist 0… 01000 = 8
Wenn H = 1576, ist seine binäre Darstellung 0..011000101000 und der entsprechende Index ist 0… 01000 = 8
Wenn H = 12356146, ist seine binäre Darstellung 0..010111001000101010010, der entsprechende Index beträgt 0… 00010 = 2
Wenn H = 59843, ist seine binäre Darstellung 0..011101001000011, sein entsprechender Index beträgt 0… 00011 = 3
Dieser Mechanismus ist für den Entwickler transparent: Wenn er einen Hashmap mit Länge 37 auswählt, wählt die Karte automatisch den nächsten Leistungswert von mehr als 37 (64) als Länge des internen Arrays aus.
Automatisch Änderung
Nach Erhalt des Index greifen die Methoden GET (), Put () oder REME () auf die entsprechende verlinkte Liste zu, um festzustellen, ob das Eingabefiel für den angegebenen Schlüssel bereits vorhanden ist. Ohne Änderung kann dieser Mechanismus Leistungsprobleme verursachen, da diese Methode über die gesamte Liste durchträgt, ob das Eintragsobjekt vorhanden ist. Angenommen, die Länge des internen Arrays benötigt den Standardwert von 16 und Sie müssen 2.000.000 Datensätze speichern. Im besten Fall werden 125.000 Eingangsobjekte pro verknüpfter Liste (2.000.000/16) stattfinden. Die Methoden GET (), REME () und Put () erfordern bei jeder Ausführung 125.000 Iterationen. Um dies zu vermeiden, kann HashMap die Länge des internen Arrays erhöhen und so sicherstellen, dass nur wenige Einstiegsobjekte in der verknüpften Liste aufbewahrt werden.
Wenn Sie eine HashMap erstellen, können Sie eine Anfangslänge und einen Lastfaktor über den folgenden Konstruktor angeben:
</pre> öffentliches HashMap (int initialCapacity, Float loadFactor) <Pre>
Wenn Sie keine Parameter angeben, beträgt der Standard -InitialCapacity -Wert 16 und der Standard -Loadfaktorwert 0,75. InitialCapacity repräsentiert die Länge der verknüpften Liste des internen Arrays.
Wenn Sie die Put (…) -Methode verwenden, um der Karte ein neues Schlüsselwertpaar hinzuzufügen, überprüft die Methode, ob die Länge des inneren Arrays erhöht werden muss. Um dies zu erreichen, speichert die Karte 2 Daten:
Kartengröße: Es repräsentiert die Anzahl der Datensätze in HashMap. Wir aktualisieren den Wert, wenn wir ihn in die HashMap einfügen oder löschen.
Schwellenwert: Es entspricht der Länge des internen Array*Loadfactors, und dieser Schwellenwert wird auch jedes Mal, wenn die Länge des internen Arrays eingestellt wird, gleichzeitig aktualisiert.
Vor dem Hinzufügen eines neuen Eintragsobjekts prüft die Put (…) -Methode, ob die Größe der aktuellen Karte größer ist als der Schwellenwert. Wenn es größer als der Schwellenwert ist, erzeugt es ein neues Array mit der doppelten Länge des aktuellen internen Arrays. Da sich die Größe des neuen Arrays geändert hat, ändert sich auch die Indexfunktion (dh das Bitbetriebs -Ergebnis, das den Hash -Wert des Schlüssels & (Arraylänge -1) zurückgibt) ebenfalls. Durch die Größe des Arrays wird zwei neue Eimer (verknüpfte Listen) erstellt und alle vorhandenen Eintragsobjekte in den Eimer zuzuordnen. Das Ziel der Anpassung der Arraygröße ist es, die Größe der verknüpften Liste zu verringern und damit die Ausführungszeit von Put (), REME () und GET () zu verkürzen. Für alle Einstiegsobjekte, die Tasten mit dem gleichen Hash -Wert entsprechen, werden sie nach der Größenänderung demselben Eimer zugewiesen. Wenn die Hash -Werte der beiden Einstiegsobjekte jedoch unterschiedlich sind, sie sich jedoch vor der Einstellung auf demselben Eimer befanden, gibt es keine Garantie dafür, dass sie sich noch auf demselben Eimer befinden.
Dieses Bild beschreibt die Situation der internen Arrays vor der Einstellung und nach der Einstellung. Vor dem Einstellen der Array -Länge muss die Karte über eine verknüpfte Liste mit 5 Elementen iterieren, um das Eingabefiel E zu erhalten. Nach der Einstellung der Arraylänge muss die gleiche GET () -Methode nur eine verknüpfte Liste mit 2 Elementen durchqueren. Die Laufgeschwindigkeit der GET () -Methode nach der Einstellung der Arraylänge wird also um das 2 -fache erhöht.
Fadensicherheit
Wenn Sie mit HashMap bereits sehr vertraut sind, wissen Sie definitiv, dass es nicht sicher ist, aber warum? Angenommen, Sie haben einen Autor -Thread, der nur vorhandene Daten in die Karte einfügt, einen Leser -Thread, der Daten aus der Karte liest. Warum funktioniert es also nicht?
Da unter dem automatischen Größenmechanismus der Thread versucht, ein Objekt hinzuzufügen oder zu erhalten, kann die Karte den alten Indexwert verwenden, so dass der neue Eimer, in dem sich das Eingabefiel befindet, nicht gefunden wird.
Im schlimmsten Fall beginnen 2 Threads gleichzeitig 2 Threads gleichzeitig ein Einfügen von 2 Put () gleichzeitig und das Array ändern sich automatisch. Da zwei Threads gleichzeitig die verknüpfte Liste ändern, ist es möglich, dass die Karte in der internen Schleife einer verknüpften Liste beendet. Wenn Sie versuchen, Daten aus einer Liste mit einer inneren Schleife zu erhalten, endet die Get () -Methode niemals.
Hashtable bietet eine thread-sichere Implementierung, die verhindert, dass die oben genannte stattfindet. Da jedoch alle synchronen CRUD -Operationen sehr langsam sind. Wenn beispielsweise Thread 1 -Aufrufe GET (KEY1), dann Thread 2 -Aufrufe GET (KEY2) und Thread 2 -Aufrufe GET (KEY3), können zu einem bestimmten Zeitpunkt nur 1 Thread seinen Wert abrufen, aber alle 3 Threads können auf diese Daten gleichzeitig zugreifen.
Seit Java 5 haben wir eine bessere und fadensichere Hashmap-Implementierung: Concurrenthashmap. Bei ConcurrentMap werden nur Eimer synchronisiert. Wenn mehrere Threads nicht denselben Eimer verwenden oder das interne Array ändern, können sie gleichzeitig die Methoden Get (), REMET () oder Put () aufrufen. In einer Multithread -Anwendung ist dieser Ansatz eine bessere Wahl.
Invarianz der Anleihen
Warum ist es eine gute Implementierung, Strings und Ganzzahlen als Schlüssel zu HashMap zu verwenden? Hauptsächlich, weil sie unveränderlich sind! Wenn Sie selbst eine Klasse selbst als Schlüssel erstellen, aber Sie können nicht garantieren, dass die Klasse unveränderlich ist, verlieren Sie möglicherweise Daten innerhalb von HashMap.
Schauen wir uns die folgenden Anwendungsfälle an:
Sie haben einen Schlüssel, dessen interner Wert "1" ist.
Wenn Sie ein Objekt in einen HashMap einfügen, ist der Schlüssel "1".
HashMap generiert Hash -Werte aus dem Hash -Code des Schlüssels (d. H. "1").
MAP speichert diesen Hash -Wert im neu erstellten Datensatz.
Sie ändern den internen Wert des Schlüssels und ändern ihn in "2".
Der Hash -Wert des Schlüssels hat sich geändert, aber Hashmap weiß das nicht (da der alte Hash -Wert gespeichert wird).
Sie versuchen, das entsprechende Objekt durch den geänderten Schlüssel zu erhalten.
MAP berechnet den Hash -Wert des neuen Schlüssels (d. H. "2"), um die verknüpfte Liste (Bucket) zu finden, in der sich das Eingabefiel befindet.
Fall 1: Da Sie den Schlüssel geändert haben, versucht MAP, im falschen Eimer nach dem Eintragsobjekt zu suchen, es wird jedoch nicht gefunden.
Fall 2: Sie haben das Glück, dass der von der modifizierte Schlüssel erzeugte Eimer und der vom alte Schlüssel erzeugte Eimer gleich sind. Die Karte durchquert dann die verknüpfte Liste und ein Eintragsobjekt mit demselben Schlüssel wurde gefunden. Um den Schlüssel zu finden, vergleichen MAP zunächst den Hash -Wert des Schlüssels, indem Sie die Equals () -Methode aufrufen. Da der modifizierte Schlüssel unterschiedliche Hash -Werte generiert (die alten Hash -Werte werden im Datensatz gespeichert), kann MAP keine Möglichkeit haben, das entsprechende Eintragsobjekt in der verlinkten Liste zu finden.
Hier ist ein Java-Beispiel, in dem wir zwei Schlüsselwertepaare in die Karte einfügen. Anschließend modifiziere ich den ersten Schlüssel und versuche, die beiden Objekte zu erhalten. Sie werden feststellen, dass nur das zweite Objekt, das von der Karte zurückgegeben wurde, das erste Objekt in der HashMap "verloren" wurde:
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() {return i;}@Overridepublic boolean equals(Object obj) {if (obj Instanceof mykey) {return i.equals (((mykey) obj) .i);} elSereturn false;}} Karte <MyKey, String> myMap = new Hashmap <> (); MyKey key1 = new Mykey (1); Mykey Key2 = New Mykey (2); Ändern von KEY1Key1.Seti (3); String test1 = MyMap.get (Key1); String test2 = mymap.get (Key2); System.out.println ("test1 =" + test1 + "test2 =" + test2);}}Die Ausgabe des obigen Codes lautet "test1 = null test2 = test 2". Wie wir erwarten, hat MAP nicht die Fähigkeit, den String 1 zu erhalten, der dem modifizierten Schlüssel 1 entspricht.
Verbesserungen in Java 8
In Java 8 wurde die interne Implementierung in HashMap stark geändert. In der Tat verwendet Java 7 1000 Codezeilen, um ihn zu implementieren, während Java 8 2000 Codezeilen verwendet. Das meiste, was ich zuvor beschrieben habe, ist in Java 8 noch korrekt, außer dass die Listen mit verknüpften Listen zum Speichern von Eingangsobjekten verwendet werden. In Java 8 verwenden wir immer noch Arrays, wird jedoch im Knoten gespeichert, der dieselben Informationen wie das vorherige Eintragsobjekt enthält und auch eine verknüpfte Liste verwendet:
Hier ist ein Teil des Code, der den Knoten in Java 8 implementiert:
statischer Klassenknoten <k, v> implementiert map.Entry <k, v> {endgültig int Hash; endgültiger K -Schlüssel; V -Wert; Knoten <k, v> Weiter;Was ist der große Unterschied zu Java 7? Nun, der Knoten kann auf Treenode ausgedehnt werden. Treenode ist eine Datenstruktur eines rot -schwarzen Baumes, der weitere Informationen speichern kann, sodass wir ein Element unter der Komplexität von O (log (n)) hinzufügen, löschen oder erhalten können. Das folgende Beispiel beschreibt alle von Treenode gespeicherten Informationen:
statische endgültige Klasse Treenode <k, v> erweitert linkedHasMap.Entry <k, v> {endgültig int Hash; // von Knoten <k, v> endgültiger K -Schlüssel; // vom Knoten <k, v> v Wert erbelt; // von Knoten <k, v> Knoten <k, v> als nächstes geerbt; // vom Knoten <k, v> Eintrag <k, v> vor, nach, nach, // von linkedHashMap.Entry <k, v> übergeordnet; treenode <k, v> links; Treenode <k, v> rechts; Treenode <k, v> prev; boolean rot geerbt;Rote und schwarze Bäume sind selbstausgleiche binäre Suchbäume. Sein interner Mechanismus stellt sicher, dass seine Länge immer log (n) ist, unabhängig davon, ob wir Knoten hinzufügen oder löschen. Der wichtigste Vorteil der Verwendung dieser Art von Baum besteht darin, dass viele Daten in der internen Tabelle denselben Index (Bucket) haben. Zu diesem Zeitpunkt beträgt die Komplexität der Suche des Baumes o (log (n)), und für die verknüpfte Liste ist die Komplexität O (n) für die gleiche Operation.
Wie Sie sehen können, speichern wir mehr Daten im Baum als verknüpfte Listen. Gemäß dem Vererbungsprinzip kann die interne Tabelle Knoten (verknüpfte Liste) oder Treenode (rot und schwarzer Baum) enthalten. Oracle beschließt, diese beiden Datenstrukturen gemäß den folgenden Regeln zu verwenden:
- Für den angegebenen Index (Bucket) in der internen Tabelle wird die verknüpfte Liste in einem roten und schwarzen Baum um konvertiert, wenn die Anzahl der Knoten mehr als 8 beträgt.
- Für den angegebenen Index (Bucket) in der internen Tabelle wird der rote und schwarze Baum, wenn die Anzahl der Knoten weniger als 6 beträgt, in eine verknüpfte Liste umgewandelt.
Dieses Bild beschreibt ein internes Array in einem Java 8 -HashMap, das sowohl Baum (Bucket 0) als auch verknüpfte Listen (Bucket 1, 2 und 3) enthält. Eimer 0 ist eine Baumstruktur, da er mehr als 8 Knoten enthält.
Speicheraufwand
Java 7
Die Verwendung von HashMap verbraucht etwas Speicher. In Java 7 enthält HashMap Schlüsselwertpaare in Eingangsobjekte, ein Eintragsobjekt enthält die folgenden Informationen:
Verweis auf den nächsten Datensatz Ein vorbereiteter Hash-Wert (Ganzzahl)
Ein Verweis auf einen Schlüssel und ein Verweis auf einen Wert
Zusätzlich verwendet HashMap in Java 7 ein internes Array von Eingangsobjekten. Angenommen, ein Java 7 -Hashmap enthält N -Elemente und sein internes Array hat Kapazität, dann ist der zusätzliche Speicherverbrauch ungefähr:
sizeof (Ganzzahl)* n + sizeof (referenz)* (3* n + c)
In:
Die Größe einer Ganzzahl beträgt 4 Bytes
Die Größe der Referenz hängt vom JVM, dem Betriebssystem und dem Prozessor ab, beträgt jedoch normalerweise 4 Bytes.
Dies bedeutet, dass der Gesamtspeicheraufwand normalerweise 16 * N + 4 * Kapazitätsbytes beträgt.
Hinweis: Nach der automatischen Größe der MAP ist der Wert der Kapazität die nächst kleinste Leistung von 2 größer als N.
HINWEIS: Ab Java 7 nimmt HashMap einen faulen Lademechanismus an. Dies bedeutet, dass das interne Array (verbrauchte 4* -Kapazitätsbytes), die im Speicher nicht zugewiesen wird, bevor wir die Put () -Methode verwenden, auch wenn Sie die Größe für HashMap angeben.
Java 8
In Java 8 -Implementierungen wird die Berechnung des Speicherverbrauchs komplizierter, da der Knoten dieselben Daten wie die Eingabe speichern oder 6 Referenzen und eine boolesche Eigenschaft hinzufügen kann (angeben, ob es sich um einen Treenode handelt).
Wenn alle Knoten nur Knoten sind, ist der von Java 8 Hashmap verzehrte Speicher dieselbe wie die von Java 7 Hashmap konsumierte.
Wenn alle Knoten Treenode sind, wird der von Java 8 Hashmap verzehrte Speicher:
N * sizeof (Ganzzahl) + n * sizeof (boolean) + sizeof (referenz) * (9 * n + Kapazität)
In den meisten Standard -JVMs beträgt das Ergebnis der obigen Formel 44 * N + 4 * Kapazitätsbytes.
Leistungsprobleme
Asymmetrischer Hashmap gegen ausgewogene Hashmap
In dem besten Fall haben sowohl die Methoden Get () als auch put () nur o (1) Komplexität. Wenn Sie sich jedoch nicht um die Hash -Funktion des Schlüssels kümmern, können Ihre Methoden für Put () und Get () sehr langsam ausgeführt werden. Die effiziente Ausführung von Put () und GET () -Methoden hängt davon ab, dass die Daten verschiedenen Indizes des internen Arrays (Bucket) zugeordnet werden. Wenn die Hash -Funktion des Schlüssels nicht ordnungsgemäß gestaltet ist, erhalten Sie eine asymmetrische Partition (unabhängig von der Größe der internen Daten). Alle Methoden Put () und GET () verwenden die größte verlinkte Liste, die nur langsam ausgeführt werden kann, da die Iteration aller Datensätze in der verlinkten Liste erforderlich ist. Im schlimmsten Fall (wenn sich die meisten Daten auf demselben Eimer befinden) wird Ihre Zeitkomplexität O (n).
Hier ist ein visuelles Beispiel. Der erste Diagramm beschreibt eine asymmetrische Hashmap und der zweite Diagramm beschreibt eine ausgeglichene Hashmap.
SCWEWEDHASHMAP
In diesem asymmetrischen Hashmap dauert es Zeit, die Methoden Get () und put () auf Bucket 0 zu betreiben. Aufnehmen K. 6 Iterationen.
In diesem ausgewogenen HashMap benötigen sie nur 3 Iterationen, um den Datensatz K zu erhalten. Diese beiden Hashmaps speichern die gleiche Datenmenge, und die internen Arrays haben die gleiche Größe. Der einzige Unterschied ist die Hash -Funktion des Schlüssels, mit der Datensätze auf verschiedene Eimer verteilen.
Hier ist ein extremes Beispiel in Java, in dem ich eine Hash -Funktion verwende, um alle Daten in dieselbe verknüpfte Liste (Eimer) zu setzen, und dann habe ich 2.000.000 Datenstücke hinzugefügt.
public class test {public static void main (String [] args) {class myKey {Integer i; public myKey (Integer i) {this.i = i;}@oversidepublic int HashCode () {return 1;}@oversidepublic booolean Equals (Objekt Object obj) {{}}} Datum = Neues Datum. HashMap <> (2_500_000,1); für (int i = 0; i <2_000_000; i ++) {MYMAP.PUT (neuer MyKey (i), "test"+i);} Date end = new Date (); System.out.Println ("Dauer (MS)"+(end.Getime ()-begin.Meine Maschinenkonfiguration ist CORE I5-2500K @ 3,6G, und es dauert mehr als 45 Minuten, um unter Java 8U40 zu laufen (ich habe den Vorgang nach 45 Minuten gestoppt). Wenn ich den gleichen Code ausführe, aber die Hash -Funktion wie diese verwende:
@Overridepublic int HashCode () {int key = 2097152-1; Rückgabeschlüssel+2097152*i;}Es dauert 46 Sekunden, um es zu laufen, was viel besser ist als zuvor! Die neue Hash -Funktion ist vernünftiger als die alte Hash -Funktion bei der Verarbeitung von Hash -Partitionen. Wenn Sie also die Put () -Methode aufrufen, ist es schneller. Wenn Sie jetzt den gleichen Code ausführen, aber die Hash -Funktion unten verwenden, bietet er eine bessere Hash -Partition:
@Overridepublic int HashCode () {return i;}Jetzt dauert es nur 2 Sekunden!
Ich hoffe, Sie können erkennen, wie wichtig Hash -Funktionen sind. Wenn Sie den gleichen Test auf Java 7 durchführen, wird die erste und zweite schlechter (da die Put () -Methode in Java 7 die Komplexität von O (n) hat, während die Komplexität in Java 8 o (log (n)) hat.
Bei Verwendung von HashMap müssen Sie eine Hash -Funktion für die Schlüssel finden, die die Schlüssel auf den wahrscheinlichsten Eimer verteilen können. Dazu müssen Sie Hash -Konflikte vermeiden. Ein String -Objekt ist ein sehr guter Schlüssel, da es eine gute Hash -Funktion hat. Ganzzahl ist auch gut, weil sein Hash sein eigener Wert ist.
Overhead Größenänderung
Wenn Sie eine große Datenmenge speichern müssen, sollten Sie beim Erstellen einer HashMap eine Anfangskapazität angeben, die nahe an der gewünschten Größe liegen sollte.
Wenn Sie dies nicht tun, verwendet die Karte die Standardgröße, d. H. 16, und der Wert des Faktorloads beträgt 0,75. Die ersten 11 Anrufe für Put () sind sehr schnell, aber der 12. (16*0,75) -Auf wird ein neues internes Array mit Länge 32 (und der entsprechenden verknüpften Liste/dem gebliebenen Baum) erzeugt, und der 13. bis 22. Aufruf zum Put () wird sehr schnell sein, aber die 23. (32*0,75) erholt sich wieder (erneut). Dann wird der interne Größenvorgang ausgelöst, wenn die Put () -Methode als 48., 96., 192. bezeichnet wird. Wenn die Datenmenge nicht groß ist, ist der Betrieb des Umbaues des internen Arrays sehr schnell, aber wenn die Datenmenge groß ist, kann die ausgegebene Zeit von Sekunden bis Minuten liegen. Durch Angeben der gewünschten Größe der Karte während der Initialisierung können Sie den Verbrauch vermeiden, der durch die Größenänderung der Operationen verursacht wird.
Aber hier gibt es auch einen Nachteil: Wenn Sie das Array auf sehr groß einstellen, zum Beispiel 2^28, aber Sie nur 2^26 Eimer im Array verwenden, werden Sie viel Speicher verschwenden (ungefähr 2^30 Bytes in diesem Beispiel).
abschließend
Für einfache Anwendungsfälle müssen Sie nicht wissen, wie HashMap funktioniert, da Sie den Unterschied zwischen O (1), O (n) und O (log (n)) nicht sehen. Es ist jedoch immer vorteilhaft, den Mechanismus hinter dieser häufig verwendeten Datenstruktur zu verstehen. Darüber hinaus ist dies eine typische Interviewfrage für Java -Entwicklerpositionen.
Bei großen Datenvolumina wird es sehr wichtig zu verstehen, wie HashMap funktioniert und wie wichtig eine Hash -Funktion für Schlüssel ist.
Ich hoffe, dieser Artikel kann Ihnen helfen, ein tiefes Verständnis für die Umsetzung von HashMap zu haben.