Wir haben die beiden Sätze von ArrayList und LinkedList analysiert. Wir wissen, dass ArrayList basierend auf Arrays implementiert ist und LinkedList basierend auf verknüpften Listen implementiert wird. Jeder hat seine eigenen Vor- und Nachteile. Beispielsweise ist ArrayList bei der Positionierung und Suche nach Elementen besser als LinkedList, während die LinkedList beim Hinzufügen und Entfernen von Elementen besser ist als ArrayList. Der in diesem Artikel eingeführte HashMap kombiniert die Vorteile beider. Die zugrunde liegende Schicht wird basierend auf einer Hash -Tabelle implementiert. Wenn Hash -Konflikte nicht berücksichtigt werden, kann die Zeitkomplexität von HashMap zusätzlich, Löschen, Änderungen und Suchvorgänge ein erstaunliches O (1) erreichen. Schauen wir uns zunächst die Struktur der Hash -Tabelle an, auf der sie basiert.
Wie aus der obigen Abbildung hervorgeht, ist eine Hash -Tabelle eine Struktur, die aus einem Array und einer verknüpften Liste besteht. Natürlich ist die obige Figur ein schlechtes Beispiel. Eine gute Hash -Funktion sollte versuchen, die Verteilung der Elemente im Array zu durchschnitt, Hash -Konflikte zu reduzieren und die Länge der verknüpften Liste zu verringern. Je länger die Länge der verknüpften Liste bedeutet, dass je mehr Knoten sie während der Suche durchquert werden müssen, desto schlimmer wird die Leistung der Hash -Tabelle. Schauen wir uns als nächstes einige Mitgliedervariablen von HashMap an.
// Standardkapazität statische endgültige int default_initial_capacity = 1 << 4; // Standard -Maximalkapazität statische endgültige int maximum_capacity = 1 << 30; // Standard -Ladefaktor bezieht TABELLE Transient Entry <K, v> [] Tabelle = (Eintrag <k, v> []) leere_table; // Hashmap-Größe, dh die Anzahl der in Hashmap-transienten Int-Größe gespeicherten Schlüsselwertepaare, die zum Bestimmen des Hash-Ladungskapazitäts verwendet werden. Die Anzahl der Hash-Ladungskapazitäten muss verwendet werden. Um den Mechanismus zu fälschen, transient int modcount; // Verwenden Sie den Standardschwellenwert der alternativen Hash statischen endgültigen int alternativ_hashing_threshold_default = Integer
Wie aus den Mitgliedsvariablen hervorgeht, beträgt die Standardkapazität von HashMap 16 und der Standardlastfaktor 0,75. Der Schwellenwert ist der Schwellenwert des Schlüsselwertpaars, das im Set gespeichert werden kann. Die Standardeinstellung ist der anfängliche Kapazität*Belastungsfaktor, dh 16*0,75 = 12. Wenn das Schlüsselwertpaar den Schwellenwert überschreiten muss, bedeutet dies, dass die Hash-Tabelle derzeit bereits gesättigt ist. Wenn die Elemente weiterhin hinzugefügt werden, wird der Hash -Konflikt hinzugefügt, der die Leistung von HashMap beeinträchtigt. Zu diesem Zeitpunkt wird der automatische Mechanismus für die Kapazitätserweiterung ausgelöst, um die Leistung von HashMap zu gewährleisten. Wir können auch sehen, dass die Hash-Tabelle tatsächlich ein Eintragsarray ist, und jeder im Array gespeicherte Eintrag ist der Headerknoten der One-Way-Linked-Liste. Dieser Eintrag ist eine statische innere Klasse von Hashmap. Schauen wir uns die Mitgliedsvariablen des Eintritts an.
statischer Klasseneintrag <k, v> implementiert map.Entry <k, v> {endgültig k key; // Key V -Wert; // Werteintrag <k, v> Weiter; // der Verweis auf den nächsten Eintrag int Hash; // Histocode ... // den folgenden Code auslassen}Eine Eintragsinstanz ist ein Schlüsselwertpaar, das Schlüssel und Wert enthält. Jede Eintragsinstanz hat einen Hinweis auf die nächste Eintragsinstanz. Um wiederholte Berechnungen zu vermeiden, speichert jede Eintragsinstanz auch den entsprechenden Hash -Code. Es kann gesagt werden, dass das Einstiegsarray der Kern von HashMap ist und alle Operationen für dieses Array durchgeführt werden. Da Hashmap -Quellcode relativ lang ist, ist es unmöglich, alle seine Methoden auf umfassende Weise einzuführen. Daher konzentrieren wir uns nur auf die wichtigsten Punkte, um sie einzuführen. Als nächstes werden wir problemorientiert sein und den internen Mechanismus von Hashmap für die folgenden Themen ausführlich untersuchen.
1. Welche Operationen tun Hashmap während des Baus?
// Konstruktor, in die Initialisierungskapazität und den Lastfaktor public HashMap (int initialCapacity, float loadfactor) {if (initialCapacity <0) {Neue IllegalArgumentException ("illegale Anfangskapazität:" + initialCapacity); } // Wenn die Initialisierungskapazität größer als die maximale Kapazität ist, setzen Sie sie auf die maximale Kapazität, wenn (initialCapacity> maximum_capacity) {initialCapacity = maximum_capacity; } // Wenn der Lastfaktor kleiner als 0 beträgt oder der Lastfaktor keine schwimmende Punktzahl ist, wird eine Ausnahme geworfen, wenn (loadFactor <= 0 || float.isnan (loadfactor)) {neue IllegalArgumentException ("illegaler Lastfaktor:" + loadfactor); } // LOADFACTOR = LOADFACTOR = loadFactor; // Der Schwellenwert ist die Initialisierungskapazitätsschwelle = InitialCapacity; init ();} void init () {}Alle Konstruktoren nennen diesen Konstruktor. In diesem Konstruktor sehen wir, dass zusätzlich zu einer Überprüfung der Parameter zwei Dinge durchgeführt werden: Setzen Sie den Lastfaktor auf den eingehenden Lastfaktor und setzen Sie den Schwellenwert auf die eingehende Initialisierungsgröße. Die Init -Methode ist leer und tut nichts. Beachten Sie, dass zu diesem Zeitpunkt kein neues Eintragsarray basierend auf der eingehenden Initialisierungsgröße erstellt wird. Wann werden wir also ein neues Array erstellen? Lesen Sie weiter.
2. Welche Operationen werden ausgeführt, wenn HashMap Schlüsselwertpaare hinzufügt?
// Taste-Wert-Paare in HashMap public v put (k Schlüssel, V-Wert) {// initialisieren if (table == leere_table) {// Initialisieren Sie die Hash-Tabelle initialisieren, initialisieren (Schwellenwert); } if (key == null) {return putFornullKey (Wert); } // Berechnen Sie den Hash -Code des Schlüssels int Hash = Hash (Schlüssel); // Positionieren Sie die Position der Hash -Tabelle gemäß dem Hash -Code int i = indexFor (Hash, Tabelle.Length); für (Eintrag <k, v> e = table [i]; e! = null; e = e.next) {Objekt k; // Wenn der entsprechende Schlüssel bereits vorhanden ist, ersetzen Sie seinen Wertwert und senden Sie den ursprünglichen Wert zurück, wenn (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 ++; // Wenn es keinen entsprechenden Schlüssel gibt, fügen Sie die HashMap -Addition (Hash, Schlüssel, Wert, i) hinzu; // NULL return null return null;}Sie können sehen, dass Sie beim Hinzufügen von Schlüsselwertpaaren zuerst prüfen, ob die Hash-Tabelle eine leere Tabelle ist und ob es sich um eine leere Tabelle handelt, sie wird initialisiert. Führen Sie dann nachfolgende Operationen durch und rufen Sie die Hash -Funktion auf, um den Hash -Code des übergaber Schlüssels zu berechnen. Positionieren Sie den angegebenen Slot des Eintragsarrays nach dem Hash-Code und durchqueren Sie dann die einseitige verknüpfte Liste des Steckplatzes. Wenn die bereits vorhandenen vorhanden sind, führen Sie einen Ersatzvorgang durch, andernfalls wird ein neuer Eintrag erstellt und in die Hash -Tabelle hinzugefügt.
3. Wie wird die Hash -Tabelle initialisiert?
// Initialisieren Sie die Hash -Tabelle und die Hash -Tabellenkapazität wird erweitert, da es möglich ist, dass die eingehende Kapazität keine Leistung von 2 privaten Hohlräumen aufblätterbar ist (int toze) {// Die Kapazität der Hash -Tabelle muss eine Leistung von 2 INT -Kapazität sein = Rounduptopower von2 (Tosize); // Setzen Sie den Schwellenwert, hier ist im Allgemeinen Kapazität * LoadFactor -Schwelle = (int) math.min (Kapazität * loadFactor, maximum_capacity + 1); // Erstellen Sie eine neue Hash -Tabelle mit einer angegebenen Kapazitätstabelle = neuer Eintrag [Kapazität]; // Initialisieren Sie den Hash -Saatgut inithashSeedasNeed (Kapazität);}Wie wir oben wissen, werden wir beim Erstellen einer HashMap kein neues Eingabebuch erstellen. Überprüfen Sie jedoch, ob die aktuelle Hash -Tabelle während des Einsatzbetriebs eine leere Tabelle ist. Wenn es sich um eine leere Tabelle handelt, rufen Sie die aufblätterbare Methode zur Initialisierung auf. Der Code für diese Methode ist oben veröffentlicht. Sie können sehen, dass die Kapazität des Eintragsarrays innerhalb der Methode neu berechnet wird, da die Initialisierungsgröße beim Erstellen des HashMap möglicherweise keine Leistung von 2 ist. Sie müssen diese Zahl daher in eine Leistung von 2 umwandeln und dann ein neues Eintragsarray basierend auf der neuen Kapazität erstellen. Setzen Sie bei der Initialisierung der Hash -Tabelle den Schwellenwert erneut ein, und der Schwellenwert ist im Allgemeinen Kapazität*Lastfaktor. Darüber hinaus wird der Hash -Samen (HashSeed) bei der Initialisierung der Hash -Tabelle initialisiert. Mit diesem Hashsamen wird die Hash -Funktion optimiert. Die Standardeinstellung ist 0 und es wird kein alternativer Hash -Algorithmus verwendet. Sie können jedoch auch den Hash -Seed -Wert selbst festlegen, um einen Optimierungseffekt zu erzielen. Dies wird nachstehend ausführlich erörtert.
4. Wann bestimmt HashMap, ob es die Kapazität erweitern muss und wie es die Kapazität erweitert?
// Fügen Sie die Eingabemethode hinzu und bestimmen Sie zuerst, ob Sie die Kapazitätshohlabdessen (int Hash, K -Schlüssel, V -Wert, int bucketIndex) erweitern möchten. Wenn die Größe von Hashmap größer ist als der Schwellenwert und der Wert des entsprechenden Steckplatzes der Hash -Tabelle ist nicht leer, wenn (Größe> = thresholz) && (null! Schwelle zeigt an, dass ein Hash -Konflikt auftreten wird. Erweitern Sie also die Kapazitätsgröße (2 * Tabelle.Length); Hash = (null! = Schlüssel)? Hash (Schlüssel): 0; bucketIndex = indexFor (Hash, Tabelle.length); } // Es wird hier gezeigt, dass die Größe von HashMap den Schwellenwert nicht überschreitet, sodass die Kapazitäts -CreateEntry (Hash, Schlüssel, Wert, BucketIndex) nicht erweitert werden muss. int oldCapacity = oldTable.length; // Wenn die aktuelle maximale Kapazität bereits verwendet wird, können Sie den Schwellenwert nur erhöhen, wenn (oldcapacity == maximum_capacity) {threshold = ginnEger.max_value; zurückkehren; } // Ansonsten erweitern Sie den Kapazitätseintrag [] newtable = neuer Eintrag [NewCapacity]; // Die Methode zur Migration von Hash -Tabellenübertragung (neutable, inithashSeedasNeed (Newcapacity)); // Setzen Sie die aktuelle Hash -Tabelle auf die neue Hash -Tabelle = newtable; // Aktualisieren Sie den Hash -Tabellen -Schwellenwert = (int) math.min (NewCapacity * LoadFactor, Maximum_Capacity + 1);};}Wenn Sie die Put-Methode aufrufen, um ein Schlüsselwertpaar hinzuzufügen, rufen Sie die AddEnty-Methode auf und erstellen Sie einen neuen Eintrag. Wenn Sie den oben angegebenen AddEntry -Code sehen, bevor Sie einen neuen Eintrag erstellen, bestimmen Sie zunächst, ob die Größe des aktuellen Sammlungselements den Schwellenwert überschreitet. Wenn der Schwellenwert den Schwellenwert überschreitet, haben Sie die Größe der Größe für die Erweiterung an. Die neue Kapazität ist doppelt so hoch wie der ursprüngliche Hash -Tisch. In der Größenmethode wird ein neues Eintragsarray mit einer Kapazität von doppelt so hoch wie die ursprüngliche Hash -Tabelle erstellt. Dann werden alle Elemente in der alten Hash -Tabelle in die neue Hash -Tabelle migriert, in der Rehash durchgeführt werden kann und ob eine Rehash nach dem Wert durchgeführt wird, der von der inithashSeedasNeded -Methode berechnet wird. Nach Abschluss der Hash -Tabellenmigration wird die aktuelle Hash -Tabelle durch eine neue ersetzt, und schließlich wird der Schwellenwert des HashMap basierend auf der neuen Hash -Tabellenkapazität neu berechnet.
5. Warum muss die Größe des Eingangsarrays eine Leistung von 2 sein?
// Gibt den Array-Index zurück, der dem Hash-Code-statischen Index für (int h, int länge) {return H & (Länge-1) entspricht; }Die Indexfor -Methode berechnet das entsprechende Index im Array basierend auf dem Hash -Code. Wir können sehen, dass der (&) -operator innerhalb dieser Methode verwendet wird. Der Betrieb soll Bit -Operationen bei zwei Operanden ausführen. Wenn die entsprechenden zwei Bits 1 sind, ist das Ergebnis 1, ansonsten sind es 0. Operationen werden häufig verwendet, um hochbit-Werte von Operanden zu entfernen, wie z. B. 01011010 & 00001111 = 00001010.
Es ist bekannt, dass die Länge, die in die Länge des Eingangsarrays übergeht. Wir wissen, dass das Array-Index von 0 berechnet wird, sodass das maximale Index des Arrays Länge-1 ist. Wenn die Länge eine Leistung von 2 ist, folgen die Binärbits von Länge-1 1. Zu diesem Zeitpunkt besteht die Funktion von H & (Länge-1) darin, den hohen Bitwert von H zu entfernen und nur den niedrigen Bitwert von H als ein Index des Arrays zu hinterlassen. Daraus können wir erkennen, dass die Größe des Eingangsarrays als eine Leistung von 2 definiert ist, um diesen Algorithmus zu verwenden, um das Index des Arrays zu bestimmen.
6. Wie berechnet die Hash -Funktion den Hash -Code?
// Die Funktion, die den Hash -Code endgültig int Hash (Objekt k) {int h = hashsed generiert; // Wenn der Schlüssel vom Zeichenstreichtyp ist, verwenden Sie einen anderen Hash -Algorithmus, wenn (0! } h ^= k.hashcode (); // Die Störungsfunktion h ^ = (h >>> 20) ^ (h >>> 12); Rückgabe h ^ (h >>> 7) ^ (h >>> 4);}Die letzten beiden Zeilen der Hash -Methode sind der Algorithmus, der den Hash -Wert wirklich berechnet. Der Algorithmus, der den Hash -Code berechnet, wird als Störungsfunktion bezeichnet. Die sogenannte Störungsfunktion besteht darin, alles miteinander zu mischen. Hier können Sie sehen, dass hier vier Verschiebungsvorgänge von rechts nach rechts verwendet werden. Ziel ist es, den hohen Wert von H und den niedrigen Wert zu mischen, um die Zufälligkeit des niedrigen Werts zu erhöhen. Wie oben wissen wir, dass das Index des Positionierungsarrays basierend auf dem niedrigen Bit-Wert des Hash-Codes bestimmt wird. Der Hash -Code des Schlüssels wird von der HashCode -Methode generiert, und der niedrige Wert des Hash -Code, der von einer schlechten HashCode -Methode generiert wird, kann eine Menge Wiederholung aufweisen. Um den Hash-Code auf das Array relativ einheitlich zugeordnet zu machen, ist die Störungsfunktion praktisch, wobei die Eigenschaften des hohen Bitwerts in den niedrigen Bitwert kombiniert werden, wodurch die Zufälligkeit des niedrigen Bitwerts erhöht wird, wodurch die Hash-Verteilung lockerer wird, wodurch die Leistung verbessert wird. Die folgende Abbildung gibt ein Beispiel zum Verständnis.
7. Was ist mit dem Ersatz -Hash los?
Wir sehen, dass in der Hash -Methode die Hashseed zuerst H zugewiesen wird. Dieser Hashsed ist ein Hash -Samen, der ein zufälliger Wert ist und zur Optimierung der Hash -Funktion verwendet wird. Der Standard -HashSeed ist 0, was bedeutet, dass der alternative Hash -Algorithmus standardmäßig nicht verwendet wird. Also, wann man Hashseed benutzt? Zunächst müssen Sie den alternativen Hash festlegen, um den Wert von jdk.map.althashing.Threshold in der Systemeigenschaft festzulegen. Dieser Wert ist in der Systemeigenschaft standardmäßig -1. Wenn es -1 ist, ist der Schwellenwert der Verwendung des alternativen Hashs integer.max_value. Dies bedeutet auch, dass Sie möglicherweise nie einen Ersatz -Hash verwenden. Natürlich können Sie diesen Schwellenwert etwas kleiner einstellen, damit ein zufälliger Hashsed generiert wird, wenn das festgelegte Element den Schwellenwert erreicht. Dies erhöht die Zufälligkeit der Hash -Funktion. Warum alternative Hash verwenden? Wenn das festgelegte Element den von Ihnen festgelegten Schwellenwert erreicht, bedeutet dies, dass die Hash -Tabelle relativ gesättigt ist und die Möglichkeit von Hash -Konflikten stark zunimmt. Zu diesem Zeitpunkt kann die Verwendung einer zufälligeren Hash -Funktion für die zusätzlichen Elemente die hinzugefügten Elemente in der Hash -Tabelle zufällig verteilt machen.
Hinweis: Alle oben genannten Analysen basieren auf JDK1.7, und es werden wesentliche Änderungen zwischen verschiedenen Versionen geben. Die Leser müssen aufmerksam werden.