¿Cómo implementaría un caché LRU en Java?

169

Por favor, no diga EHCache o OSCache, etc. Suponga a los fines de esta pregunta que quiero implementar el mío usando solo el SDK (aprender haciendo). Dado que el caché se usará en un entorno multiproceso, ¿qué estructuras de datos usaría? Ya he implementado uno usando LinkedHashMap y Collections # synchronizedMap , pero tengo curiosidad por saber si alguna de las nuevas colecciones concurrentes serían mejores candidatos.

ACTUALIZACIÓN: Estaba leyendo lo último de Yegge cuando encontré esta pepita:

Si necesita acceso de tiempo constante y desea mantener el orden de inserción, no puede hacerlo mejor que LinkedHashMap, una estructura de datos realmente maravillosa. La única forma en que podría ser más maravilloso es si hubiera una versión concurrente. Pero Ay.

Estaba pensando casi exactamente lo mismo antes de comenzar con la implementación LinkedHashMap+ Collections#synchronizedMapque mencioné anteriormente. Es bueno saber que no había pasado por alto algo.

Según las respuestas hasta ahora, parece que mi mejor apuesta para una LRU altamente concurrente sería extender ConcurrentHashMap usando algo de la misma lógica que LinkedHashMapusa.

Hank Gay
fuente
O(1)versión requerida: stackoverflow.com/questions/23772102/…
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
Muy pregunta similar también aquí
Mifeet

Respuestas:

102

Me gustan muchas de estas sugerencias, pero por ahora creo que me quedaré con LinkedHashMap+ Collections.synchronizedMap. Si yo vuelva a visitar en el futuro, probablemente voy a trabajar en la ampliación ConcurrentHashMapde la misma manera LinkedHashMapse extiende HashMap.

ACTUALIZAR:

A pedido, aquí está la esencia de mi implementación actual.

private class LruCache<A, B> extends LinkedHashMap<A, B> {
    private final int maxEntries;

    public LruCache(final int maxEntries) {
        super(maxEntries + 1, 1.0f, true);
        this.maxEntries = maxEntries;
    }

    /**
     * Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was
     * created.
     *
     * <p>
     * This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of
     * <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for
     * <code>LinkedHashMap</code>.
     * </p>
     *
     * @param eldest
     *            the <code>Entry</code> in question; this implementation doesn't care what it is, since the
     *            implementation is only dependent on the size of the cache
     * @return <tt>true</tt> if the oldest
     * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
     */
    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return super.size() > maxEntries;
    }
}

Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));
Hank Gay
fuente
15
Sin embargo, me gustaría usar la encapsulación aquí en lugar de la herencia. Esto es algo que aprendí de Effective Java.
Kapil D
10
@KapilD Ha pasado un tiempo, pero estoy casi seguro de que los JavaDoc LinkedHashMaprespaldan explícitamente este método para crear una implementación de LRU.
Hank Gay
77
LinkedHashMap de Java @HankGay (con el tercer parámetro = verdadero) no es un caché LRU. Esto se debe a que volver a colocar una entrada no afecta el orden de las entradas (un caché LRU real colocará la última entrada insertada en la parte posterior del orden de iteración, independientemente de si esa entrada existe inicialmente en el caché)
Pacerier
2
@Pacerier No veo este comportamiento en absoluto. Con el mapa habilitado para AccessOrder, todas las acciones hacen una entrada como la más recientemente utilizada (la más reciente): inserción inicial, actualización de valor y recuperación de valor. ¿Me estoy perdiendo de algo?
Esailija
3
@Pacerier "volver a poner una entrada no afecta el orden de las entradas", esto es incorrecto. Si observa la implementación de LinkedHashMap, para el método "put", hereda la implementación de HashMap. Y el Javadoc de HashMap dice "Si el mapa contenía previamente una asignación para la clave, se reemplaza el valor anterior". Y si revisa su código fuente, al reemplazar el valor anterior, llamará al método recordAccess, y en el método recordAccess de LinkedHashMap, se verá así: if (lm.accessOrder) {lm.modCount ++; eliminar(); addBefore (lm.header);}
nybon
18

Si volviera a hacer esto desde cero hoy, usaría Guava's CacheBuilder.

Hank Gay
fuente
10

Esta es la segunda ronda.

