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