Java LRU (menos usado recentemente) Explicação detalhada
LRU é a abreviação de menos recentemente usada. É traduzido como "uso mais recente". O cache da LRU é implementado usando esse princípio. Simplificando, é para armazenar em cache uma certa quantidade de dados. Quando o limite definido for excedido, alguns dados expirados serão excluídos. Por exemplo, cache 10.000 dados. Quando os dados são inferiores a 10.000, você pode adicioná -los à vontade. Quando excede 10.000, você precisa adicionar novos dados. Ao mesmo tempo, você precisa excluir os dados expirados para garantir que possamos armazenar 10.000 dados no máximo. Como determinar quais dados expirados para excluir? Se você usar o algoritmo LRU para implementá -lo, excluirá os dados mais antigos. Sem dizer muito, vamos falar sobre a versão Java da implementação de cache da LRU.
Geralmente, existem duas opções para implementar o cache da LRU em Java. Um é usar o LinkedHashmap, e o outro é projetar sua própria estrutura de dados e usar a lista vinculada + hashmap.
LinkedHashmap Implementação de cache LRU
O LinkedHashmap próprio implementou o armazenamento seqüencial. Por padrão, ele é armazenado na ordem de adição de elementos. Ele também pode permitir o armazenamento na ordem de acesso, ou seja, os dados de leitura recentemente são colocados na frente e os dados de leitura mais antigos são colocados no final. Em seguida, ele também possui um método para determinar se deve excluir os dados mais antigos. O padrão é retornar falso, ou seja, não excluir dados. O método de usar o LinkedHashmap para implementar o cache da LRU é implementar uma expansão simples do LinkedHashmap. Há duas maneiras de se estender, uma é a herança e a outra é a delegação. O método específico é usado para depender de preferências pessoais.
// Um construtor de LinkedHashmap. Quando o painel de acesso ao parâmetro for verdadeiro, ele será classificado na ordem de acesso. O acesso mais recente é colocado em primeiro lugar e o acesso mais antigo é colocado atrás do Public LinkedHashMap (int InitialCapacity, Float LoadFactor, Boolean AccessOrder) {Super (InitialCapacity, LoadFactor); this.accessOrder = AccessOrder;} // LinkedHashMap vem com o método para determinar se deve excluir o elemento mais antigo. Ele retorna false por padrão, ou seja, não exclui dados antigos. // O que precisamos fazer é reescrever esse método e excluir dados antigos quando certas condições forem atendidas booleanas protegidas removetEstentry (map.entry <k, v> mais velho) {return false;} Implementação de Cache LRU Cache (herança) LinkedHashmap (herança)
O método de herança é relativamente simples de implementar e a interface do mapa é implementada. Ao usar um ambiente multithread, você pode usar o método Coleções.SynchronizedMap () para implementar operações seguras de threads.
pacote cn.lzrabbit.structure.lru; importar java.util.linkedhashmap; importar java.util.map;/*** criado por Liuzhao em 14-5-15. */classe pública lrucache2 <k, v> estende o LinkedHashMap <k, v> {private final int max_cache_size; public lrucache2 (int em armazenamento em cache) {super ((int) math.ceil (cacheize / 0,75) + 1, 0,75f, true); Max_cache_size = em cache; } @Override Boolean protegido RemoveLDestEntry (map.entry idosos) {return size ()> max_cache_size; } @Override public string tostring () {stringbuilder sb = new stringbuilder (); para (map.entry <k, v> entrada: entrada ()) {sb.append (string.format ("%s:%s", entrada.getKey (), entrada.getValue ())); } return sb.toString (); }}Esta é uma implementação relativamente padrão. Ainda é um pouco pesado escrever assim em uso real. Ao escrever como esse método mais prático, ele economiza o problema de ver uma classe separadamente.
final int em cacheSize = 100; map <string, string> map = new LinkedHashMap <string, string> ((int) math.ceil (cacheize / 0.75f) + 1, 0,75f, true) {@Override Boolean RemonelDestentry (map.entRy <String, string> eSerDeRLE) {Return size ()> cachEn. }}; Implementação de Cache LRU Cache LinkedHashmap (delegação)
A implementação do método de delegação é mais elegante, mas como a interface do mapa não é implementada, a sincronização do encadeamento precisa ser feita por você mesmo.
pacote cn.lzrabbit.structure.lru; importar java.util.linkedhashmap; importar java.util.map; importar java.util.set;/*** criado por Liuzhao em 14-5-13. */public class Lrucache3 <k, v> {private final int max_cache_size; Float final privado default_load_factor = 0,75f; LinkedHashmap <k, v> mapa; public lrucache3 (int em armazenamento em cache) {max_cache_size = em cache; // Calcule a capactação do hashmap com base no cacheize e nos fatores de carregamento. +1 Verifique se a expansão do hashmap não será acionada quando o limite superior do cacheize for atingido. int capacidade = (int) math.ceil (max_cache_size / default_load_factor) + 1; map = new LinkedHashMap (capacidade, default_load_factor, true) {@Override protegido boolean removelDestentry (map.entry idosos) {return size ()> max_cache_size; }}; } public sincronizado void put (Key k, V valor) {map.put (chave, valor); } public sincronizado v get (k key) {return map.get (key); } public sincronizado void Remover (K -key) {map.remove (chave); } public Sincronized Set <pap.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 (Map.Entry Entry: map.entrySet ()) {sb.append (string.format ("%s:%s", entrada.getKey (), entrada.getValue ()); } return sb.toString (); }} Lista vinculada da LRU Cache + implementação de hashmap
Nota: Esta implementação não é impressionada. Se usado em um ambiente com vários threads, você precisa adicionar métodos relevantes para obter operações seguras de encadeamento.
pacote cn.lzrabbit.structure.lru; importar java.util.hashmap;/*** Criado por Liuzhao em 14-5-12. */public class Lrucache1 <k, v> {private final int max_cache_size; entrada privada primeiro; entrada privada por último; Hashmap privado <k, entrada <k, v >> hashmap; public lrucache1 (int em armazenamento em cache) {max_cache_size = em cache; hashmap = novo hashmap <k, entrada <k, v >> (); } public void put (Key K, V Value) {Entrada Entrada = Getentry (chave); if (entradas == null) {if (hashmap.size ()> = max_cache_size) {hashmap.remove (last.key); removelast (); } entrada = new Entry (); entrada.Key = Key; } entrada.value = value; movetofirst (entrada); hashmap.put (chave, entrada); } public v get (K -Key) {Entrada <k, v> Entrada = getentry (key); if (entradas == null) retorna nulo; movetofirst (entrada); retornar entrada.value; } public void Remover (K -key) {Entrada de entrada = getentry (chave); if (entradas! = null) {if (entradas.pre! = null) entrada.pre.next = entradas.next; if (Entry.Next! = NULL) Entry.Next.Pre = Entry.pre; if (entradas == primeiro) primeiro = entrada.next; if (entradas == last) last = Entry.pre; } hashmap.remove (chave); } private void movetofirst (entrada de entrada) {if (entradas == primeiro) return; if (entradas.pre! = null) entrada.pre.next = entradas.next; if (Entry.Next! = NULL) Entry.Next.Pre = Entry.pre; if (entrada == last) last = last.pre; if (primeiro == null || last == null) {primeiro = last = entradas; retornar; } entrada.Next = primeiro; primeiro.pre = entrada; primeiro = entrada; primeiro = entrada; entrada.pre = null; } private void removeLast () {if (last! = null) {last = last.pre; if (last == null) primeiro = nulo; else last.next = null; }} Entrada privada <k, v> getentry (k -key) {return hashmap.get (key); } @Override public string tostring () {stringbuilder sb = new stringbuilder (); Entrada de entrada = primeiro; while (entrada! = null) {sb.append (string.format ("%s:%s", entrada.key, entrada.value)); entrada = entrada.next; } return sb.toString (); } classe de entrada <k, v> {public entrada pre; entrada pública a seguir; Public K Key; Public V Value; }} FIFO Implementação de LinkedHashmap
O FIFO é a abreviação da primeira saída da primeira entrada, que é frequentemente chamada de primeiro in, primeiro a sair. Por padrão, o LinkedHashmap é salvo na ordem de adição. Só precisamos reescrever o método RemonelDestEntry para implementar facilmente um cache do FIFO. A versão simplificada do código de implementação é a seguinte.
Final int cacheSize = 5; LinkedHashMap <Integer, String> lru = new LinkedHashMap <Integer, String> () {@Override protegido boolean RemowDelDestentry (map.entry <Inteiro, String> idosa) {Return size ()> cachesize; }}; Ligue para o exemplo
pacote cn.lzrabbit.structure.lru; importar cn.lzrabbit.itest; importar java.util.linkedhashmap; importar java.util.map;/*** criado por liuzhao em 14-5-15. */public class LrucacheTest {public static void main (string [] args) lança exceção {System.out.println ("start ..."); lrucache1 (); lrucache2 (); lrucache3 (); lrucache4 (); System.out.println ("Over ..."); } void static lrucache1 () {System.out.println (); System.out.println ("=========================== LRU 链表实现 ============================="); Lrucache1 <Inteiro, 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 (herança) 实现 ============================ "); Lrucache2 <Inteiro, 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 (); } estático void lrucache3 () {System.out.println (); System.out.println ("=========================== LRU LinkedHashMap (delegação) 实现 ==============================); Lrucache3 <Inteiro, 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 (); } void static lrucache4 () {System.out.println (); System.out.println ("=========================== FIFO LinkedHashMap 默认实现 ============================"); Final Int CacheSize = 5; LinkedHashmap <Inteiro, String> lru = new LinkedHashMap <Integer, String> () {@Override Boolean protegido RemoveLDestentry (map.entry <Integer, String> mais velho) {Tamanho do retorno ()> 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 execução
"C:/Arquivos de programas (x86) /java/jdk1.6.0_10/bin/java" -didea.launcher.port = 7535 "-didea.launcher.bin.path = c:/arquivos de programa (x86)/jetbrains/Intellij IDEIRA 13.0.2/bin" -e jetbrains/Intellij *.0.2/bin " -bin" - (x86) /java/jdk1.6.0_10/jre/lib/charsets.jar ;c:/program Files (x86) /java/jdk1.6.0_10/jre/lib/deploy.jar; (x86) /java/jdk1.6.0_10/jre/lib/javaws.jar ;c:/program Files (x86) /java/jdk1.6.0_10/jre/lib/jce.jar; (x86) /java/jdk1.6.0_10/jre/lib/jce.jar ;c:/program Files (x86) /java/jdk1.6.0_10/jre/lib/management-agent.jar; (x86) /java/jdk1.6.0_10/jre/lib/plugin.jar ;c:/program Files (x86) /java/jdk1.6.0_10/jre/lib/resources.jar; (x86) /java/jdk1.6.0_10/jre/lib/rt.jar ;c:/program Files (x86) /java/jdk1.6.0_10/jre/ext/dnsns.jar; (x86) /java/jdk1.6.0_10/jre/ext/localedata.jar ;c./program Files (x86) /java/jdk1.6.0_10/jre/lib/ext/sunjce_provider.Jar; (x86) /java/jdk1.6.0_10/jre/lib/ext/sunmscapi.jar ;c:/program Files (x86)/Java/jdk1.6.0_10/jre/lib/ext/sunpkcs11.jar;D:/SVN/projects/Java/Java.Algorithm/target/test-classes;D:/SVN/projects/Java/Java.Algorithm/target/classes;C:/Program Files (x86)/jetbrains/Intellij Idea 13.0.2/lib/Idea_rt.jar "com.intellij.rt.execution.application.appmain Mainstart...======================================================================================================= ==================================================================================================================== =================================================================================================================== ==================================================================================================================== LinkedHashmap (herança) Implementação ============================================================= ============================================================================ =========================================================================== ============================================================================ 1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 ====================================== implementation=================================================={1=11, 2=11, 3=11, 4=11, 5=11}{3=11, 4=11, 5=11, 6=66, 7=77}over...Process finished with exit code 0Obrigado pela leitura, espero que isso possa ajudá -lo. Obrigado pelo seu apoio a este site!