La primera ronda fue lo que se me ocurrió, luego releí los comentarios con el dominio un poco más arraigado en mi cabeza.

Así que aquí está la versión más simple con una prueba unitaria que muestra que funciona según algunas otras versiones.

Primero la versión no concurrente:

import java.util.LinkedHashMap;
import java.util.Map;

public class LruSimpleCache<K, V> implements LruCache <K, V>{

    Map<K, V> map = new LinkedHashMap (  );


    public LruSimpleCache (final int limit) {
           map = new LinkedHashMap <K, V> (16, 0.75f, true) {
               @Override
               protected boolean removeEldestEntry(final Map.Entry<K, V> 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 verdadera bandera rastreará el acceso de gets y put. Ver JavaDocs. RemoveEdelstEntry sin el indicador verdadero para el constructor simplemente implementaría un caché FIFO (vea las notas a continuación en FIFO y removeEldestEntry).

Aquí está la prueba que demuestra que funciona como un caché LRU:

public class LruSimpleTest {

    @Test
    public void test () {
        LruCache <Integer, Integer> 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 ();

    }

Ahora para la versión concurrente ...

paquete 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<K, V> implements LruCache<K, V> {

    final CacheMap<K, V>[] cacheRegions;


    private static class CacheMap<K, V> extends LinkedHashMap<K, V> {
        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<K, V> 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<K, V> 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<K, V> cache : cacheRegions ) {
            size += cache.size ();
        }
        return size;
    }

    public String toString () {

        StringBuilder builder = new StringBuilder ();
        for ( CacheMap<K, V> cache : cacheRegions ) {
            builder.append ( cache.toString () ).append ( '\n' );
        }

        return builder.toString ();
    }


}

Puedes ver por qué cubro primero la versión no concurrente. Lo anterior intenta crear algunas franjas para reducir la contención de bloqueo. Entonces usamos la clave y luego busca esa clave para encontrar el caché real. Esto hace que el tamaño límite sea más una sugerencia / conjetura aproximada dentro de una buena cantidad de error, dependiendo de qué tan bien esté el algoritmo hash de claves.

Aquí está la prueba para mostrar que la versión concurrente probablemente funciona. :) (Prueba bajo fuego sería la forma real).

public class SimpleConcurrentLRUCache {


    @Test
    public void test () {
        LruCache <Integer, Integer> 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 <Integer, Integer> 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 ();



    }

}

Esta es la última publicación. La primera publicación que eliminé, ya que era un LFU, no un caché de LRU.

Pensé en darle otra oportunidad. Estaba tratando de encontrar la versión más simple de un caché LRU usando el JDK estándar sin demasiada implementación.

Esto es lo que se me ocurrió. Mi primer intento fue un poco desastroso cuando implementé un LFU en lugar de un LRU, y luego agregué FIFO y el soporte de LRU ... y luego me di cuenta de que se estaba convirtiendo en un monstruo. Luego comencé a hablar con mi amigo John, que apenas estaba interesado, y luego le describí a fondo cómo implementé un LFU, LRU y FIFO y cómo podía cambiarlo con un simple argumento ENUM, y luego me di cuenta de que todo lo que realmente quería fue un simple LRU. Así que ignóreme la publicación anterior y avíseme si desea ver un caché LRU / LFU / FIFO que se puede cambiar a través de una enumeración ... ¿no? Ok .. aquí va.

La LRU más simple posible usando solo el JDK. Implementé tanto una versión concurrente como una versión no concurrente.

Creé una interfaz común (es minimalismo, por lo que probablemente falten algunas características que le gustaría, pero funciona para mis casos de uso, pero si desea ver la función XYZ, hágamelo saber ... vivo para escribir código). .

public interface LruCache<KEY, VALUE> {
    void put ( KEY key, VALUE value );

    VALUE get ( KEY key );

    VALUE getSilent ( KEY key );

    void remove ( KEY key );

    int size ();
}

Te preguntarás qué es getSilent . Lo uso para probar. getSilent no cambia la puntuación LRU de un elemento.

Primero el no concurrente ...

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LruCacheNormal<KEY, VALUE> implements LruCache<KEY,VALUE> {

    Map<KEY, VALUE> map = new HashMap<> ();
    Deque<KEY> 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 ();
    }
}

El queue.removeFirstOccurrence es una operación potencialmente costoso si usted tiene un gran caché. Se podría tomar LinkedList como ejemplo y agregar un mapa hash de búsqueda inversa de elemento a nodo para hacer que las operaciones de eliminación sean MÁS RÁPIDAS y más consistentes. También comencé, pero luego me di cuenta de que no lo necesitaba. Pero tal vez...

Cuando se llama a put , la clave se agrega a la cola. Cuando se llama a get , la clave se elimina y se vuelve a agregar a la parte superior de la cola.

Si su caché es pequeña y la construcción de un artículo es costosa, entonces esta debería ser una buena caché. Si su caché es realmente grande, entonces la búsqueda lineal podría ser un cuello de botella, especialmente si no tiene áreas calientes de caché. Cuanto más intensos sean los puntos calientes, más rápida será la búsqueda lineal, ya que los elementos calientes siempre están en la parte superior de la búsqueda lineal. De todos modos ... lo que se necesita para que esto vaya más rápido es escribir otra LinkedList que tenga una operación de eliminación que tenga un elemento inverso a la búsqueda de nodo para eliminar, luego eliminar sería tan rápido como eliminar una clave de un mapa hash.

Si tiene un caché de menos de 1,000 elementos, esto debería funcionar bien.

Aquí hay una prueba simple para mostrar sus operaciones en acción.

public class LruCacheTest {

    @Test
    public void test () {
        LruCache<Integer, Integer> 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 ();

    }
}

El último caché de LRU tenía un solo subproceso, y no lo envuelva en nada sincronizado ...

Aquí hay una puñalada en una versión concurrente.

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<KEY, VALUE> implements LruCache<KEY,VALUE> {

    private final ReentrantLock lock = new ReentrantLock ();


    private final Map<KEY, VALUE> map = new ConcurrentHashMap<> ();
    private final Deque<KEY> 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 ();
    }
}

Las principales diferencias son el uso de ConcurrentHashMap en lugar de HashMap y el uso de Lock (podría haber salido con sincronizado, pero ...).

No lo he probado bajo fuego, pero parece un simple caché LRU que podría funcionar en el 80% de los casos de uso en los que necesita un mapa LRU simple.

Agradezco sus comentarios, excepto por qué no utiliza la biblioteca a, b o c. La razón por la que no siempre uso una biblioteca es porque no siempre quiero que cada archivo war tenga 80 MB, y escribo bibliotecas, por lo que tiendo a hacer que las bibliotecas se puedan conectar con una solución lo suficientemente buena y alguien pueda conectar -en otro proveedor de caché si lo desean. :) Nunca sé cuándo alguien podría necesitar guayaba o ehcache u otra cosa que no quiero incluir, pero si hago que el almacenamiento en caché sea conectable, tampoco los excluiré.

