Java LRU (menos recientemente usado) Explicación detallada
LRU es la abreviatura de menos recientemente usado. Se traduce como "último uso". LRU Cache se implementa utilizando este principio. En pocas palabras, es para almacenar en caché una cierta cantidad de datos. Cuando se excede el umbral establecido, se eliminarán algunos datos caducados. Por ejemplo, almacenamos 10,000 datos. Cuando los datos son menos de 10,000, puede agregarlos a voluntad. Cuando supera los 10,000, debe agregar nuevos datos. Al mismo tiempo, debe eliminar los datos caducados para garantizar que podamos almacenar 10,000 datos al máximo. ¿Cómo determinar qué datos vencidos para eliminar? Si usa el algoritmo LRU para implementarlo, eliminará los datos más antiguos. Sin decir mucho, hablemos sobre la versión Java de la implementación de LRU Cache.
Por lo general, hay dos opciones para implementar LRU Cache en Java. Una es usar LinkedHashMap, y el otro es diseñar su propia estructura de datos y usar Linked List + HashMap.
Linkedhashmap Implementación de LRU Cache
LinkedHashMap en sí ha implementado un almacenamiento secuencial. Por defecto, se almacena en el orden de agregar elementos. También puede habilitar el almacenamiento en el orden de acceso, es decir, los datos de lectura recientemente se colocan en la parte delantera y los datos de lectura más tempranos se colocan al final. Luego también tiene un método para determinar si eliminar los datos más antiguos. El valor predeterminado es devolver falso, es decir, no eliminar datos. El método de usar LinkedHashMap para implementar LRU Cache es implementar una expansión simple de LinkedHashMap. Hay dos formas de extender, una es la herencia y la otra es la delegación. El método específico se utiliza para depender de las preferencias personales.
// Un constructor de Linkedhashmap. Cuando el parámetro AccessOrge es verdadero, se ordenará en el orden de acceso. El acceso más reciente se coloca primero y el acceso más temprano se coloca detrás de Public Linkedhashmap (int InitialCapacity, Float LoadFactor, Boolean AccessOrder) {Super (InicialCapacity, LoadFactor); this.accessorder = accessorder;} // Linkedhashmap viene con el método para determinar si eliminar el elemento más antiguo. Devuelve falso por defecto, es decir, no elimina los datos antiguos. // Lo que debemos hacer es reescribir este método y eliminar los datos antiguos cuando ciertas condiciones se cumplen Boolean Boolean RemoLeStentry (map.entry <k, v> eldest) {return false;} Implementación de LRU Cache Linkedhashmap (herencia)
El método de herencia es relativamente simple de implementar, y se implementa la interfaz MAP. Cuando use un entorno de múltiples subprocesos, puede usar el método Collections.SyChronizedMap () para implementar operaciones seguras de hilo.
paquete cn.lzrabbit.structure.lru; import java.util.linkedhashmap; import java.util.map;/*** creado por Liuzhao el 14-5-15. */public class lrucache2 <k, v> extiende Linkedhashmap <k, v> {private final int max_cache_size; public lrucache2 (int cachesize) {super ((int) math.ceil (cachesize / 0.75) + 1, 0.75f, true); Max_cache_size = Cachesize; } @Override Boolean Boolean RemoLeLDestEntry (MAP.Entry Elderly) {return size ()> max_cache_size; } @Override public string toString () {StringBuilder sb = new StringBuilder (); for (map.entry <k, v> entry: entrySet ()) {sb.append (string.format ("%s:%s", entry.getKey (), entry.getValue ())); } return sb.ToString (); }}Esta es una implementación relativamente estándar. Todavía es un poco engorroso escribir así en uso real. Al escribirlo así como este método más práctico, ahorra el problema de ver una clase por separado.
final int cachesize = 100; map <string, string> map = new Linkedhashmap <String, String> ((int) Math.Ceil (Cachesize / 0.75f) + 1, 0.75f, true) {@Override Boolean Boolean RemoLeSdestEntry (MAP.EnTry <String, String> Elderly) {Tamaño de retorno ()> Cacheseiz; }}; Implementación de LRU Cache Linkedhashmap (Delegación)
La implementación del método de delegación es más elegante, pero dado que la interfaz del mapa no se implementa, la sincronización de subprocesos debe hacerse usted mismo.
paquete cn.lzrabbit.structure.lru; import java.util.linkedhashmap; import java.util.map; import java.util.set;/*** creado por Liuzhao el 14-5-13. */public class lrucache3 <k, v> {private final int max_cache_size; Flotador final privado default_load_factor = 0.75f; Linkedhashmap <k, v> map; public lrucache3 (int cachesize) {max_cache_size = cachesize; // Calcule la capti del hashmap basada en los factores de caché y carga. +1 Asegúrese de que la expansión del hashmap no se active cuando se alcance el límite superior de caché. int capacidad = (int) math.ceil (max_cache_size / default_load_factor) + 1; MAP = new LinkedHashMap (Capacidad, default_load_factor, true) {@Override Boolean RemoLeLDestEntry (MAP.Entry Elderly) {return size ()> max_cache_size; }}; } public sincronizado void put (k key, v valor) {map.put (clave, valor); } public sincronizado v get (k key) {return map.get (clave); } public sincronizado void eliminar (k key) {map.remove (clave); } Public Syncronized Set <map.entry <k, v >> getAll () {return map.entryset (); } public sincronizado int size () {return map.size (); } public sincronizado void clear () {map.clear (); } @Override public string toString () {StringBuilder sb = new StringBuilder (); para (entrada map.entry: map.entryset ()) {sb.append (string.format ("%s:%s", entry.getKey (), entry.getValue ())); } return sb.ToString (); }} Lista vinculada de LRU Cache + implementación de hashmap
NOTA: Esta implementación no se agita. Si se usa en un entorno múltiple, debe agregar sincronizado a métodos relevantes para lograr operaciones seguras de hilo.
paquete cn.lzrabbit.structure.lru; import java.util.hashmap;/*** creado por Liuzhao el 14-5-12. */public class lrucache1 <k, v> {private final int max_cache_size; entrada privada primero; Entrada privada Última; Hashmap privado <k, entrada <k, v >> hashmap; public lrucache1 (int cachesize) {max_cache_size = cachesize; hashmap = new Hashmap <K, Entrada <k, V >> (); } public void put (k key, v value) {Entry entry = getEntry (clave); if (entry == null) {if (hashmap.size ()> = max_cache_size) {hashmap.remove (last.key); removelast (); } entrada = nueva entrada (); Entry.Key = Key; } Entry.Value = Value; Movetofirst (entrada); hashmap.put (clave, entrada); } public v get (k key) {entry <k, v> entry = getEntry (clave); if (entrada == nulo) return null; Movetofirst (entrada); devolver entrada.value; } public void remove (k key) {Entry Entry = GetEntry (clave); if (entrada! = null) {if (entry.pre! = null) entry.pre.next = entry.next; if (Entry.Next! = NULL) Entry.next.Pre = Entry.Pre; if (entrada == Primero) Primero = Entry.Next; if (entrada == Last) Last = Entry.Pre; } hashmap.remove (clave); } private void Movetofirst (entrada de entrada) {if (entrada == primero) return; if (Entry.Pre! = NULL) Entry.Pre.Next = Entry.Next; if (Entry.Next! = NULL) Entry.next.Pre = Entry.Pre; if (entrada == Last) Last = Last.Pre; if (first == null || last == null) {primero = last = entry; devolver; } entry.next = primero; primero.pre = entrada; primero = entrada; primero = entrada; entry.pre = null; } private void removelast () {if (last! = null) {last = last.pre; if (last == null) primero = null; else Last.next = null; }} Entrada privada <k, v> getEntry (k key) {return hashmap.get (clave); } @Override public string toString () {StringBuilder sb = new StringBuilder (); Entrada entrada = primero; while (entry! = null) {sb.append (string.format ("%s:%s", entry.key, entry.value)); Entry = Entry.next; } return sb.ToString (); } Entrada de clase <k, v> {entrada pública pre; entrada pública siguiente; Public K Key; valor público v; }} Implementación de FIFO de Linkedhashmap
FIFO es la abreviatura de la primera salida de la primera entrada, que a menudo se llama First-In, First-Out. Por defecto, LinkedHashMap se guarda en el orden de adición. Solo necesitamos reescribir el método RemoLDestEdentry para implementar fácilmente un caché FIFO. La versión simplificada del código de implementación es la siguiente.
final int cachesize = 5; Linkedhashmap <integer, string> lru = new LinkedHashMap <Integer, String> () {@Override Boolean Boolean RemoLDestentRy (MAP.Entry <Integer, String> Elderly) {Tamaño de retorno ()> Cachesize; }}; Ejemplo de llamada
paquete cn.lzrabbit.structure.lru; import cn.lzrabbit.itest; import java.util.linkedhashmap; import java.util.map;/*** creado por Liuzhao el 14-5-15. */public class lrucachetest {public static void main (string [] args) lanza la excepción {System.out.println ("Inicio ..."); lrucache1 (); lrucache2 (); lrucache3 (); lrucache4 (); System.out.println ("Over ..."); } static void lrucache1 () {system.out.println (); System.out.println ("============================ Lru 链表实现 ============================="); 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 ("===================================================================================================== =================================================================================================================================================================================================================================================. Linkedhashmap (herencia) 实现 ============================ "); 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 ("============================ Lru Linkedhashmap (Delegación) 实现 ==========================="); 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 ("============================ FIFO Linkedhashmap 默认实现 ============================"); final int cachesize = 5; Linkedhashmap <Integer, String> lru = new Linkedhashmap <Integer, String> () {@Override Boolean Boolean RemoLDestentry (MAP.Entry <Integer, String> Eldest) {return size ()> Cachesize; }}; 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 (); }}Resultados de ejecución
"C:/Archivos de programa (x86) /java/jdk1.6.0_10/bin/java" -didea.launcher.port = 7535 "-didea.launcher.bin.path = c:/programas (x86)/jetbrains/ideal 13.0.2/bin" -dfile.en Archivos (x86) /java/jdk1.6.0_10/jre/lib/charsets.jar;c:/program archivos (x86) /java/jdk1.6.0_10/jre/lib/deploy.jar;c:/program files (x86) /java/jdk1.6.0_10/jre/lib/javaws.jar;c:/program (x86) /java/jdk1.6.0_10/jre/lib/jce.jar;c:/program files (x86) /java/jdk1.6.0_10/jre/lib/jce.jar;c:/program archivos (x86) /java/jdk1.6.0_10/jre/lib/management-agent.jar;c:/program files files (x86) /java/jdk1.6.0_10/jre/lib/plugin.jar;c:/program archivos (x86) /java/jdk1.6.0_10/jre/lib/resources.jar;c:/program files (x86) /java/jdk1.6.0_10/jre/lib/rt.jar;c:/program (x86) /java/jdk1.6.0_10/jre/ext/dnsns.jar;c:/program files (x86) /Java/jdk1.6.6.0_10/jre/ext/localedata.jar;c:/program (x86) /java/jdk1.6.0_10/jre/lib/ext/sunjce_provider.jar;c (x86) /java/jdk1.6.0_10/jre/lib/ext/sunmscapi.jar;c:/program archivos (x86) /java/jdk1.6.0_10/jre/lib/ext/sunpkcs11.jar ;d:/svn/projects/Java/Java.algorithm (x86)/JetBrains/IntelliJ Idea 13.0.2/lib/Idea_rt.jar "com.intellij.rt.execution.application.appmain Mainstart...======================================================================================================= ==================================================================================================================== =========================================================================================================================================================================================== S ==================================================================================================================== Linkedhashmap (herencia) Implementación ============================================================== =========================================================================== =========================================================================== =========================================================================== 1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 =================================== FIFO Linkedhashmap predeterminado Implementación ====================================================== {1 = 11, 2 = 11, 3 = 11, 4 = 11, 5 = 11} {3 = 11, 4 = 11, 5 = 11, 6 = 66, 7 = 77} sobre ... proceso terminado con exitGracias por leer, espero que pueda ayudarte. ¡Gracias por su apoyo para este sitio!