In diesem Artikel begannen wir, den Quellcode von LinkedHasMap zu analysieren. LinkedHasMap erbt HashMap, was bedeutet, dass LinkedHasMap auf der Grundlage von HashMap erweitert wird. Daher müssen die Leser den Quellcode von LinkedHasMap betrachten, sondern den Quellcode von HashMap verstehen. Sie können die Einführung meines vorherigen Artikel "Java Collection Series [3] ---- HashMap Source Code Analysis" überprüfen. Solange Sie ein tiefes Verständnis des Implementierungsprinzips von HashMap haben und sich dann die Quellcodes von LinkedHasMap ansehen, sind Hashset und LinkedHashset alle sehr einfach. Daher sollten Leser geduldig sein und den HashMap -Quellcode untersuchen. Dies ist ein gutes Geschäft, um einen zu kaufen, der drei kostenlos wird. Bei der früheren Analyse des HashMap-Quellcodes habe ich eine problemorientierte Analyse des Quellcode verwendet, damit ich ihn nicht zufällig wie eine kopflose Fliege analysieren würde, und die Leser könnten auch ein tieferes Verständnis des Problems haben. In diesem Artikel habe ich beschlossen, diese Methode zu verwenden, um LinkedHasMap zu analysieren.
1. Welche Art von Struktur wird in LinkedHasMap verwendet?
Wie Sie sehen können, gibt es, da LinkedHasMap von HashMap erbt, in LinkedHasMap immer noch eine Hash -Tabelle, aber LinkedHashMap hat einen Eintrag umgeschrieben und zwei Mitgliedsvariablen zum ursprünglichen HashMap -Eintrag hinzugefügt, nämlich den vorherigen Knotenreferenz und die Nachfolge -Knotenreferenz. Auf diese Weise werden alle Knoten miteinander verknüpft, um eine mit zwei Wege verknüpfte Liste zu bilden. Wenn Sie Elemente erhalten, durchqueren Sie einfach die mit zwei Wege verknüpfte Liste direkt. Mal sehen, wie die LinkedHasMap -Implementierung des Eintrags aussieht.
private statische Klasseneintrag <k, v> erweitert Hashmap.Entry <k, v> {// Referenz des vorherigen Knotens des aktuellen Knotens im bidirektionalen Listen -Eintrag <k, v> vor; // Referenz des nachfolgenden Knotens des aktuellen Knotens im bidirektionalen Listeneintrag <k, v> nach; Eintrag (int Hash, K Key, V -Wert, Hashmap.Entry <k, v> next) {Super (Hash, Schlüssel, Wert, Weiter); } // Entfernen Sie diesen Knoten aus der bidirektionalen verknüpften Liste private void remove () {vor.after = After; After.before = vor; } // Einfügen des aktuellen Knotens in einen vorhandenen Knoten in der bidirektionalen verknüpften Liste private void addBefore (Eintrag <k, v> existingEntry) {// auf die Referenz des nächsten Knotens des aktuellen Knotens auf den angegebenen Knoten nach = vorabereter; // Die Referenz des vorherigen Knotens des aktuellen Knotens verweist auf den vorherigen Knoten des angegebenen Knotens vor = vorhandenEntry.bevor; // Die Referenz des nächsten Knotens des angegebenen Knotens verweist vor dem aktuellen Knoten vor. After = this; // Die Referenz des vorherigen Knotens des angegebenen Knotens verweist auf den aktuellen Knoten nach. Beefore = this; } // In der Reihenfolge des Zugriffs sortiert, zeichnen Sie jedes Mal auf, wenn der Operation erhalten wird, als die Operation (Hashmap <k, v> m) {linkedHasMap <k, v> lm = (linkedHashMap <k, v>) m; // Wenn in Zugangsbestellung sortiert, wenn (lm.accessorder) {lm.modcount ++; // Entfernen Sie sich zuerst aus der bidirektionalen verlinkten Liste; // Setzen Sie sich an den Schwanz der bidirektionalen verknüpften Liste AddBefore (lm.Header); }} void recordReMoval (HashMap <k, v> m) {remove (); }}2. Wie implementiert LinkedHasMap die Sortierung in Einfügungsreihenfolge?
// Die Methode, die in der Put -Methode der übergeordneten Klassen -void Addentry (int Hash, K -Schlüssel, V -Wert, int bucketIndex) {// die Additiony -Methode der übergeordneten Klasse Super.adDentry (Hash, Schlüssel, Wert, Bucketindex) aufgerufen wird; // Der folgende Vorgang ist für die Implementierung von LRU -Cache bequem. Wenn die Cache -Kapazität unzureichend ist, entfernen Sie den ältesten Elementeintrag <k, v> älterer = header.after; if (REMETENELDESTENTRY (älteste)) {RemeenEntryForKey (ältest.Key); }} // Die Methode void createEntry (int Hash, K -Schlüssel, V -Wert, int bucketIndex) {// Erstigen Sie den Eintrag HashMap von HashMap.Entry <k, v> old = table [bucketIndex]; // Es in LinkedHasMaps eigener Eintrag <k, v> e = neuer Eintrag <> (Hash, Schlüssel, Wert, alt); Tabelle [BucketIndex] = e; // Fügen Sie den aktuellen Knoten zum Schwanz der bidirektionalen verknüpften Liste E.Addbefore (Header) ein; Größe ++;}LinkedHashMap überschreibt die Additiony und erstellte die Methoden seiner übergeordneten Klasse -HashMap. Wenn Sie ein Schlüsselwertpaar einfügen möchten, wird die Put-Methode seiner übergeordneten Klassen-Hashmap zuerst aufgerufen. In der Put -Methode werden wir überprüfen, ob der entsprechende Schlüssel in der Hash -Tabelle vorhanden ist. Wenn es existiert, ersetzen Sie einfach den Wert direkt. Wenn es nicht vorhanden ist, rufen Sie die AddEntry -Methode an, um einen neuen Eintrag zu erstellen. Beachten Sie, dass LinkedHasMaps eigene AddEntry -Methode zu diesem Zeitpunkt aufgerufen wird. Wir sehen den obigen Code. Diese AddeldeldEntry -Methode der übergeordneten Klasse ruft nicht nur die AddeldEntry -Methode zurück und ruft auch REMELDELLESTEERN auf, um das älteste Element zu entfernen. Dieser Vorgang dient hauptsächlich dazu, den LRU -Algorithmus zu implementieren, der nachstehend erörtert wird. Wir sehen, dass LinkedHasMap auch die CreateStry -Methode umschreibt. Wenn Sie einen neuen Eintrag erstellen möchten, wird diese Methode aufgerufen. Nach jedem Eintrag in die Hash -Tabelle wird die Methode addBefore aufgerufen, um den aktuellen Knoten in den Schwanz der bidirektionalen verknüpften Liste einzufügen. Auf diese Weise zeichnet die bidirektionale verknüpfte Liste die Reihenfolge jedes eingefügten Knotens auf. Wenn Sie Elemente erhalten, durchqueren Sie einfach die bidirektionale verknüpfte Liste. Die folgende Abbildung zeigt die Operation jedes Aufrufs, um die Vorderseite hinzuzufügen. Da es sich um eine bidirektionale verknüpfte Liste handelt, wird der aktuelle Knoten tatsächlich in den Schwanz der bidirektionalen verknüpften Liste eingefügt.
3. Wie kann ich LinkedHasMap verwenden, um LRU -Cache zu implementieren?
Wir wissen, dass die Implementierung von Cache vom Speicher des Computers abhängt und die Speicherressourcen recht begrenzt sind und es unmöglich ist, Elemente ohne Grenzwert zu speichern. Daher müssen wir einige Elemente angemessen löschen, wenn die Kapazität nicht ausreicht. Welches Element ist also besser zu löschen? Die Idee des LRU -Algorithmus ist, dass, wenn in letzter Zeit auf eine Daten zugegriffen wurde, auch die Chancen, in Zukunft zugegriffen zu werden, ebenfalls höher sind. So können wir Daten löschen, auf die nicht oft zugegriffen wird. Schauen wir uns als nächstes an, wie LinkedHasMap den LRU -Mechanismus implementiert.
Public Class LinkedHasMap <K, V> erweitert Hashmap <K, V> implementiert MAP <K, v> {// Bothly Linked List Header Private Transient Entry <K, V> Header; // private endgültige Boolesche Accessorder in der Reihenfolge des Zugangs sortieren; ... public linkedHasMap (intit initialCapacity, float loadfactor, boolean AccessOrder) {Super (initialCapacity, loadFactor); this.accessorder = AccessOrder; } // Wert gemäß Key Public V GET (Objektschlüssel) {// Aufrufen der übergeordneten Klassenmethode, um den entsprechenden Eintrag <k, v> e = (Eintrag <k, v>) GetEntry (Schlüssel) abzurufen; if (e == null) {return null; } // Wenn es in Zugriffsreihenfolge sortiert ist, wird der Knoten nach jeder Verwendung am Ende der bidirektionalen verknüpften Liste E. recordAccess (this) platziert. Return E. value; } private statische Klasseneintrag <k, v> erweitert Hashmap.Entry <k, v> {... // Fügen Sie den aktuellen Knoten in einen vorhandenen Knoten in die bidirektionale verlinkte Liste privat void addbefore (Eintrag <k, v> vorhandenerEntier) ein. // Die Referenz des vorherigen Knotens des aktuellen Knotens verweist auf den vorherigen Knoten des angegebenen Knotens vor = vorhandenEntry.bevor; // Die Referenz des nächsten Knotens des angegebenen Knotens verweist vor dem aktuellen Knoten vor. After = this; // Die Referenz des vorherigen Knotens des angegebenen Knotens verweist auf den aktuellen Knoten nach. Beefore = this; } // In Zugriffsreihenfolge sortiert, zeichnen Sie jedes Mal auf, wenn der Operation void recordAccess (Hashmap <k, v> m) {linkedHashMap <k, v> lm = (linkedHashMap <k, v>) m; // Wenn in Zugangsbestellung sortiert, wenn (lm.accessorder) {lm.modcount ++; // Entfernen Sie sich zuerst aus der bidirektionalen verlinkten Liste; // Setzen Sie sich an den Schwanz der bidirektionalen verknüpften Liste AddBefore (lm.Header); }} ...} // Diese Methode wird in der übergeordneten Klasse Put -Methode void Addentry (int Hash, K -Schlüssel, V -Wert, int bucketIndex) {// Berechnen Sie die Add. // Der folgende Vorgang ist für die Implementierung von LRU -Cache bequem. Wenn die Cache -Kapazität unzureichend ist, entfernen Sie den ältesten Elementeintrag <k, v> älterer = header.after; if (REMETENELDESTENTRY (älteste)) {REMELDELDESTFORKEY (ältest.Key); }} // Wo löscht das älteste Element? Diese Methode wurde so konzipiert, dass sie durch Unterklassen geschützt werden, die boolean enteneldErdEntry (MAP.Entry <k, v> ältere Menschen) {return false; }}Um intuitiver zu sein, habe ich einen irrelevanten Code in dem oben veröffentlichten Code weggelassen. Wir können sehen, dass LinkedHasMap einen Mitgliedervariablen -Accessorder hat, der aufgezeichnet wird, ob es in der Reihenfolge des Zugriffs sortiert werden muss. Es bietet einen Konstruktor, der den Wert von AccessOrder selbst angeben kann. Jedes Mal, wenn Sie die GET -Methode aufrufen, um das Element zu erhalten, wird E. recordaccess (this) aufgerufen, wodurch der aktuelle Knoten zum Ende der bidirektionalen verknüpften Liste verschoben wird. Jetzt wissen wir, dass wir dieses Element jedes Mal, wenn wir das Element erhalten, auf das Ende der bidirektionalen Linkliste verschieben, wenn wir das Element erhalten. Der Zweck dieses Schritts besteht darin, die am häufigsten verwendeten Elemente von den nicht oft verwendeten Elementen zu unterscheiden, und die häufig verwendeten Elemente werden am Ende platziert und die weniger häufig verwendeten Elemente werden am Kopf platziert. Kehren wir zum obigen Code zurück und sehen, dass wir jedes Mal, wenn die AddEntry -Methode aufgerufen wird, feststellen, ob das älteste Element gelöscht werden muss. Die Logik des Urteils wird durch REMELELDESTENTRY implementiert, die so konzipiert ist, dass sie durch Unterklassen überschrieben und die Logik im Inneren umschreiben. Beachten Sie, dass der älteste Knoten aus dem Kopf der bidirektionalen verknüpften Liste zum Löschen auf den Schwanz der bidirektionalen verlinkten Liste auf den Schwanz der bidirektionalen verlinkten Liste verschoben wird. Das folgende Beispiel implementiert einen einfachen LRU -Cache.
Public Class Lrumap <k, v> erweitert LinkedHasMap <k, v> {private int -Kapazität; Lrumap (int Kapazität) {// Aufruf des übergeordneten Klassenkonstruktors, so ein Sortieren in Zugriffsreihenfolge Super (Kapazität, 1f, true); this.capacity = Kapazität; } @Override public boolean RemeeldEntry (MAP.Entry <k, v> ältere Menschen) {// Wenn das Schlüssel-Wert-Paar größer oder gleich der Hash-Tabellenkapazität ist. } public static void main (String [] args) {lrumap <Integer, String> map = new Lrumap <Integer, String> (4); map.put (1, "a"); map.put (2, "b"); map.put (3, "c"); System.out.println ("Originalsammlung:" + map); String s = map.get (2); System.out.println ("Element erhalten:" + map); map.put (4, "d"); System.out.println ("After Insertion:" + Map); }}Die Ergebnisse sind wie folgt:
Hinweis: Alle oben genannten Analysen basieren auf JDK1.7, und es wird Unterschiede zwischen verschiedenen Versionen geben, die Leser müssen aufpassen.
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.