Usa LinkedHashMap per implementare la cache LRU

Question

Stavo cercando di implementare una cache LRU usando LinkedHashMap. Nella documentazione di LinkedHashMap (http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html), si dice:

Nota che l'ordine di inserimento non è interessato se un tasto viene nuovamente inserito nella mappa.

Ma quando faccio le seguenti mette

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); 
    } 

} 

L'uscita è

{1=1, 3=3} 

che indica che la ri-inserito ha influenzato l'ordine. Qualcuno conosce qualche spiegazione?

Answer 1

Come sottolineato da @Jeffrey, si sta utilizzando accessOrder. Quando hai creato la LinkedHashMap, il terzo parametro specifica come viene modificato l'ordine.

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

Per un'attuazione più dettagliata delle LRU, si può guardare a questo http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

Answer 2

Ma non si sta utilizzando l'ordine di inserzione, si sta utilizzando access order.

ordine di iterazione è l'ordine in cui i suoi inserimenti loro ultima accessibile, da almeno ha avuto accesso a più di recente (accesso-ordine)

...

Invocare il metodo put o get comporta un accesso alla voce corrispondente

Quindi questo è lo stato di cache come 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

Ecco la mia implementazione utilizzando LinkedHashMap in AccessOrder. Sposterà in avanti l'ultimo elemento a cui è stato effettuato l'accesso, il che comporta solo overhead O (1) perché gli elementi sottostanti sono organizzati in una lista doppiamente collegata mentre sono anche indicizzati dalla funzione hash. Quindi le operazioni get/put/top_newest_one costano tutte 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 
    } 
}