java - Utilice LinkedHashMap para implementar el caché LRU

insert

Question

Estaba intentando implementar un caché LRU utilizando LinkedHashMap. En la documentación de LinkedHashMap ( http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html ), dice:

Tenga en cuenta que el orden de inserción no se ve afectado si se vuelve a insertar una clave en el mapa.

Pero cuando hago los siguientes pone

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 salida es

{1=1, 3=3}

Lo que indica que el reinsertado afectó el pedido. ¿Alguien sabe alguna explicación?

Answer 1

Aquí está mi implementación utilizando LinkedHashMap en AccessOrder. Moverá el último elemento al que se accedió al frente, lo que solo incurre en O (1) porque los elementos subyacentes están organizados en una lista con doble enlace, mientras que también se indexan por función de hash. Por lo tanto, las operaciones get / put / top_newest_one cuestan 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
    }
}

Answer 2

Pero no está utilizando el orden de inserción, está utilizando el orden de acceso .

el orden de iteración es el orden en el que se accedió por última vez a sus entradas, desde el último acceso más reciente al más reciente (orden de acceso)

...

Al invocar el método de poner u obtener se obtiene un acceso a la entrada correspondiente

Así que este es el estado de su caché a medida que lo modifica:

    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 }

Answer 3

Como lo señaló Jeffrey , usted está usando accessOrder. Cuando creó el LinkedHashMap, el tercer parámetro especifica cómo se cambia el orden.

"true for access-order, false for insertion-order"

Para una implementación más detallada de LRU, puede consultar este http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

Answer 4

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 +
                ''}'';
    }
}