La reducción de dependencias tiene su propia recompensa. Me encanta recibir comentarios sobre cómo hacer esto aún más simple o más rápido o ambos.

Además, si alguien sabe de un listo para ir ...

Ok ... sé lo que estás pensando ... ¿Por qué no solo usa la entrada removeEldest de LinkedHashMap, y bueno debería pero ... pero ... pero ... Eso sería un FIFO no un LRU y estábamos tratando de implementar una LRU.

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };

Esta prueba falla para el código anterior ...

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

Así que aquí hay un caché FIFO rápido y sucio usando removeEldestEntry.

import java.util.*;

public class FifoCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    final int limit;

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> 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 ();
    }
}

FIFOs son rápidos. No busques alrededor. Podrías hacer frente a un FIFO frente a una LRU y eso manejaría muy bien la mayoría de las entradas activas. Una LRU mejor necesitará ese elemento inverso a la función Nodo.

De todos modos ... ahora que escribí un código, déjame revisar las otras respuestas y ver lo que me perdí ... la primera vez que las escaneé.

RickHigh
fuente
9

LinkedHashMapes O (1), pero requiere sincronización. No es necesario reinventar la rueda allí.

2 opciones para aumentar la concurrencia:

1. Crear múltiples LinkedHashMap, y el hash en ellos: ejemplo: LinkedHashMap[4], index 0, 1, 2, 3. En la tecla do key%4 (u binary ORon [key, 3]) para elegir qué mapa hacer un put / get / remove.

