Java LRU (la moins récemment utilisée) Explication détaillée
Le LRU est l'abréviation des moins récemment utilisés. Il est traduit par "dernière utilisation". Le cache LRU est implémenté en utilisant ce principe. Autrement dit, il s'agit de mettre en cache une certaine quantité de données. Lorsque le seuil défini est dépassé, certaines données expirées seront supprimées. Par exemple, nous mettons en cache 10 000 éléments de données. Lorsque les données sont inférieures à 10 000, vous pouvez l'ajouter à volonté. Lorsqu'il dépasse 10 000, vous devez ajouter de nouvelles données. Dans le même temps, vous devez supprimer les données expirées pour vous assurer que nous pouvons mettre en cache 10 000 éléments de données au maximum. Comment déterminer les données expirées à supprimer? Si vous utilisez l'algorithme LRU pour l'implémenter, vous supprimerez les données les plus anciennes. Sans dire grand-chose, parlons de la version Java de la mise en œuvre de LRU Cache.
Il existe généralement deux options pour implémenter le cache LRU en Java. L'un consiste à utiliser LinkedHashMap, et l'autre consiste à concevoir votre propre structure de données et à utiliser Linked List + Hashmap.
Implémentation LinkedHashmap de Cache LRU
LinkedHashMap lui-même a implémenté le stockage séquentiel. Par défaut, il est stocké dans l'ordre d'ajouter des éléments. Il peut également permettre le stockage de l'ordre d'accès, c'est-à-dire que les données récemment lues sont placées à l'avant et les premières données de lecture sont placées à la fin. Ensuite, il a également une méthode pour déterminer s'il faut supprimer les données les plus anciennes. La valeur par défaut est de renvoyer false, c'est-à-dire de ne pas supprimer les données. La méthode d'utilisation de LinkedHashmap pour implémenter le cache LRU consiste à implémenter une expansion simple de LinkedHashMap. Il y a deux façons d'étendre, l'une est l'héritage et l'autre est la délégation. La méthode spécifique est utilisée pour dépendre des préférences personnelles.
// Un constructeur de LinkedHashmap. Lorsque l'entrave d'accès paramètre est vrai, il sera trié dans l'ordre d'accès. L'accès le plus récent est placé en premier et l'accès le plus ancien est placé derrière le public LinkedHashmap (int initialCapacity, float lostfactor, boolean accessOrder) {super (initialCapacity, loadFactor); this.AccessOrder = AccessOrder;} // LinkedHashMap est livré avec une méthode pour déterminer s'il faut supprimer l'élément le plus ancien. Il renvoie False par défaut, c'est-à-dire qu'il ne supprime pas les anciennes données. // Ce que nous devons faire, c'est réécrire cette méthode et supprimer les anciennes données lorsque certaines conditions sont remplies Boolean devayElDestentry (map.entry <k, v> aîné) {return false;} Implémentation LRU Cache LinkedHashmap (héritage)
La méthode d'héritage est relativement simple à implémenter et l'interface MAP est implémentée. Lorsque vous utilisez un environnement multi-thread, vous pouvez utiliser la méthode Collection.SynchronizedMap () pour implémenter les opérations de filetage.
Package cn.lzrabbit.structure.lru; import java.util.linkedhashmap; import java.util.map; / ** * créé par liuzhao le 14-5-15. * / public class lrucache2 <k, v> étend 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 Protected booléen devatelDestentry (map.entry âgé) {return size ()> max_cache_size; } @Override public String toString () {StringBuilder sb = new StringBuilder (); pour (map.entry <k, v> entrée: entryset ()) {sb.append (string.format ("% s:% s", entry.getKey (), entry.getValue ())); } return sb.toString (); }}Il s'agit d'une implémentation relativement standard. Il est encore un peu lourd d'écrire comme celui-ci dans une utilisation réelle. Lorsque vous l'écrivez comme cette méthode plus pratique, cela évite de voir une classe séparément.
final int cachesize = 100; map <string, string> map = new LinkedHashmap <String, String> ((int) math.ceil (cachesize / 0.75f) + 1, 0.75f, true) {@Override Protected boolean devatelDestenTry (map.enry <string, string> Elderly) {return size ()> cacheSize; }}; Implémentation LRU Cache LinkedHashmap (délégation)
La mise en œuvre de la méthode de délégation est plus élégante, mais comme l'interface MAP n'est pas implémentée, la synchronisation du thread doit être effectuée par vous-même.
Package cn.lzrabbit.structure.lru; import java.util.linkedhashmap; import java.util.map; import java.util.set; / ** * créé par liuzhao le 14-5-13. * / public class lrucache3 <k, v> {private final int max_cache_size; Float final privé default_load_factor = 0,75f; LinkedHashmap <k, v> carte; public lrucache3 (int cacheSize) {max_cache_size = cacheSize; // Calculez la capactiy du hashmap en fonction des facteurs de cache et de chargement. +1 Assurez-vous que l'expansion de Hashmap ne sera pas déclenchée lorsque la limite supérieure de cache est atteinte. int la capacité = (int) math.ceil (max_cache_size / default_load_factor) + 1; map = new LinkedHashMap (capacité, default_load_factor, true) {@Override Protected boolean devatelDestentry (map.entry elderly) {return size ()> max_cache_size; }}; } public synchronisé void put (k key, v valeur) {map.put (key, valeur); } public synchronisé v get (k key) {return map.get (key); } public synchronisé void dispos (k key) {map.remove (key); } set synchronisé public <map.entry <k, v >> getall () {return map.entryset (); } public synchronisé int size () {return map.size (); } public synchronisé void clear () {map.clear (); } @Override public String toString () {StringBuilder sb = new StringBuilder (); pour (map.entry entrée: map.entryset ()) {sb.append (string.format ("% s:% s", entry.getKey (), entry.getValue ())); } return sb.toString (); }} Liste liée de LRU Cache + Implémentation HashMap
Remarque: Cette implémentation est non thread. Si vous êtes utilisé dans un environnement multi-thread, vous devez ajouter synchronisé à des méthodes pertinentes pour réaliser des opérations en filetage.
Package cn.lzrabbit.structure.lru; import java.util.hashmap; / ** * créé par Liuzhao le 14-5-12. * / public class lrucache1 <k, v> {private final int max_cache_size; Entrée privée d'abord; Entrée privée en dernier; Hashmap privé <k, entrée <k, v >> hashmap; public lrucache1 (int cacheSize) {max_cache_size = cacheSize; hashmap = new hashmap <k, entrée <k, v >> (); } public void put (k key, V valeur) {entrée d'entrée = gentry (key); if (entry == null) {if (hashmap.size ()> = max_cache_size) {hashmap.remove (last.key); Removelast (); } entrée = nouvelle entrée (); entrée.Key = key; } entrée.value = valeur; moveToFirst (entrée); hashmap.put (clé, entrée); } public v get (k key) {entrée <k, v> entrée = gentry (key); if (entry == null) renvoie null; moveToFirst (entrée); Retour Entrée.Value; } public void retire (k key) {entrée entrée = gentry (key); if (entry! = null) {if (entry.pre! = null) entry.pre.next = entry.next; if (entry.next! = null) entry.next.pre = entrée.pre; if (entry == First) First = Entry.Next; if (entry == dernier) dernier = entrée.pre; } hashmap.remove (key); } private void MoveToFirst (entrée d'entrée) {if (entry == premier) return; if (entry.pre! = null) entry.pre.next = entry.next; if (entry.next! = null) entry.next.pre = entrée.pre; if (entry == Last) Last = Last.Pre; if (first == null || dernier == null) {premier = dernier = entrée; retour; } entry.next = premier; first.pre = entrée; premier = entrée; premier = entrée; entrée.pre = null; } private void removelast () {if (last! = null) {last = last.pre; if (dernier == null) d'abord = null; else last.next = null; }} Entrée privée <k, v> gentry (k key) {return hashmap.get (key); } @Override public String toString () {StringBuilder sb = new StringBuilder (); Entrée d'entrée = premier; while (entrée! = null) {sb.append (string.format ("% s:% s", entry.key, entry.value)); entrée = entrée.Next; } return sb.toString (); } Entrée de classe <k, v> {Public Entry Pre; Entrée publique Suivant; Public K Key; Valeur publique V; }} Implémentation FIFO de LinkedHashmap
FIFO est l'abréviation de la première sortie de première entrée, qui est souvent appelée premier-in, premier-out. Par défaut, LinkedHashmap est enregistré dans l'ordre d'addition. Nous avons juste besoin de réécrire la méthode de dentillelDestentry pour implémenter facilement un cache FIFO. La version simplifiée du code d'implémentation est la suivante.
final int cacheSize = 5; LinkedHashMap <Integer, String> lRu = new LinkedHashMap <Integer, String> () {@Override Protected Boolean devatelDestentry (Map.Entry <Integer, String> Elderly) {return size ()> cachesize; }}; Exemple d'appel
package cn.lzrabbit.structure.lru; import Cn.lzrabbit.itest; import java.util.linkedhashmap; import java.util.map; / ** * créé par liuzhao le 14-5-15. * / public class lrucachestEst {public static void main (String [] args) lève exception {System.out.println ("start ..."); 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 (); } statique <t> void lrucache2 () {System.out.println (); System.out.println("======================================================================= =================================================================================================. LinkedHashmap (héritage) 实现 ========================== "); 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 (); } statique void lrucache3 () {System.out.println (); System.out.println ("========================== LRU LinkedHashmap (délégation) 实现 ========================"); 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 (); } statique void lrucache4 () {System.out.println (); System.out.println ("========================== FIFO LinkedHashmap 默认实现 =========================="); final int cachesize = 5; LinkedHashMap <Integer, String> lRu = new LinkedHashMap <Integer, String> () {@Override Protected boolean devatelDestentry (map.entry <nteger, 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 (); }}Résultats en cours d'exécution
"C: / Program Files (x86) /java/jdk1.6.0_10/bin/java" -didea.launcher.port = 7535 "-didea.launcher.bin.path = c: / programme files (x86) / jetbrains / intellej Files (x86) /java/jdk1.6.0_10/jre/lib/charsets.jar;c:/program Files (x86) /java/jdk1.6.0_10/jre/lib/deploy.jar;c:/program Fichiers (x86) /java/jdk1.6.0_10/jre/lib/javaws.jar;c:/program files (x86) /java/jdk1.6.0_10/jre/lib/jce.jar;c:/program Files (x86) /java/jdk1.6.0_10/jre/lib/jce.jar; (x86) /java/jdk1.6.0_10/jre/lib/management-agent.jar;c:/program files (x86) /java/jdk1.6.0_10/jre/lib/plugin.jar;c:/program Files (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 Fichiers Fichiers (x86) /java/jdk1.6.0_10/jre/ext/dnsns.jar ;c:/program files (x86) /java/jdk1.6.0_10/jre/ext/localedata.jar;c:/program Fichiers Fichiers (x86) /java/jdk1.6.0_10/jre/lib/ext/sunjce_provider.jar;c:/program files (x86) /java/jdk1.6.0_10/jre/lib/ext/sunmscapi.jar; (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; (x86) / JetBrains / Intellij Idea 13.0.2 / lib / idea_rt.jar "com.intellij.rt.execution.application.appmain Mainstart ... ===================================================================================================================================================================================================================. ====================================================================================================================================. ===================================================================================================================================. ====================================================================================================================================. LinkedHashmap (héritage) implémentation ================================================================================================================== ===============================================================. ==============================================================. ===============================================================. 1:11 2:11 3:11 4:11 5:11 5:11 6:66 2:11 7:77 4:11 ======================================================. implémentation ================================================ {1 = 11, 2 = 11, 3 = 11, 46, 7 = 77} {3 = 11, 4 = 11, 5 = 11, 66.Merci d'avoir lu, j'espère que cela peut vous aider. Merci pour votre soutien à ce site!