Utilisation LinkedHashMap à mettre en œuvre de cache LRU

J'essayais de mettre en œuvre un cache LRU à l'aide de LinkedHashMap.
Dans la documentation de LinkedHashMap (http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html), il est dit:

Noter que l'ordre d'insertion n'est pas affectée si une clé est à nouveau inséré dans la carte.

Mais quand je fais ce qui suit met

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int size;

    public static void main(String[] args) {
        LRUCache<Integer, Integer> cache = LRUCache.newInstance(2);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(1, 1);
        cache.put(3, 3);

        System.out.println(cache);
    }

    private LRUCache(int size) {
        super(size, 0.75f, true);
        this.size = size;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > size;
    }

    public static <K, V> LRUCache<K, V> newInstance(int size) {
        return new LRUCache<K, V>(size);
    }

}

La sortie est

{1=1, 3=3}

Qui indique que la ré-inséré n'a affecté l'ordre.
Quelqu'un sait de toute explication?

Je me demande, êtes-vous de le faire dans un but précis? Parce que Java fournit déjà un WeakHashMap qui fournit cette fonctionnalité. docs.oracle.com/javase/7/docs/api/java/util/WeakHashMap.html
Si la commande ne sera pas affectée par la ré-insertion. L'ordre doit être {2=2, 3=3}, depuis le {1=1} est ajouté en premier et ré-inséré.
WeakHashMap ne pas faire ce que vous pense. Ce n'est pas la même chose qu'un LRU cache.
c'est exactement ce que je pense. Il fournit une structure de données qui permet de stocker en cache les valeurs sans se soucier de les éliminer si elles ne sont pas mentionnées ailleurs dans le code. Qui est un des ordures collectées façon de mettre en œuvre un cache LRU. Si vous n'avez pas l'obligation d'essuyer les anciennes valeurs (pour l'actualisation des questions, et c'est le but précis je parlais), alors il répond exactement à ce problème en permettant de Java en vue de leur libération juste quand il y a la nécessité.
Je suis pour la mise en œuvre de cette pratique de codage. Je pense à l'aide de la weakHashMap est une meilleure façon, si je suis à l'aide de la LRU pour tenir temp objets et laissez GC s'occuper de tout. Merci

OriginalL'auteur Lei Chen | 2014-12-15

16

Comme l'a souligné m. Jeffrey, vous utilisez accessOrder. Lorsque vous avez créé le LinkedHashMap, le troisième paramètre de spécifier comment l'ordre est modifié.
```
"true for access-order, false for insertion-order"
```
Pour plus de détails sur la mise en œuvre de la LRU, vous pouvez regarder ce
http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

Merci, le matériau est très utile.
Le lien ne doit pas utiliser une solution avec LinkedHashMap.

OriginalL'auteur 1736964698
4

Mais vous n'êtes pas à l'aide de la commande d'insertion, vous êtes à l'aide de ordre d'accès.

ordre d'itération est l'ordre dans lequel ses entrées dernière
accessible, du moins récemment accédé à la plus récemment (accès à la commande)

...

L'invocation de la déposer ou récupérer des résultats de la méthode d'accès à la
entrée correspondante

C'est donc l'état de votre cache que vous la modifiez:
```
    LRUCache<Integer, Integer> cache = LRUCache.newInstance(2);
    cache.put(1, 1); //{ 1=1 }
    cache.put(2, 2); //{ 1=1, 2=2 }
    cache.put(1, 1); //{ 2=2, 1=1 }
    cache.put(3, 3); //{ 1=1, 3=3 }
```
OriginalL'auteur Jeffrey

Voici ma mise en œuvre en utilisant LinkedHashMap dans AccessOrder. Il vous permettra de déplacer la dernière accessibles élément à l'avant qui n'engage que O(1) frais généraux, car les éléments qui sous-tendent sont organisés dans une liste à double liaison, tandis que sont également indexées en fonction de hachage. Donc le get/put/top_newest_one opérations ont toutes un coût en O(1).

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int maxSize;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.maxSize = capacity;
    }

    //return -1 if miss
    public int get(int key) {
        Integer v = super.get(key);
        return v == null ? -1 : v;
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return this.size() > maxSize; //must override it if used in a fixed cache
    }
}

OriginalL'auteur Emilio Zhao

I also implement LRU cache with little change in code. I have tested and it works perfectly as concept of LRU cache.
package com.first.misc;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCachDemo {
public static void main(String aa[]){
LRUCache<String, String> lruCache = new LRUCache<>(3);
lruCache.cacheable("test", "test");
lruCache.cacheable("test1", "test1");
lruCache.cacheable("test2", "test2");
lruCache.cacheable("test3", "test3");
lruCache.cacheable("test4", "test4");
lruCache.cacheable("test", "test");
System.out.println(lruCache.toString());
}
}
class LRUCache<K, T>{
private Map<K,T> cache;
private int windowSize;
public LRUCache( final int windowSize) {
this.windowSize = windowSize;
this.cache = new LinkedHashMap<K, T>(){
@Override
protected boolean removeEldestEntry(Map.Entry<K, T> eldest) {
return size() > windowSize;
}
};
}
//put data in cache
public void cacheable(K key, T data){
//check key is exist of not if exist than remove and again add to make it recently used
//remove element if window size is exhaust
if(cache.containsKey(key)){
cache.remove(key);
}
cache.put(key,data);
}
//evict functioanlity
@Override
public String toString() {
return "LRUCache{" +
"cache=" + cache.toString() +
", windowSize=" + windowSize +
'}';
}
}

OriginalL'auteur Rajeev Rathor

Vous devez vous connecter pour publier un commentaire.