2. Podrías hacer un 'casi' LRU extendiéndote ConcurrentHashMapy teniendo un mapa hash vinculado como una estructura en cada una de las regiones dentro de él. El bloqueo se produciría de forma más granular que un LinkedHashMapsincronizado. En uno puto putIfAbsentsolo se necesita un bloqueo en la cabeza y la cola de la lista (por región). Al eliminar u obtener, toda la región debe estar bloqueada. Tengo curiosidad por saber si las listas enlazadas de Atomic de algún tipo podrían ayudar aquí, probablemente para el encabezado de la lista. Quizás por más.

La estructura no mantendría el orden total, sino solo el orden por región. Siempre que el número de entradas sea mucho mayor que el número de regiones, esto es lo suficientemente bueno para la mayoría de las memorias caché. Cada región tendrá que tener su propio recuento de entradas, esto se utilizaría en lugar del recuento global para el desencadenante de desalojo. El número predeterminado de regiones en a ConcurrentHashMapes 16, que es suficiente para la mayoría de los servidores de hoy.

  1. sería más fácil de escribir y más rápido con una concurrencia moderada.

  2. sería más difícil de escribir pero escala mucho mejor con una concurrencia muy alta. Sería más lento para el acceso normal (al igual que ConcurrentHashMapes más lento que HashMapdonde no hay concurrencia)

jiaweizhang
fuente
8

Hay dos implementaciones de código abierto.

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

Hay un proyecto de código abierto para un ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/

Ron
fuente
2
La solución de Solr no es en realidad LRU, pero ConcurrentLinkedHashMapes interesante. Afirma haber sido rodado MapMakerdesde Guava, pero no lo vi en los documentos. ¿Alguna idea de lo que está pasando con ese esfuerzo?
Hank Gay
3
Se integró una versión simplificada, pero las pruebas no se han completado, por lo que aún no es pública. Tuve muchos problemas para hacer una integración más profunda, pero espero terminarlo ya que hay algunas buenas propiedades algorítmicas. La capacidad de escuchar un desalojo (capacidad, caducidad, GC) se agregó y se basa en el enfoque de CLHM (cola de escucha). También me gustaría contribuir con la idea de "valores ponderados", ya que es útil al almacenar en caché las colecciones. Desafortunadamente, debido a otros compromisos, me he visto demasiado abrumado para dedicar el tiempo que se merece Guava (y eso se lo prometí a Kevin / Charles).
Ben Manes
3
Actualización: La integración se completó y pública en Guava r08. Esto a través de la configuración #maximumSize ().
Ben Manes
7

Consideraría usar java.util.concurrent.PriorityBlockingQueue , con prioridad determinada por un contador "numberOfUses" en cada elemento. Sería muy, muy cuidadoso para obtener toda mi sincronización correcta, ya que el contador "numberOfUses" implica que el elemento no puede ser inmutable.

El objeto del elemento sería un contenedor para los objetos en el caché:

class CacheElement {
    private final Object obj;
    private int numberOfUsers = 0;

    CacheElement(Object obj) {
        this.obj = obj;
    }

    ... etc.
}
Steve McLeod
fuente
¿no quieres decir que debe ser inmutable?
shsteimer
2
tenga en cuenta que si intenta hacer la versión de prioridad de bloqueo de bloqueo mencionada por steve mcleod, debe hacer que el elemento sea inmutable, ya que modificar el elemento mientras está en la cola no tendrá ningún efecto, deberá eliminar el elemento y volver a agregarlo para poder volver a priorizarlo.
James
James a continuación señala un error que cometí. Lo cual ofrezco como evidencia de cuán difícil es sangrar escribir cachés confiables y resistentes.
Steve McLeod
6

Espero que esto ayude .

import java.util.*;
public class Lru {

public static <K,V> Map<K,V> lruCache(final int maxSize) {
    return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {

        private static final long serialVersionUID = -3588047435434569014L;

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    };
 }
 public static void main(String[] args ) {
    Map<Object, Object> lru = Lru.lruCache(2);      
    lru.put("1", "1");
    lru.put("2", "2");
    lru.put("3", "3");
    System.out.println(lru);
}
}
murasing
fuente
1
Buen ejemplo! ¿Podría comentar por qué necesita establecer la capacidad maxSize * 4/3?
Akvel
1
@Akvel se llama capacidad inicial, puede ser cualquier valor [entero] mientras que 0.75f ​​es el factor de carga predeterminado, espero que este enlace ayude: ashishsharma.me/2011/09/custom-lru-cache-java.html
murasing
5

