Come implementeresti una cache LRU in Java?

Per favore non dire EHCache o OSCache, ecc. Supponiamo per gli scopi di questa domanda che voglio implementare il mio usando solo l’SDK (learning by doing). Dato che la cache verrà utilizzata in un ambiente con multithreading, quali strutture dati useresti? Ne ho già implementato uno utilizzando LinkedHashMap e Collections # synchronizedMap , ma sono curioso di sapere se una qualsiasi delle nuove collezioni concorrenti sarebbe migliore.

AGGIORNAMENTO: stavo solo leggendo le ultime notizie di Yegge quando ho trovato questo nugget:

Se hai bisogno di un accesso costante e vuoi mantenere l’ordine di inserzione, non puoi fare di meglio di LinkedHashMap, una struttura dati davvero meravigliosa. L’unico modo in cui potrebbe essere più meraviglioso è se ci fosse una versione concorrente. Ma ahimè.

Stavo pensando quasi esattamente la stessa cosa prima di andare con l’ LinkedHashMap + Collections#synchronizedMap ho menzionato sopra. Bello sapere che non avevo semplicemente trascurato qualcosa.

Sulla base delle risposte fino ad ora, sembra che la mia migliore scommessa per un LRU altamente concorrente sia estendere ConcurrentHashMap usando la stessa logica utilizzata da LinkedHashMap .

    Mi piacciono molti di questi suggerimenti, ma per ora penso che rimarrò con LinkedHashMap + Collections.synchronizedMap . Se lo faccio rivisitare in futuro, probabilmente lavorerò ad estendere ConcurrentHashMap nello stesso modo in cui LinkedHashMap estende HashMap .

    AGGIORNARE:

    A richiesta, ecco il succo della mia attuale implementazione.

     private class LruCache extends LinkedHashMap { private final int maxEntries; public LruCache(final int maxEntries) { super(maxEntries + 1, 1.0f, true); this.maxEntries = maxEntries; } /** * Returns true if this LruCache has more entries than the maximum specified when it was * created. * * 

    * This method does not modify the underlying Map; it relies on the implementation of * LinkedHashMap to do that, but that behavior is documented in the JavaDoc for * LinkedHashMap. *

    * * @param eldest * the Entry in question; this implementation doesn't care what it is, since the * implementation is only dependent on the size of the cache * @return true if the oldest * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry) */ @Override protected boolean removeEldestEntry(final Map.Entry eldest) { return super.size() > maxEntries; } } Map example = Collections.synchronizedMap(new LruCache(CACHE_SIZE));

    Se lo CacheBuilder facendo di nuovo da zero, CacheBuilder di Guava.

    Questo è il secondo round.

    Il primo round è stato quello che ho scoperto, quindi ho riletto i commenti con il dominio un po ‘più radicato nella mia testa.

    Quindi, ecco la versione più semplice con un test unitario che mostra funziona basato su alcune altre versioni.

    Prima la versione non simultanea:

     import java.util.LinkedHashMap; import java.util.Map; public class LruSimpleCache implements LruCache { Map map = new LinkedHashMap ( ); public LruSimpleCache (final int limit) { map = new LinkedHashMap  (16, 0.75f, true) { @Override protected boolean removeEldestEntry(final Map.Entry eldest) { return super.size() > limit; } }; } @Override public void put ( K key, V value ) { map.put ( key, value ); } @Override public V get ( K key ) { return map.get(key); } //For testing only @Override public V getSilent ( K key ) { V value = map.get ( key ); if (value!=null) { map.remove ( key ); map.put(key, value); } return value; } @Override public void remove ( K key ) { map.remove ( key ); } @Override public int size () { return map.size (); } public String toString() { return map.toString (); } } 

    La vera bandiera traccerà l’accesso di prende e mette. Vedi JavaDocs. Il removeEdelstEntry senza il flag vero per il costruttore implementerebbe solo una cache FIFO (vedi le note seguenti su FIFO e removeEldestEntry).

    Ecco il test che dimostra che funziona come una cache LRU:

     public class LruSimpleTest { @Test public void test () { LruCache  cache = new LruSimpleCache<> ( 4 ); cache.put ( 0, 0 ); cache.put ( 1, 1 ); cache.put ( 2, 2 ); cache.put ( 3, 3 ); boolean ok = cache.size () == 4 || die ( "size" + cache.size () ); cache.put ( 4, 4 ); cache.put ( 5, 5 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == 4 || die (); ok |= cache.getSilent ( 5 ) == 5 || die (); cache.get ( 2 ); cache.get ( 3 ); cache.put ( 6, 6 ); cache.put ( 7, 7 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == null || die (); ok |= cache.getSilent ( 5 ) == null || die (); if ( !ok ) die (); } 

    Ora per la versione concorrente …

    pacchetto org.boon.cache;

     import java.util.LinkedHashMap; import java.util.Map; import java.util.concurrent.locks.ReadWriteLock; import java.util.concurrent.locks.ReentrantReadWriteLock; public class LruSimpleConcurrentCache implements LruCache { final CacheMap[] cacheRegions; private static class CacheMap extends LinkedHashMap { private final ReadWriteLock readWriteLock; private final int limit; CacheMap ( final int limit, boolean fair ) { super ( 16, 0.75f, true ); this.limit = limit; readWriteLock = new ReentrantReadWriteLock ( fair ); } protected boolean removeEldestEntry ( final Map.Entry eldest ) { return super.size () > limit; } @Override public V put ( K key, V value ) { readWriteLock.writeLock ().lock (); V old; try { old = super.put ( key, value ); } finally { readWriteLock.writeLock ().unlock (); } return old; } @Override public V get ( Object key ) { readWriteLock.writeLock ().lock (); V value; try { value = super.get ( key ); } finally { readWriteLock.writeLock ().unlock (); } return value; } @Override public V remove ( Object key ) { readWriteLock.writeLock ().lock (); V value; try { value = super.remove ( key ); } finally { readWriteLock.writeLock ().unlock (); } return value; } public V getSilent ( K key ) { readWriteLock.writeLock ().lock (); V value; try { value = this.get ( key ); if ( value != null ) { this.remove ( key ); this.put ( key, value ); } } finally { readWriteLock.writeLock ().unlock (); } return value; } public int size () { readWriteLock.readLock ().lock (); int size = -1; try { size = super.size (); } finally { readWriteLock.readLock ().unlock (); } return size; } public String toString () { readWriteLock.readLock ().lock (); String str; try { str = super.toString (); } finally { readWriteLock.readLock ().unlock (); } return str; } } public LruSimpleConcurrentCache ( final int limit, boolean fair ) { int cores = Runtime.getRuntime ().availableProcessors (); int stripeSize = cores < 2 ? 4 : cores * 2; cacheRegions = new CacheMap[ stripeSize ]; for ( int index = 0; index < cacheRegions.length; index++ ) { cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair ); } } public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) { cacheRegions = new CacheMap[ concurrency ]; for ( int index = 0; index < cacheRegions.length; index++ ) { cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair ); } } private int stripeIndex ( K key ) { int hashCode = key.hashCode () * 31; return hashCode % ( cacheRegions.length ); } private CacheMap map ( K key ) { return cacheRegions[ stripeIndex ( key ) ]; } @Override public void put ( K key, V value ) { map ( key ).put ( key, value ); } @Override public V get ( K key ) { return map ( key ).get ( key ); } //For testing only @Override public V getSilent ( K key ) { return map ( key ).getSilent ( key ); } @Override public void remove ( K key ) { map ( key ).remove ( key ); } @Override public int size () { int size = 0; for ( CacheMap cache : cacheRegions ) { size += cache.size (); } return size; } public String toString () { StringBuilder builder = new StringBuilder (); for ( CacheMap cache : cacheRegions ) { builder.append ( cache.toString () ).append ( '\n' ); } return builder.toString (); } } 

    Puoi capire perché copro prima la versione non simultanea. Quanto sopra tenta di creare delle strisce per ridurre la contesa del blocco. Quindi abbiamo hash la chiave e poi cerca quell’hash per trovare la cache effettiva. Ciò rende la dimensione limite più di un suggerimento / ipotesi approssimativa entro una discreta quantità di errore, a seconda di quanto sia ben distribuito l’algoritmo di hash delle chiavi.

    Ecco il test per dimostrare che la versione concorrente probabilmente funziona. 🙂 (Test sotto fuoco sarebbe il vero modo).

     public class SimpleConcurrentLRUCache { @Test public void test () { LruCache  cache = new LruSimpleConcurrentCache<> ( 1, 4, false ); cache.put ( 0, 0 ); cache.put ( 1, 1 ); cache.put ( 2, 2 ); cache.put ( 3, 3 ); boolean ok = cache.size () == 4 || die ( "size" + cache.size () ); cache.put ( 4, 4 ); cache.put ( 5, 5 ); puts (cache); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == 4 || die (); ok |= cache.getSilent ( 5 ) == 5 || die (); cache.get ( 2 ); cache.get ( 3 ); cache.put ( 6, 6 ); cache.put ( 7, 7 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); cache.put ( 8, 8 ); cache.put ( 9, 9 ); ok |= cache.getSilent ( 4 ) == null || die (); ok |= cache.getSilent ( 5 ) == null || die (); puts (cache); if ( !ok ) die (); } @Test public void test2 () { LruCache  cache = new LruSimpleConcurrentCache<> ( 400, false ); cache.put ( 0, 0 ); cache.put ( 1, 1 ); cache.put ( 2, 2 ); cache.put ( 3, 3 ); for (int index =0 ; index < 5_000; index++) { cache.get(0); cache.get ( 1 ); cache.put ( 2, index ); cache.put ( 3, index ); cache.put(index, index); } boolean ok = cache.getSilent ( 0 ) == 0 || die (); ok |= cache.getSilent ( 1 ) == 1 || die (); ok |= cache.getSilent ( 2 ) != null || die (); ok |= cache.getSilent ( 3 ) != null || die (); ok |= cache.size () < 600 || die(); if ( !ok ) die (); } } 

    Questo è l'ultimo post .. Il primo post che ho eliminato in quanto era un LFU non una cache di LRU.

    Ho pensato di dare un altro andare. Stavo cercando di trovare la versione più semplice di una cache LRU utilizzando il JDK standard senza troppa implementazione.

    Ecco cosa mi è venuto in mente. Il mio primo tentativo è stato un po 'disastroso mentre implementavo un LFU al posto di LRU e poi ho aggiunto FIFO e il supporto di LRU ad esso ... e poi ho capito che stava diventando un mostro. Poi ho iniziato a parlare con il mio amico John che era a malapena interessato, e poi ho descritto in modo approfondito come ho implementato un LFU, LRU e FIFO e come si poteva passare con un semplice ENUM arg, e poi ho capito che tutto quello che volevo davvero era una semplice LRU. Quindi ignora il post precedente da me e fammi sapere se vuoi vedere una cache LRU / LFU / FIFO che è commutabile tramite un enum ... no? Ok .. eccolo.

    La LRU più semplice ansible usando solo il JDK. Ho implementato sia una versione concorrente che una versione non concorrente.

    Ho creato un'interfaccia comune (è il minimalismo che probabilmente manca alcune funzionalità che vorresti ma funziona per i miei casi d'uso, ma lascia che se vuoi vedere la funzione XYZ fammi sapere ... vivo per scrivere codice). .

     public interface LruCache { void put ( KEY key, VALUE value ); VALUE get ( KEY key ); VALUE getSilent ( KEY key ); void remove ( KEY key ); int size (); } 

    Potresti chiederti cos'è getSilent . Lo uso per i test. getSilent non modifica il punteggio LRU di un articolo.

    Prima quella non concomitante ....

     import java.util.Deque; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; public class LruCacheNormal implements LruCache { Map map = new HashMap<> (); Deque queue = new LinkedList<> (); final int limit; public LruCacheNormal ( int limit ) { this.limit = limit; } public void put ( KEY key, VALUE value ) { VALUE oldValue = map.put ( key, value ); /*If there was already an object under this key, then remove it before adding to queue Frequently used keys will be at the top so the search could be fast. */ if ( oldValue != null ) { queue.removeFirstOccurrence ( key ); } queue.addFirst ( key ); if ( map.size () > limit ) { final KEY removedKey = queue.removeLast (); map.remove ( removedKey ); } } public VALUE get ( KEY key ) { /* Frequently used keys will be at the top so the search could be fast.*/ queue.removeFirstOccurrence ( key ); queue.addFirst ( key ); return map.get ( key ); } public VALUE getSilent ( KEY key ) { return map.get ( key ); } public void remove ( KEY key ) { /* Frequently used keys will be at the top so the search could be fast.*/ queue.removeFirstOccurrence ( key ); map.remove ( key ); } public int size () { return map.size (); } public String toString() { return map.toString (); } } 

    Queue.removeFirstOccurrence è un'operazione potenzialmente costosa se si dispone di una cache di grandi dimensioni. Uno potrebbe prendere LinkedList come esempio e aggiungere una mappa hash di ricerca inversa da elemento a nodo per rendere le operazioni di rimozione MOLTO PIÙ VELOCI e più coerenti. Ho iniziato anch'io, ma poi ho capito che non ne avevo bisogno. Ma forse...

    Quando viene chiamato put , la chiave viene aggiunta alla coda. Quando viene chiamato get , la chiave viene rimossa e riaggiunta nella parte superiore della coda.

    Se la tua cache è piccola e la costruzione di un object è costosa, questa dovrebbe essere una buona cache. Se la tua cache è veramente grande, la ricerca lineare potrebbe essere un collo di bottiglia soprattutto se non hai aree calde di cache. Più intensi sono i punti caldi, più velocemente la ricerca lineare come elementi caldi è sempre in cima alla ricerca lineare. Ad ogni modo ... ciò che serve per andare più veloce è scrivere un'altra LinkedList che ha un'operazione di rimozione che ha l'elemento inverso alla ricerca del nodo da rimuovere, quindi la rimozione sarebbe veloce quanto la rimozione di una chiave da una mappa hash.

    Se hai una cache inferiore a 1.000 elementi, questo dovrebbe funzionare correttamente.

    Ecco un semplice test per mostrare le sue operazioni in azione.

     public class LruCacheTest { @Test public void test () { LruCache cache = new LruCacheNormal<> ( 4 ); cache.put ( 0, 0 ); cache.put ( 1, 1 ); cache.put ( 2, 2 ); cache.put ( 3, 3 ); boolean ok = cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 0 ) == 0 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); cache.put ( 4, 4 ); cache.put ( 5, 5 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 0 ) == null || die (); ok |= cache.getSilent ( 1 ) == null || die (); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == 4 || die (); ok |= cache.getSilent ( 5 ) == 5 || die (); if ( !ok ) die (); } } 

    L'ultima cache di LRU era single threaded, e per favore non avvolgerla in un qualcosa sincronizzato ....

    Ecco una pugnalata a una versione concorrente.

     import java.util.Deque; import java.util.LinkedList; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.locks.ReentrantLock; public class ConcurrentLruCache implements LruCache { private final ReentrantLock lock = new ReentrantLock (); private final Map map = new ConcurrentHashMap<> (); private final Deque queue = new LinkedList<> (); private final int limit; public ConcurrentLruCache ( int limit ) { this.limit = limit; } @Override public void put ( KEY key, VALUE value ) { VALUE oldValue = map.put ( key, value ); if ( oldValue != null ) { removeThenAddKey ( key ); } else { addKey ( key ); } if (map.size () > limit) { map.remove ( removeLast() ); } } @Override public VALUE get ( KEY key ) { removeThenAddKey ( key ); return map.get ( key ); } private void addKey(KEY key) { lock.lock (); try { queue.addFirst ( key ); } finally { lock.unlock (); } } private KEY removeLast( ) { lock.lock (); try { final KEY removedKey = queue.removeLast (); return removedKey; } finally { lock.unlock (); } } private void removeThenAddKey(KEY key) { lock.lock (); try { queue.removeFirstOccurrence ( key ); queue.addFirst ( key ); } finally { lock.unlock (); } } private void removeFirstOccurrence(KEY key) { lock.lock (); try { queue.removeFirstOccurrence ( key ); } finally { lock.unlock (); } } @Override public VALUE getSilent ( KEY key ) { return map.get ( key ); } @Override public void remove ( KEY key ) { removeFirstOccurrence ( key ); map.remove ( key ); } @Override public int size () { return map.size (); } public String toString () { return map.toString (); } } 

    Le principali differenze sono l'uso di ConcurrentHashMap invece di HashMap, e l'uso del Lock (avrei potuto passare alla sincronizzazione, ma ...).

    Non l'ho ancora testato, ma sembra una semplice cache LRU che potrebbe funzionare nell'80% dei casi d'uso in cui è necessaria una semplice mappa LRU.

    Accolgo con favore il feedback, eccetto il perché non usi la libreria a, b, o c. La ragione per cui non uso sempre una libreria è perché non sempre voglio che ogni file di guerra sia 80 MB, e scrivo le librerie quindi tendo a rendere le librerie plug-in con una soluzione abbastanza buona e qualcuno può collegarle -in un altro provider di cache, se lo desiderano. 🙂 Non so mai quando qualcuno potrebbe aver bisogno di Guava o ehcache o qualcos'altro che non voglio includerli, ma se faccio il plug-in di cache, non li escluderò neanche.

    La riduzione delle dipendenze ha una sua ricompensa. Mi piacerebbe avere un feedback su come renderlo ancora più semplice o più veloce o entrambi.

    Anche se qualcuno sa di pronto a partire ....

    Ok .. So cosa stai pensando ... Perché non usa solo removeEldest entry da LinkedHashMap, e beh, dovrei ma .... ma .. ma .. Sarebbe un FIFO non un LRU e noi eravamo cercando di implementare un LRU.

      Map map = new LinkedHashMap () { @Override protected boolean removeEldestEntry ( Map.Entry eldest ) { return this.size () > limit; } }; 

    Questo test non riesce per il codice sopra ...

      cache.get ( 2 ); cache.get ( 3 ); cache.put ( 6, 6 ); cache.put ( 7, 7 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == null || die (); ok |= cache.getSilent ( 5 ) == null || die (); 

    Quindi ecco una cache FIFO veloce e sporca usando removeEldestEntry.

     import java.util.*; public class FifoCache implements LruCache { final int limit; Map map = new LinkedHashMap () { @Override protected boolean removeEldestEntry ( Map.Entry eldest ) { return this.size () > limit; } }; public LruCacheNormal ( int limit ) { this.limit = limit; } public void put ( KEY key, VALUE value ) { map.put ( key, value ); } public VALUE get ( KEY key ) { return map.get ( key ); } public VALUE getSilent ( KEY key ) { return map.get ( key ); } public void remove ( KEY key ) { map.remove ( key ); } public int size () { return map.size (); } public String toString() { return map.toString (); } } 

    I FIFO sono veloci. Nessuna ricerca in giro. Potresti far fronte a una FIFO di fronte a una LRU e gestiresti abbastanza bene la maggior parte delle voci calde. Una LRU migliore avrà bisogno dell'elemento inverso per la funzione Nodo.

    Comunque ... ora che ho scritto un codice, lasciami passare le altre risposte e vedere cosa mi è mancato ... la prima volta che li ho scansionati.

    LinkedHashMap è O (1), ma richiede la sincronizzazione. Non c’è bisogno di reinventare la ruota lì.

    2 opzioni per aumentare la concorrenza:

    1. Crea più LinkedHashMap e hash in loro: esempio: LinkedHashMap[4], index 0, 1, 2, 3 . Sulla chiave, key%4 (o binary OR su [key, 3] ) per scegliere quale mappa eseguire un put / get / remove.

    2. Si potrebbe fare un ‘quasi’ LRU estendendo ConcurrentHashMap e avendo una mappa hash collegata come la struttura in ciascuna delle regioni al suo interno. Il blocco si verifica in modo più granulare rispetto a LinkedHashMap che è sincronizzato. Su una put o putIfAbsent solo un blocco sulla testa e sulla coda dell’elenco (per regione). In una rimozione o ottenere l’intera regione deve essere bloccato. Sono curioso di sapere se gli elenchi collegati Atomic di qualche tipo potrebbero aiutare qui – probabilmente così per il capo della lista. Forse per di più.

    La struttura non manterrebbe l’ordine totale, ma solo l’ordine per regione. Finché il numero di voci è molto più grande del numero di regioni, questo è abbastanza buono per la maggior parte delle cache. Ogni regione dovrà avere il proprio numero di voci, che verrebbe utilizzato piuttosto che il conteggio globale per il trigger di sfratto. Il numero predefinito di regioni in una ConcurrentHashMap è 16, che è sufficiente per la maggior parte dei server oggi.

    1. sarebbe più facile da scrivere e più veloce in caso di concorrenza moderata.

    2. sarebbe più difficile scrivere ma scalare molto meglio ad una concorrenza molto alta. Sarebbe più lento per un accesso normale (proprio come ConcurrentHashMap è più lento di HashMap dove non c’è concorrenza)

    Ci sono due implementazioni open source.

    Apache Solr ha ConcurrentLRUCache: https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html

    C’è un progetto open source per una ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/

    Vorrei prendere in considerazione l’utilizzo di java.util.concurrent.PriorityBlockingQueue , con priorità determinata da un contatore “numberOfUses” in ogni elemento. Sarei molto, molto attento a correggere tutta la mia sincronizzazione, poiché il contatore “numberOfUses” implica che l’elemento non può essere immutabile.

    L’object elemento sarebbe un wrapper per gli oggetti nella cache:

     class CacheElement { private final Object obj; private int numberOfUsers = 0; CacheElement(Object obj) { this.obj = obj; } ... etc. } 

    La cache di LRU può essere implementata utilizzando ConcurrentLinkedQueue e ConcurrentHashMap che possono essere utilizzati anche nello scenario di multithreading. Il capo della coda è quell’elemento che è rimasto in coda più a lungo. La coda della coda è quell’elemento che è rimasto in coda nel minor tempo ansible. Quando un elemento esiste nella mappa, possiamo rimuoverlo da LinkedQueue e inserirlo nella coda.

     import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentLinkedQueue; public class LRUCache { private ConcurrentHashMap map; private ConcurrentLinkedQueue queue; private final int size; public LRUCache(int size) { this.size = size; map = new ConcurrentHashMap(size); queue = new ConcurrentLinkedQueue(); } public V get(K key) { //Recently accessed, hence move it to the tail queue.remove(key); queue.add(key); return map.get(key); } public void put(K key, V value) { //ConcurrentHashMap doesn't allow null key or values if(key == null || value == null) throw new NullPointerException(); if(map.containsKey(key) { queue.remove(key); } if(queue.size() >= size) { K lruKey = queue.poll(); if(lruKey != null) { map.remove(lruKey); } } queue.add(key); map.put(key,value); } } 

    Spero che questo ti aiuti .

     import java.util.*; public class Lru { public static  Map lruCache(final int maxSize) { return new LinkedHashMap(maxSize*4/3, 0.75f, true) { private static final long serialVersionUID = -3588047435434569014L; @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > maxSize; } }; } public static void main(String[] args ) { Map lru = Lru.lruCache(2); lru.put("1", "1"); lru.put("2", "2"); lru.put("3", "3"); System.out.println(lru); } } 

    Ecco la mia implementazione per LRU. Ho usato PriorityQueue, che funziona fondamentalmente come FIFO e non thread-safe. Comparatore usato basato sulla creazione del tempo di pagina e basato sull’esecuzione dell’ordine delle pagine per il tempo meno utilizzato.

    Pagine da prendere in considerazione: 2, 1, 0, 2, 8, 2, 4

    La pagina aggiunta alla cache è: 2
    La pagina aggiunta alla cache è: 1
    La pagina aggiunta alla cache è: 0
    Pagina: 2 già esistenti nella cache. Ultimo orario di accesso aggiornato
    Errore di pagina, PAGINA: 1, Sostituito con PAGINA: 8
    La pagina aggiunta alla cache è: 8
    Pagina: 2 già esistenti nella cache. Ultimo orario di accesso aggiornato
    Errore di pagina, PAGINA: 0, Sostituito con PAGINA: 4
    La pagina aggiunta alla cache è: 4

    PRODUZIONE

    LRUCache Pages
    ————-
    PageName: 8, PageCreationTime: 1365957019974
    PageName: 2, PageCreationTime: 1365957020074
    PageName: 4, PageCreationTime: 1365957020174

    inserire il codice qui

     import java.util.Comparator; import java.util.Iterator; import java.util.PriorityQueue; public class LRUForCache { private PriorityQueue priorityQueue = new PriorityQueue(3, new LRUPageComparator()); public static void main(String[] args) throws InterruptedException { System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4"); System.out.println("----------------------------------------------\n"); LRUForCache cache = new LRUForCache(); cache.addPageToQueue(new LRUPage("2")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("1")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("0")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("2")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("8")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("2")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("4")); Thread.sleep(100); System.out.println("\nLRUCache Pages"); System.out.println("-------------"); cache.displayPriorityQueue(); } public synchronized void addPageToQueue(LRUPage page){ boolean pageExists = false; if(priorityQueue.size() == 3){ Iterator iterator = priorityQueue.iterator(); while(iterator.hasNext()){ LRUPage next = iterator.next(); if(next.getPageName().equals(page.getPageName())){ /* wanted to just change the time, so that no need to poll and add again. but elements ordering does not happen, it happens only at the time of adding to the queue In case somebody finds it, plz let me know. */ //next.setPageCreationTime(page.getPageCreationTime()); priorityQueue.remove(next); System.out.println("Page: " + page.getPageName() + " already exisit in cache. Last accessed time updated"); pageExists = true; break; } } if(!pageExists){ // enable it for printing the queue elemnts //System.out.println(priorityQueue); LRUPage poll = priorityQueue.poll(); System.out.println("Page Fault, PAGE: " + poll.getPageName()+", Replaced with PAGE: "+page.getPageName()); } } if(!pageExists){ System.out.println("Page added into cache is : " + page.getPageName()); } priorityQueue.add(page); } public void displayPriorityQueue(){ Iterator iterator = priorityQueue.iterator(); while(iterator.hasNext()){ LRUPage next = iterator.next(); System.out.println(next); } } } class LRUPage{ private String pageName; private long pageCreationTime; public LRUPage(String pagename){ this.pageName = pagename; this.pageCreationTime = System.currentTimeMillis(); } public String getPageName() { return pageName; } public long getPageCreationTime() { return pageCreationTime; } public void setPageCreationTime(long pageCreationTime) { this.pageCreationTime = pageCreationTime; } @Override public boolean equals(Object obj) { LRUPage page = (LRUPage)obj; if(pageCreationTime == page.pageCreationTime){ return true; } return false; } @Override public int hashCode() { return (int) (31 * pageCreationTime); } @Override public String toString() { return "PageName: " + pageName +", PageCreationTime: "+pageCreationTime; } } class LRUPageComparator implements Comparator{ @Override public int compare(LRUPage o1, LRUPage o2) { if(o1.getPageCreationTime() > o2.getPageCreationTime()){ return 1; } if(o1.getPageCreationTime() < o2.getPageCreationTime()){ return -1; } return 0; } } 

    Ecco l’implementazione della cache LRU simultanea con le migliori prestazioni testata senza blocco sincronizzato:

     public class ConcurrentLRUCache { private final int maxSize; private ConcurrentHashMap map; private ConcurrentLinkedQueue queue; public ConcurrentLRUCache(final int maxSize) { this.maxSize = maxSize; map = new ConcurrentHashMap(maxSize); queue = new ConcurrentLinkedQueue(); } /** * @param key - may not be null! * @param value - may not be null! */ public void put(final Key key, final Value value) { if (map.containsKey(key)) { queue.remove(key); // remove the key from the FIFO queue } while (queue.size() >= maxSize) { Key oldestKey = queue.poll(); if (null != oldestKey) { map.remove(oldestKey); } } queue.add(key); map.put(key, value); } /** * @param key - may not be null! * @return the value associated to the given key or null */ public Value get(final Key key) { return map.get(key); } 

    }

    This is the LRU cache I use, which encapsulates a LinkedHashMap and handles concurrency with a simple synchronize lock guarding the juicy spots. It “touches” elements as they are used so that they become the “freshest” element again, so that it is actually LRU. I also had the requirement of my elements having a minimum lifespan, which you can also think of as “maximum idle time” permitted, then you’re up for eviction.

    However, I agree with Hank’s conclusion and accepted answer — if I were starting this again today, I’d check out Guava’s CacheBuilder .

     import java.util.HashMap; import java.util.LinkedHashMap; import java.util.Map; public class MaxIdleLRUCache { final static private int IDEAL_MAX_CACHE_ENTRIES = 128; public interface DeadElementCallback { public void notify(KK key, VV element); } private Object lock = new Object(); private long minAge; private HashMap> cache; public MaxIdleLRUCache(long minAgeMilliseconds) { this(minAgeMilliseconds, IDEAL_MAX_CACHE_ENTRIES); } public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries) { this(minAgeMilliseconds, idealMaxCacheEntries, null); } public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries, final DeadElementCallback callback) { this.minAge = minAgeMilliseconds; this.cache = new LinkedHashMap>(IDEAL_MAX_CACHE_ENTRIES + 1, .75F, true) { private static final long serialVersionUID = 1L; // This method is called just after a new entry has been added public boolean removeEldestEntry(Map.Entry> eldest) { // let's see if the oldest entry is old enough to be deleted. We don't actually care about the cache size. long age = System.currentTimeMillis() - eldest.getValue().birth; if (age > MaxIdleLRUCache.this.minAge) { if ( callback != null ) { callback.notify(eldest.getKey(), eldest.getValue().payload); } return true; // remove it } return false; // don't remove this element } }; } public void put(KK key, VV value) { synchronized ( lock ) { // System.out.println("put->"+key+","+value); cache.put(key, new Item(value)); } } public VV get(KK key) { synchronized ( lock ) { // System.out.println("get->"+key); Item item = getItem(key); return item == null ? null : item.payload; } } public VV remove(String key) { synchronized ( lock ) { // System.out.println("remove->"+key); Item item = cache.remove(key); if ( item != null ) { return item.payload; } else { return null; } } } public int size() { synchronized ( lock ) { return cache.size(); } } private Item getItem(KK key) { Item item = cache.get(key); if (item == null) { return null; } item.touch(); // idle the item to reset the timeout threshold return item; } private static class Item { long birth; T payload; Item(T payload) { this.birth = System.currentTimeMillis(); this.payload = payload; } public void touch() { this.birth = System.currentTimeMillis(); } } } 

    Well for a cache you will generally be looking up some piece of data via a proxy object, (a URL, String….) so interface-wise you are going to want a map. but to kick things out you want a queue like structure. Internally I would maintain two data structures, a Priority-Queue and a HashMap. heres an implementation that should be able to do everything in O(1) time.

    Here’s a class I whipped up pretty quick:

     import java.util.HashMap; import java.util.Map; public class LRUCache { int maxSize; int currentSize = 0; Map> map; LinkedList queue; public LRUCache(int maxSize) { this.maxSize = maxSize; map = new HashMap>(); queue = new LinkedList(); } private void freeSpace() { K k = queue.remove(); map.remove(k); currentSize--; } public void put(K key, V val) { while(currentSize >= maxSize) { freeSpace(); } if(map.containsKey(key)) {//just heat up that item get(key); return; } ListNode ln = queue.add(key); ValueHolder rv = new ValueHolder(val, ln); map.put(key, rv); currentSize++; } public V get(K key) { ValueHolder rv = map.get(key); if(rv == null) return null; queue.remove(rv.queueLocation); rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue return rv.value; } } class ListNode { ListNode prev; ListNode next; K value; public ListNode(K v) { value = v; prev = null; next = null; } } class ValueHolder { V value; ListNode queueLocation; public ValueHolder(V value, ListNode ql) { this.value = value; this.queueLocation = ql; } } class LinkedList { ListNode head = null; ListNode tail = null; public ListNode add(K v) { if(head == null) { assert(tail == null); head = tail = new ListNode(v); } else { tail.next = new ListNode(v); tail.next.prev = tail; tail = tail.next; if(tail.prev == null) { tail.prev = head; head.next = tail; } } return tail; } public K remove() { if(head == null) return null; K val = head.value; if(head.next == null) { head = null; tail = null; } else { head = head.next; head.prev = null; } return val; } public void remove(ListNode ln) { ListNode prev = ln.prev; ListNode next = ln.next; if(prev == null) { head = next; } else { prev.next = next; } if(next == null) { tail = prev; } else { next.prev = prev; } } } 

    Ecco come funziona. Keys are stored in a linked list with the oldest keys in the front of the list (new keys go to the back) so when you need to ‘eject’ something you just pop it off the front of the queue and then use the key to remove the value from the map. When an item gets referenced you grab the ValueHolder from the map and then use the queuelocation variable to remove the key from its current location in the queue and then put it at the back of the queue (its now the most recently used). Adding things is pretty much the same.

    I’m sure theres a ton of errors here and I haven’t implemented any synchronization. but this class will provide O(1) adding to the cache, O(1) removal of old items, and O(1) retrieval of cache items. Even a trivial synchronization (just synchronize every public method) would still have little lock contention due to the run time. If anyone has any clever synchronization tricks I would be very interested. Also, I’m sure there are some additional optimizations that you could implement using the maxsize variable with respect to the map.

    Have a look at ConcurrentSkipListMap . It should give you log(n) time for testing and removing an element if it is already contained in the cache, and constant time for re-adding it.

    You’d just need some counter etc and wrapper element to force ordering of the LRU order and ensure recent stuff is discarded when the cache is full.

    Here is my short implementation, please criticize or improve it!

     package util.collection; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentLinkedQueue; /** * Limited size concurrent cache map implementation.
    * LRU: Least Recently Used.
    * If you add a new key-value pair to this cache after the maximum size has been exceeded, * the oldest key-value pair will be removed before adding. */ public class ConcurrentLRUCache { private final int maxSize; private int currentSize = 0; private ConcurrentHashMap map; private ConcurrentLinkedQueue queue; public ConcurrentLRUCache(final int maxSize) { this.maxSize = maxSize; map = new ConcurrentHashMap(maxSize); queue = new ConcurrentLinkedQueue(); } private synchronized void freeSpace() { Key key = queue.poll(); if (null != key) { map.remove(key); currentSize = map.size(); } } public void put(Key key, Value val) { if (map.containsKey(key)) {// just heat up that item put(key, val); return; } while (currentSize >= maxSize) { freeSpace(); } synchronized(this) { queue.add(key); map.put(key, val); currentSize++; } } public Value get(Key key) { return map.get(key); } }

    Here’s my own implementation to this problem

    simplelrucache provides threadsafe, very simple, non-distributed LRU caching with TTL support. It provides two implementations:

    • Concurrent based on ConcurrentLinkedHashMap
    • Synchronized based on LinkedHashMap

    You can find it here: http://code.google.com/p/simplelrucache/

    I’m looking for a better LRU cache using Java code. Is it possible for you to share your Java LRU cache code using LinkedHashMap and Collections#synchronizedMap ? Currently I’m using LRUMap implements Map and the code works fine, but I’m getting ArrayIndexOutofBoundException on load testing using 500 users on the below method. The method moves the recent object to front of the queue.

     private void moveToFront(int index) { if (listHead != index) { int thisNext = nextElement[index]; int thisPrev = prevElement[index]; nextElement[thisPrev] = thisNext; if (thisNext >= 0) { prevElement[thisNext] = thisPrev; } else { listTail = thisPrev; } //old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1 // prev[0 old head] = new head right ; next[new head] = old head prevElement[index] = -1; nextElement[index] = listHead; prevElement[listHead] = index; listHead = index; } } 

    get(Object key) and put(Object key, Object value) method calls the above moveToFront method.

    Wanted to add comment to the answer given by Hank but some how I am not able to – please treat it as comment

    LinkedHashMap maintains access order as well based on parameter passed in its constructor It keeps doubly lined list to maintain order (See LinkedHashMap.Entry)

    @Pacerier it is correct that LinkedHashMap keeps same order while iteration if element is added again but that is only in case of insertion order mode.

    this is what I found in java docs of LinkedHashMap.Entry object

      /** * This method is invoked by the superclass whenever the value * of a pre-existing entry is read by Map.get or modified by Map.set. * If the enclosing Map is access-ordered, it moves the entry * to the end of the list; otherwise, it does nothing. */ void recordAccess(HashMap m) { LinkedHashMap lm = (LinkedHashMap)m; if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } } 

    this method takes care of moving recently accessed element to end of the list. So all in all LinkedHashMap is best data structure for implementing LRUCache.

    Another thought and even a simple implementation using LinkedHashMap collection of Java.

    LinkedHashMap provided method removeEldestEntry and which can be overridden in the way mentioned in example. By default implementation of this collection structure is false. If its true and size of this structure goes beyond the initial capacity than eldest or older elements will be removed.

    We can have a pageno and page content in my case pageno is integer and pagecontent i have kept page number values string.

     import java.util.LinkedHashMap; import java.util.Map; /** * @author Deepak Singhvi * */ public class LRUCacheUsingLinkedHashMap { private static int CACHE_SIZE = 3; public static void main(String[] args) { System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99"); System.out.println("----------------------------------------------\n"); // accessOrder is true, so whenever any page gets changed or accessed, // its order will change in the map, LinkedHashMap lruCache = new LinkedHashMap(CACHE_SIZE, .75F, true) { private static final long serialVersionUID = 1L; protected boolean removeEldestEntry(Map.Entry eldest) { return size() > CACHE_SIZE; } }; lruCache.put(2, "2"); lruCache.put(1, "1"); lruCache.put(0, "0"); System.out.println(lruCache + " , After first 3 pages in cache"); lruCache.put(2, "2"); System.out.println(lruCache + " , Page 2 became the latest page in the cache"); lruCache.put(8, "8"); System.out.println(lruCache + " , Adding page 8, which removes eldest element 2 "); lruCache.put(2, "2"); System.out.println(lruCache+ " , Page 2 became the latest page in the cache"); lruCache.put(4, "4"); System.out.println(lruCache+ " , Adding page 4, which removes eldest element 1 "); lruCache.put(99, "99"); System.out.println(lruCache + " , Adding page 99, which removes eldest element 8 "); } } 

    Result of above code execution is as follows:

      Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99 -------------------------------------------------- {2=2, 1=1, 0=0} , After first 3 pages in cache {2=2, 1=1, 0=0} , Page 2 became the latest page in the cache {1=1, 0=0, 8=8} , Adding page 8, which removes eldest element 2 {0=0, 8=8, 2=2} , Page 2 became the latest page in the cache {8=8, 2=2, 4=4} , Adding page 4, which removes eldest element 1 {2=2, 4=4, 99=99} , Adding page 99, which removes eldest element 8 

    Android offers an implementation of an LRU Cache . The code is clean and straightforward.