Java lru (am wenigsten verwendet) detaillierte Erklärung
LRU ist die Abkürzung des am wenigsten verwendeten kürzlich verwendeten. Es wird als "neueste Verwendung" übersetzt. LRU -Cache wird unter Verwendung dieses Prinzips implementiert. Einfach ausgedrückt, es soll eine bestimmte Datenmenge zwischenspeichern. Wenn der festgelegte Schwellenwert überschritten wird, werden einige abgelaufene Daten gelöscht. Zum Beispiel zwischen 10.000 Daten. Wenn die Daten weniger als 10.000 sind, können Sie sie nach Belieben hinzufügen. Wenn es 10.000 überschreitet, müssen Sie neue Daten hinzufügen. Gleichzeitig müssen Sie die abgelaufenen Daten löschen, um sicherzustellen, dass wir 10.000 Daten maximal zwischenstrahlen können. Wie kann ich bestimmen, welche abgelaufenen Daten zu löschen sind? Wenn Sie den LRU -Algorithmus verwenden, um ihn zu implementieren, löschen Sie die ältesten Daten. Lassen Sie uns ohne viel sagen, und sprechen wir über die Java -Version der LRU -Cache -Implementierung.
In der Regel gibt es zwei Optionen zur Implementierung von LRU -Cache in Java. Einer besteht darin, LinkedHasMap zu verwenden, und das andere besteht darin, Ihre eigene Datenstruktur zu entwerfen und verknüpfte Liste + HashMap zu verwenden.
LinkedHashMap -Implementierung von LRU -Cache
LinkedHasMap selbst hat sequentielle Speicher implementiert. Standardmäßig wird es in der Reihenfolge des Hinzufügens von Elementen gespeichert. Es kann auch Speicher in der Reihenfolge des Zugriffs ermöglichen, dh die kürzlich gelesenen Daten werden vorne platziert und die frühesten Lesedaten werden am Ende platziert. Anschließend gibt es auch eine Methode, um zu bestimmen, ob die ältesten Daten gelöscht werden sollen. Die Standardeinstellung besteht darin, false zurückzugeben, dh keine Daten zu löschen. Die Methode zur Verwendung von LinkedHasMap zur Implementierung von LRU -Cache besteht darin, eine einfache Expansion von LinkedHasMap zu implementieren. Es gibt zwei Möglichkeiten, sich zu verlängern, einer ist Erbschaft und der andere die Delegation. Die spezifische Methode wird verwendet, um von persönlichen Vorlieben abhängig zu sein.
// ein Konstruktor von linkedHasMap. Wenn der Parameter AccessOrder wahr ist, wird er in der Reihenfolge des Zugriffs sortiert. Der jüngste Zugriff wird zuerst platziert und der früheste Zugriff wird hinter Public LinkedHasMap (int initialCapacity, float loadfactor, boolean AccessOrder) {Super (initialCapacity, loadFactor) gelegt. this.accessorder = AccessOrder;} // linkedHashMap wird mit Methode enthält, um festzustellen, ob das älteste Element löschen soll. Es gibt standardmäßig false zurück, dh es löscht alte Daten nicht. // Wir müssen diese Methode neu schreiben und alte Daten löschen, wenn bestimmte Bedingungen geschützt sind. LRU Cache LinkedHashMap (Erbschaftsumsetzung)
Die Vererbungsmethode ist relativ einfach zu implementieren und die Kartenschnittstelle wird implementiert. Bei Verwendung einer Multi-Thread-Umgebung können Sie die Methode der Sammlungen.SynchronizedMap () verwenden, um Thread-safe-Operationen zu implementieren.
Paket cn.lzrabbit.structure.lru; Import Java.util.linkedHasMap; Import Java.util.Map;/*** Erstellt von Liuzhao am 14.5.15. */public class lRucache2 <k, v> erweitert linkedHashMap <k, v> {private endgültige int max_cache_size; public lRucache2 (int cachesize) {super ((int) math.ceil (cachesize / 0,75) + 1, 0,75f, true); Max_cache_size = cachesize; } @Override Protected boolean RemoveELDESTEntry (map.entry älter) {return size ()> max_cache_size; } @Override public String toString () {StringBuilder sb = new StringBuilder (); für (Map.Entry <k, v> Eintrag: Einstieg ()) {sb.append (string.format ("%s:%s", Eintrag.getKey (), Eintrag.getValue ()); } return sb.toString (); }}Dies ist eine relativ Standard -Implementierung. Es ist immer noch etwas umständlich, so in der tatsächlichen Verwendung so zu schreiben. Wenn es so eine praktischere Methode schreibt, speichert es sich die Mühe, eine Klasse separat zu sehen.
endgültig int cachesize = 100; map <String, String> map = new LinkedHashMap <String, String> ((int) math.ceil (cachesize / 0.75f) + 1, 0,75f, true) {@Override Protected Boolean RemoveLdestentry (MAP.Entry <String> ältere ältere) {{{{{{)> cachessize; }}; LRU Cache LinkedHashMap (Delegation) Implementierung
Die Implementierung der Delegationsmethode ist eleganter, aber da die Kartenschnittstelle nicht implementiert ist, muss sich die Threadsynchronisation selbst erfolgen.
Paket cn.lzrabbit.structure.lru; Import Java.util.linkedHasMap; Import Java.util.map; Import Java.util.set;/*** Erstellt von Liuzhao am 14.5.13. */public class lRucache3 <k, v> {private endgültige int max_cache_size; private final float default_load_factor = 0,75f; LinkedHasMap <k, v> Karte; public lRucache3 (int cachesize) {max_cache_size = cachesize; // Berechnen Sie die Kapakte des HashMap basierend auf Cachesize- und Ladungsfaktoren. +1 Stellen Sie sicher, dass die HashMap -Expansion nicht ausgelöst wird, wenn die obere Grenze von Cachesize erreicht wird. int capacity = (int) math.ceil (max_cache_size / default_load_factor) + 1; map = new linkedHashMap (Kapazität, default_load_factor, true) {@Override Protected boolean RemeeldEnterry (map.Entry älter) {return size ()> max_cache_size; }}; } public synchronisierte void put (k key, v -Wert) {map.put (Schlüssel, Wert); } public synchronized v get (k key) {return map.get (key); } public synchronisierte void remove (k key) {map.remove (key); } public synchronisierte set <map.Entry <k, v >> getAll () {return map.EntrySet (); } public synchronisierte int size () {return map.size (); } public synchronisierte void clear () {map.clear (); } @Override public String toString () {StringBuilder sb = new StringBuilder (); für (Map.Entry -Eintrag: map.enterrySet ()) {sb.append (string.format ("%s:%s", Entry.getKey (), Entry.getValue ()); } return sb.toString (); }} Die verknüpfte Liste + HashMap -Implementierung von LRU Cache
Hinweis: Diese Implementierung ist nicht thread. Wenn Sie in einer Umgebung mit mehreren Threaden verwendet werden, müssen Sie relevante Methoden synchronisiert werden, um Thread-safe-Operationen zu erreichen.
Paket cn.lzrabbit.structure.lru; import Java.util.hashMap;/*** Erstellt von Liuzhao am 14.5.12. */public class lRucache1 <k, v> {private endgültige int max_cache_size; Privateintrag zuerst; Privateintrag zuletzt; Private Hashmap <k, Eintrag <k, v >> Hashmap; public lRucache1 (int cachesize) {max_cache_size = cachesize; HashMap = new Hashmap <k, Eintrag <k, v >> (); } public void put (k key, v -Wert) {Eintragseintrag = getEntry (Schlüssel); if (Eintrag == null) {if (hashMap.size ()> = max_cache_size) {HashMap.remove (last.Key); removelast (); } Eintrag = neuer Eintrag (); Eintrag.Key = Key; } Eintrag.Value = Wert; MoveToFirst (Eintrag); HashMap.put (Schlüssel, Eintrag); } public v get (k key) {Eintrag <k, v> Eintrag = GetEntry (Schlüssel); if (Eintrag == null) return null; MoveToFirst (Eintrag); Rückgabeeingabe.Value; } public void remove (k key) {Eintrag Eintrag = getEntry (Schlüssel); if (Eintrag! = NULL) {if (Eintrag.pre! if (Eintrag.Next! = null) Eintrag if (Eintrag == zuerst) first = Eintrag.Next; if (Eintrag == last) last = Eintrag.pre; } Hashmap.remove (Schlüssel); } private void movetofirst (Eintragseintrag) {if (Eintrag == zuerst) return; if (Eintrag. if (Eintrag.Next! = null) Eintrag if (Eintrag == last) last = last.pre; if (first == null || last == null) {first = last = Eintrag; zurückkehren; } Eintrag.Next = zuerst; zuerst.pre = Eintrag; zuerst = Eintrag; zuerst = Eintrag; Eintrag.pre = null; } private void renoveVelast () {if (last! = null) {last = last.pre; if (last == null) zuerst = null; sonst last.Next = null; }} privater Eintrag <k, v> GetEntry (k key) {return hashmap.get (key); } @Override public String toString () {StringBuilder sb = new StringBuilder (); Eingabeeintrag = zuerst; while (einstieg! Eintrag = Eintrag.Next; } return sb.toString (); } Klasseneintrag <k, v> {publiceintrag pre; öffentlicher Eintrag als nächstes; öffentlicher K -Schlüssel; öffentlicher V -Wert; }} FIFO -Implementierung von LinkedHasMap
FIFO ist die Abkürzung des ersten Eingangs-Erstausgangs, der oft als erstes als Erstausgang bezeichnet wird. Standardmäßig wird LinkedHasMap in der Reihenfolge der Addition gespeichert. Wir müssen nur die REMELDESTENTRY -Methode umschreiben, um einen FIFO -Cache einfach zu implementieren. Die vereinfachte Version des Implementierungscode ist wie folgt.
Finale int cachesize = 5; linkedHasMap <Integer, String> lRU = new LinkedHashMap <Integer, String> () {@Override Protected boolean RemeeldErdEntEntry (MAP.Entry <Integer, String> älter) {return size ()> cachesize; }}; Aufrufen Beispiel
Paket cn.lzrabbit.structure.lru; Import cn.lzrabbit.itest; import Java.util.linkedhashMap; Import Java.util.map;/*** Erstellt von Liuzhao unter 14-5-15. */public class lRucachetest {public static void main (String [] args) löst Ausnahme aus {System.out.println ("Start ..."); lrucache1 (); lrucache2 (); lrucache3 (); lrucache4 (); System.out.println ("Over ..."); } static void lRucache1 () {System.out.println (); System.out.println ("================================================================="); LRUCache1 <Integer, String> lRU = new lrucache1 (5); lru.put (1, "11"); lru.put (2, "11"); lru.put (3, "11"); lru.put (4, "11"); lru.put (5, "11"); System.out.println (lru.toString ()); lru.put (6, "66"); lru.get (2); lru.put (7, "77"); lru.get (4); System.out.println (lru.toString ()); System.out.println (); } static <T> void lrucache2 () {System.out.println (); System.out.println("======================================================================= ==================================================================================ieben LinkedHasMap (Erbschaft) 实现 ========================== "); LRUCache2 <Integer, String> lRU = new LRUCache2 (5); lru.put (1, "11"); lru.put (2, "11"); lru.put (3, "11"); lru.put (4, "11"); lru.put (5, "11"); System.out.println (lru.toString ()); lru.put (6, "66"); lru.get (2); lru.put (7, "77"); lru.get (4); System.out.println (lru.toString ()); System.out.println (); } static void lrucache3 () {System.out.println (); System.out.println ("====================================================================================================================================================================================================================================="); LRUCache3 <Integer, String> lRU = new lrucache3 (5); lru.put (1, "11"); lru.put (2, "11"); lru.put (3, "11"); lru.put (4, "11"); lru.put (5, "11"); System.out.println (lru.toString ()); lru.put (6, "66"); lru.get (2); lru.put (7, "77"); lru.get (4); System.out.println (lru.toString ()); System.out.println (); } static void lrucache4 () {System.out.println (); System.out.println ("==========================================================================================================================================================="); endgültig int cachesize = 5; LinkedHasMsMap <Integer, String> lRU = new LinkedHasMap <Integer, String> () {@Override Protected boolean RemoveEeldEntry (MAP.Entry <Integer, String> Eldest) {return size ()> cachesze; }}; lru.put (1, "11"); lru.put (2, "11"); lru.put (3, "11"); lru.put (4, "11"); lru.put (5, "11"); System.out.println (lru.toString ()); lru.put (6, "66"); lru.get (2); lru.put (7, "77"); lru.get (4); System.out.println (lru.toString ()); System.out.println (); }}Auslaufergebnisse
"C:/Program Files (x86)/Java/jdk1.6.0_10/bin/java" -Didea.launcher.port=7535 "-Didea.launcher.bin.path=C:/Program Files (x86)/JetBrains/IntelliJ IDEA 13.0.2/bin" -Dfile.encoding=UTF-8 -classpath "C:/Program Files (x86) /java/jdk1.6.0_10/jre/lib/charsets.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/deploy.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/javaws.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/jce.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/jce.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/management-agent.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/plugin.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/resources.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/rt.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/ext/dnsns.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/ext/localedata.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/ext/sunjce_provider.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/ext/sunmscapi.jar;c:/program Dateien (x86) /java/jdk1.6.0_10/jre/lib/ext/sunpkcs11.jar; (x86)/jetbrains/intellij idee 13.0.2/lib/idee_rt.jar "com.intellij.rt.execution.application.appmain Mainstart...======================================================================================================= =====================================================ieben =====================================================ieben =====================================================ieben LinkedHasMap (Erbschaft) Implementierung ================================================================ ============================================================================ =========================================================================== ============================================================================ 1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 =================================== FIFO LinkedHashMap default Implementierung =================================================== {1 = 11, 2 = 11, 3 = 11, 4 = 11, 5 = 11} {3 = 11, 4 = 11, 5 = 11, 6 = 66, 7 = 77Danke fürs Lesen, ich hoffe, es kann Ihnen helfen. Vielen Dank für Ihre Unterstützung für diese Seite!