La caché de LRU se puede implementar usando un ConcurrentLinkedQueue y un ConcurrentHashMap que también se puede usar en un escenario de subprocesos múltiples. La cabeza de la cola es ese elemento que ha estado en la cola por más tiempo. La cola de la cola es ese elemento que ha estado en la cola el menor tiempo. Cuando existe un elemento en el Mapa, podemos eliminarlo de LinkedQueue e insertarlo en la cola.

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

public class LRUCache<K,V> {
  private ConcurrentHashMap<K,V> map;
  private ConcurrentLinkedQueue<K> queue;
  private final int size; 

  public LRUCache(int size) {
    this.size = size;
    map = new ConcurrentHashMap<K,V>(size);
    queue = new ConcurrentLinkedQueue<K>();
  }

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

}
sanjanab
fuente
Esto no es seguro. Por ejemplo, puede superar fácilmente el tamaño máximo de LRU llamando simultáneamente put.
dpeacock
Por favor corríjalo. En primer lugar, no se compila en la línea map.containsKey (key). En segundo lugar, en get () debe verificar si realmente se eliminó la clave; de ​​lo contrario, el mapa y la cola no están sincronizados y "queue.size ()> = size" siempre se cumple. Publicaré mi versión con esta solución ya que me gustó su idea de usar estas dos colecciones.
Aleksander Lech
3

Aquí está mi implementación para LRU. He usado PriorityQueue, que básicamente funciona como FIFO y no es seguro. Comparador usado basado en la creación del tiempo de página y basado en la realización del pedido de las páginas por el tiempo usado menos recientemente.

Páginas para consideración: 2, 1, 0, 2, 8, 2, 4

La página agregada al caché es: 2 La
página agregada al caché es: 1 La
página agregada al caché es: 0 La
página: 2 ya existe en el caché. Último tiempo de acceso actualizado
Fallo de página, PÁGINA: 1, Reemplazado con PÁGINA: 8 La
página agregada en la memoria caché es: 8
Página: 2 ya existe en la memoria caché. Último tiempo de acceso actualizado
Fallo de página, PÁGINA: 0, Reemplazado con PÁGINA: 4 La
página agregada en la caché es: 4

SALIDA

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

Ingresa el código aquí

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;


public class LRUForCache {
    private PriorityQueue<LRUPage> priorityQueue = new PriorityQueue<LRUPage>(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<LRUPage> 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<LRUPage> 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<LRUPage>{

    @Override
    public int compare(LRUPage o1, LRUPage o2) {
        if(o1.getPageCreationTime() > o2.getPageCreationTime()){
            return 1;
        }
        if(o1.getPageCreationTime() < o2.getPageCreationTime()){
            return -1;
        }
        return 0;
    }
}
Deepak Singhvi
fuente
2

Aquí está mi implementación probada de caché LRU simultánea de mejor rendimiento sin ningún bloque sincronizado:

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

/**
 * @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);
}

}

Zoltan Boda
fuente
1
@zoltan boda ... no has manejado una situación ... ¿y si el mismo objeto se usa varias veces? en este caso no deberíamos agregar múltiples entradas para el mismo objeto ... en su lugar, su clave debería ser
55
Advertencia: este no es un caché LRU. En un caché LRU, descarta los elementos a los que se accedió menos recientemente. Éste tira los artículos escritos menos recientemente. También es un escaneo lineal para realizar la operación queue.remove (key).
Dave L.
Además, ConcurrentLinkedQueue # size () no es una operación de tiempo constante.
Nates
3
Su método put no parece seguro: tiene algunas declaraciones de verificación y acción que se romperán con múltiples hilos.
Assylias
2

Esta es la caché LRU que uso, que encapsula un LinkedHashMap y maneja la concurrencia con un simple bloqueo de sincronización que protege los puntos jugosos. "Toca" los elementos a medida que se usan para que se conviertan nuevamente en el elemento "más fresco", de modo que en realidad es LRU. También tuve el requisito de que mis elementos tuvieran una vida útil mínima, lo que también se puede considerar como el "tiempo de inactividad máximo" permitido, entonces está listo para ser desalojado.

Sin embargo, estoy de acuerdo con la conclusión de Hank y la respuesta aceptada: si comenzara esto de nuevo hoy, verificaría Guava CacheBuilder.

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;


public class MaxIdleLRUCache<KK, VV> {

    final static private int IDEAL_MAX_CACHE_ENTRIES = 128;

    public interface DeadElementCallback<KK, VV> {
        public void notify(KK key, VV element);
    }

    private Object lock = new Object();
    private long minAge;
    private HashMap<KK, Item<VV>> 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<KK, VV> callback) {
        this.minAge = minAgeMilliseconds;
        this.cache = new LinkedHashMap<KK, Item<VV>>(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<KK, Item<VV>> 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<VV>(value));
        }
    }

    public VV get(KK key) {
        synchronized ( lock ) {
//          System.out.println("get->"+key);
            Item<VV> item = getItem(key);
            return item == null ? null : item.payload;
        }
    }

    public VV remove(String key) {
        synchronized ( lock ) {
//          System.out.println("remove->"+key);
            Item<VV> item =  cache.remove(key);
            if ( item != null ) {
                return item.payload;
            } else {
                return null;
            }
        }
    }

    public int size() {
        synchronized ( lock ) {
            return cache.size();
        }
    }

    private Item<VV> getItem(KK key) {
        Item<VV> 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<T> {
        long birth;
        T payload;

        Item(T payload) {
            this.birth = System.currentTimeMillis();
            this.payload = payload;
        }

        public void touch() {
            this.birth = System.currentTimeMillis();
        }
    }

}
broc.seib
fuente
2

Bueno, para un caché, generalmente buscará algún dato a través de un objeto proxy (una URL, cadena ...), por lo que en cuanto a la interfaz, querrá un mapa. pero para expulsar las cosas quieres una cola como estructura. Internamente, mantendría dos estructuras de datos, una Cola de prioridad y un HashMap. Heres una implementación que debería ser capaz de hacer todo en tiempo O (1).

Aquí hay una clase que preparé bastante rápido:

import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V>
{
    int maxSize;
    int currentSize = 0;

    Map<K, ValueHolder<K, V>> map;
    LinkedList<K> queue;

    public LRUCache(int maxSize)
    {
        this.maxSize = maxSize;
        map = new HashMap<K, ValueHolder<K, V>>();
        queue = new LinkedList<K>();
    }

    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<K> ln = queue.add(key);
        ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln);
        map.put(key, rv);       
        currentSize++;
    }

    public V get(K key)
    {
        ValueHolder<K, V> 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<K>
{
    ListNode<K> prev;
    ListNode<K> next;
    K value;
    public ListNode(K v)
    {
        value = v;
        prev = null;
        next = null;
    }
}

class ValueHolder<K,V>
{
    V value;
    ListNode<K> queueLocation;
    public ValueHolder(V value, ListNode<K> ql)
    {
        this.value = value;
        this.queueLocation = ql;
    }
}

class LinkedList<K>
{
    ListNode<K> head = null;
    ListNode<K> tail = null;

    public ListNode<K> add(K v)
    {
        if(head == null)
        {
            assert(tail == null);
            head = tail = new ListNode<K>(v);
        }
        else
        {
            tail.next = new ListNode<K>(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<K> ln)
    {
        ListNode<K> prev = ln.prev;
        ListNode<K> next = ln.next;
        if(prev == null)
        {
            head = next;
        }
        else
        {
            prev.next = next;
        }
        if(next == null)
        {
            tail = prev;
        }
        else
        {
            next.prev = prev;
        }       
    }
}

Así es como funciona. Las claves se almacenan en una lista vinculada con las claves más antiguas al principio de la lista (las claves nuevas van al reverso), de modo que cuando necesite 'expulsar' algo, simplemente salga del frente de la cola y luego use la clave para eliminar el valor del mapa. Cuando se hace referencia a un elemento, toma el ValueHolder del mapa y luego usa la variable de ubicación para quitar la clave de su ubicación actual en la cola y luego la coloca en la parte posterior de la cola (ahora es la más recientemente utilizada). Agregar cosas es más o menos lo mismo.

Estoy seguro de que hay un montón de errores aquí y no he implementado ninguna sincronización. pero esta clase proporcionará O (1) agregando a la caché, O (1) eliminación de elementos antiguos y O (1) recuperación de elementos de la caché. Incluso una sincronización trivial (solo sincronice todos los métodos públicos) aún tendría poca contención de bloqueo debido al tiempo de ejecución. Si alguien tiene algún truco inteligente de sincronización, estaría muy interesado. Además, estoy seguro de que hay algunas optimizaciones adicionales que podría implementar utilizando la variable maxsize con respecto al mapa.

luke
fuente
Gracias por el nivel de detalle, pero ¿dónde proporciona esto una victoria sobre la implementación LinkedHashMap+ Collections.synchronizedMap()?
Hank Gay el
Rendimiento, no estoy seguro, pero no creo que LinkedHashMap tenga inserción O (1) (probablemente sea O (log (n))), en realidad podría agregar algunos métodos para completar la interfaz del mapa en mi implementación y luego use Collections.synchronizedMap para agregar concurrencia.
luke
En la clase LinkedList anterior en el método add hay un código en el bloque else, es decir, if (tail.prev == null) {tail.prev = head; head.next = tail; } ¿Cuándo se ejecutará este código? Ejecuté algunas ejecuciones en seco y creo que esto nunca se ejecutará y debería eliminarse.
Dipesh el
1

Echa un vistazo a ConcurrentSkipListMap . Debería darle tiempo de registro (n) para probar y eliminar un elemento si ya está contenido en el caché, y tiempo constante para volver a agregarlo.

Solo necesitará un contador, etc. y un elemento de envoltura para forzar el pedido de la orden LRU y asegurarse de que las cosas recientes se descarten cuando el caché esté lleno.

madlep
fuente
¿ ConcurrentSkipListMapProporcionaría algún beneficio de facilidad de implementación ConcurrentHashMap, o es simplemente un caso de evitar casos patológicos?
Hank Gay
Simplificaría las cosas, ya que ConcurrentSkipListMap ordena elementos, lo que le permitiría administrar en qué orden se usaron las cosas. ConcurrentHashMap no hace esto, por lo que básicamente tendría que repetir todo el contenido de la memoria caché para actualizar los últimos elementos de un elemento contador usado 'o lo que sea
madlep
Entonces, con la ConcurrentSkipListMapimplementación, ¿crearía una nueva implementación de la Mapinterfaz que delegue ConcurrentSkipListMapy realice algún tipo de ajuste para que los tipos de claves arbitrarias se envuelvan en un tipo que se ordene fácilmente en función del último acceso?
Hank Gay el
1

Aquí está mi breve implementación, ¡critíquela o mejore!

package util.collection;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Limited size concurrent cache map implementation.<br/>
 * LRU: Least Recently Used.<br/>
 * 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<Key, Value> {

private final int maxSize;
private int currentSize = 0;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

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);
}
}
Zoltan Boda
fuente
1
Esto no es caché LRU, solo es caché FIFO.
lslab
1

Aquí está mi propia implementación de este problema

simplelrucache proporciona almacenamiento en caché LRU seguro, muy simple y no distribuido con soporte TTL. Proporciona dos implementaciones:

  • Concurrente basado en ConcurrentLinkedHashMap
  • Sincronizado basado en LinkedHashMap

Puede encontrarlo aquí: http://code.google.com/p/simplelrucache/

Daimon
fuente
1

La mejor manera de lograrlo es usar un LinkedHashMap que mantenga el orden de inserción de los elementos. El siguiente es un código de muestra:

public class Solution {

Map<Integer,Integer> cache;
int capacity;
public Solution(int capacity) {
    this.cache = new LinkedHashMap<Integer,Integer>(capacity); 
    this.capacity = capacity;

}

// This function returns false if key is not 
// present in cache. Else it moves the key to 
// front by first removing it and then adding 
// it, and returns true. 

public int get(int key) {
if (!cache.containsKey(key)) 
        return -1; 
    int value = cache.get(key);
    cache.remove(key); 
    cache.put(key,value); 
    return cache.get(key); 

}

public void set(int key, int value) {

    // If already present, then  
    // remove it first we are going to add later 
       if(cache.containsKey(key)){
        cache.remove(key);
    }
     // If cache size is full, remove the least 
    // recently used. 
    else if (cache.size() == capacity) { 
        Iterator<Integer> iterator = cache.keySet().iterator();
        cache.remove(iterator.next()); 
    }
        cache.put(key,value);
}

}

Dhirendra Gautam
fuente
0

Estoy buscando un mejor caché LRU usando código Java. ¿Es posible que comparta su código de caché Java LRU usando LinkedHashMapy Collections#synchronizedMap? Actualmente estoy usando LRUMap implements Mapy el código funciona bien, pero estoy haciendo ArrayIndexOutofBoundExceptionpruebas de carga con 500 usuarios en el siguiente método. El método mueve el objeto reciente al frente de la cola.

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)y el put(Object key, Object value)método llama al moveToFrontmétodo anterior .

Raj Pandian
fuente
0

Quería agregar un comentario a la respuesta dada por Hank, pero de alguna manera no puedo hacerlo, trátelo como un comentario

LinkedHashMap también mantiene el orden de acceso en función del parámetro pasado en su constructor. Mantiene una lista doblemente alineada para mantener el orden (Ver LinkedHashMap.Entry)

@Pacerier es correcto que LinkedHashMap mantenga el mismo orden durante la iteración si el elemento se agrega nuevamente, pero eso es solo en el caso del modo de orden de inserción.

Esto es lo que encontré en los documentos de Java del objeto LinkedHashMap.Entry

    /**
     * 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<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }

Este método se encarga de mover el elemento al que se accedió recientemente al final de la lista. Así que, en general, LinkedHashMap es la mejor estructura de datos para implementar LRUCache.

Abhishek Gayakwad
fuente
0

Otro pensamiento e incluso una implementación simple usando la colección de Java LinkedHashMap.

LinkedHashMap proporcionó el método removeEldestEntry y que se puede anular de la manera mencionada en el ejemplo. Por defecto, la implementación de esta estructura de colección es falsa. Si su verdadero y tamaño de esta estructura supera la capacidad inicial, se eliminarán los elementos más antiguos o más antiguos.

Podemos tener un pageno y el contenido de la página en mi caso pageno es entero y el contenido de la página he mantenido la cadena de valores del número de página.

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<Integer,String> lruCache = new              
                 LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) {

           private static final long serialVersionUID = 1L;

           protected boolean removeEldestEntry(Map.Entry<Integer,String>                           

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

     }

}

El resultado de la ejecución del código anterior es el siguiente:

 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 
Deepak Singhvi
fuente
Eso es un FIFO. Él pidió una LRU.
RickHigh
No pasa esta prueba ... cache.get (2); caché.get (3); cache.put (6, 6); cache.put (7, 7); ok | = cache.size () == 4 || die ("tamaño" + cache.size ()); ok | = cache.getSilent (2) == 2 || morir (); ok | = cache.getSilent (3) == 3 || morir (); ok | = cache.getSilent (4) == nulo || morir (); ok | = cache.getSilent (5) == nulo || morir ();
RickHigh
0

Siguiendo el concepto @sanjanab (pero después de las correcciones), hice mi versión de LRUCache proporcionando también al Consumidor que permite hacer algo con los elementos eliminados si es necesario.

public class LRUCache<K, V> {

    private ConcurrentHashMap<K, V> map;
    private final Consumer<V> onRemove;
    private ConcurrentLinkedQueue<K> queue;
    private final int size;

    public LRUCache(int size, Consumer<V> onRemove) {
        this.size = size;
        this.onRemove = onRemove;
        this.map = new ConcurrentHashMap<>(size);
        this.queue = new ConcurrentLinkedQueue<>();
    }

    public V get(K key) {
        //Recently accessed, hence move it to the tail
        if (queue.remove(key)) {
            queue.add(key);
            return map.get(key);
        }
        return null;
    }

    public void put(K key, V value) {
        //ConcurrentHashMap doesn't allow null key or values
        if (key == null || value == null) throw new IllegalArgumentException("key and value cannot be null!");

        V existing = map.get(key);
        if (existing != null) {
            queue.remove(key);
            onRemove.accept(existing);
        }

        if (map.size() >= size) {
            K lruKey = queue.poll();
            if (lruKey != null) {
                V removed = map.remove(lruKey);
                onRemove.accept(removed);
            }
        }
        queue.add(key);
        map.put(key, value);
    }
}
Aleksander Lech
fuente