Comment implémenter une cache LRU en Java?

j'aime beaucoup ces suggestions, mais pour l'instant je pense que je vais rester avec LinkedHashMap + Collections.synchronizedMap . Si je revisite cela à l'avenir, je vais probablement travailler sur l'extension ConcurrentHashMap de la même manière que LinkedHashMap étend HashMap .

mise à jour:

sur demande, voici l'essentiel de mon implémentation actuelle.

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

ou utilisez cette structure de données Apache Commons:

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/LRUMap.html

deuxième round.

le premier round a été ce que j'ai trouvé puis j'ai relu les commentaires avec le domaine un peu plus ancré dans ma tête.

voici donc la version la plus simple avec un test unitaire qui montre qu'elle fonctionne sur la base de certaines autres versions.

d'Abord le non-cumul version:

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


}

le vrai drapeau tracera l'accès des gets et puts. Voir La Documentation Javadoc. Le removeEdelstEntry sans le drapeau true pour le constructeur implémenterait simplement un cache FIFO (voir les notes ci-dessous sur FIFO et removeeldestry).

voici le test qui prouve qu'il fonctionne comme cache 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 ();

    }

maintenant pour la version concurrente...

package org.aubaine.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 ();
    }


}

vous pouvez voir pourquoi je couvre la version non-concurrente d'abord. Les tentatives ci-dessus pour créer bandes pour réduire la contention de verrouillage. Donc, nous il hachons la clé et puis regarde ce hachage pour trouver le cache réel. Cela rend la taille limite plus d'une suggestion / conjecture grossière à l'intérieur d'un certain montant d'erreur en fonction de la façon dont bien étalé votre algorithme de hachage de clés est.

voici le test pour montrer que la version concurrente fonctionne probablement. :) (Test sous le feu serait le vrai moyen).

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



    }

}

C'est le dernier post.. Le premier post que j'ai supprimé c'était une LFU, pas une cache LRU.

j'ai pensé que j'allais donner une autre chance. J'essayais de trouver la version la plus simple d'un cache LRU en utilisant la norme JDK avec trop d'implémentation.

voilà ce que j'ai trouvé. Ma première tentative a été un peu un désastre car j'ai mis en œuvre une LFU au lieu de et LRU, et puis j'ai ajouté FIFO, et soutien LRU à elle... et puis j'ai réalisé que c'était en train de devenir un monstre. Puis j'ai commencé à parler à mon copain John qui était à peine intéressé, et puis j'ai décrit en détail comment j'ai mis en œuvre un LFU, LRU et FIFO et comment vous pourriez le changer avec un simple enum arg, et puis j'ai réalisé que tout ce que je voulais vraiment était un LRU simple. Donc, ignorez le post précédent de moi, et faites-moi savoir si vous voulez voir un LRU/LFU/FIFO cache qui est commutable via un enum... pas? OK.. ici il y aille.

le LRU le plus simple possible en utilisant juste le JDK. J'ai mis en place à la fois un concurrent et une version la non-concordance version.

j'ai créé une interface commune (c'est Minimalisme si probablement manquer quelques fonctionnalités que vous aimeriez mais cela fonctionne pour mes cas d'utilisation, mais laissez si vous voulez voir la fonctionnalité XYZ me le faire savoir... Je vis pour écrire du code.).

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

vous pouvez vous demander ce que getSilent est. - Je l'utiliser pour le test. getSilent ne change pas le score LRU d'un élément.

d'Abord le non-cumul....

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

Le file d'attente.removeFirstOccurrence est une opération potentiellement coûteuse si vous avez un grand cache. On pourrait prendre LinkedList comme exemple et ajouter une carte de hachage de recherche inversée d'un élément à un noeud pour rendre les opérations de suppression beaucoup plus rapides et plus cohérentes. J'ai commencé aussi, mais j'ai réalisé que je n'en avais pas besoin. Mais... peut-être...

quand mis est appelé, la clé est ajoutée à la file d'attente. Lorsque get est appelé, la clé est retirée et ré-ajoutée au haut de la file d'attente.

si votre cache est petit et que la construction d'un article est chère, alors cela devrait être un bon cache. Si votre cache est vraiment important, la recherche linéaire pourrait être un goulot de bouteille, surtout si vous n'avez pas chaud zones de cache. Le plus intense de la hot spots, les plus la recherche linéaire est rapide, car les éléments chauds sont toujours au sommet de la recherche linéaire. De toute façon... ce qui est nécessaire pour que cela aille plus vite est d'écrire une autre LinkedList qui a une opération de suppression qui a un élément inversé à la recherche de noeud pour supprimer, puis supprimer serait à peu près aussi rapide que supprimer une clé d'une carte de hachage.

si vous avez une cache de moins de 1.000 Articles, cela devrait fonctionner très bien.

voici un test simple pour montrer ses opérations en action.

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

    }
}

la dernière cache LRU était filetée, et s'il vous plaît ne l'enveloppez pas dans un rien synchronisé....

voici un coup de poignard à une version 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 ();
    }
}

les principales différences sont l'utilisation de la Competienthashmap au lieu de HashMap, et l'utilisation de la serrure (j'aurais pu m'en sortir avec synchronisé, mais...).

je ne l'ai pas testé sous le feu, mais il semble comme une cache LRU simple qui pourrait fonctionner dans 80% des cas d'utilisation où vous avez besoin d'une carte LRU simple.

je me félicite de commentaires, à l'exception du pourquoi n'utilisez-vous pas de la bibliothèque a, b, ou c. La raison pour laquelle je n'utilise pas toujours une bibliothèque est que je ne veux pas toujours que chaque fichier war soit 80 Mo, et j'écris des bibliothèques donc j'ai tendance à rendre les libs plug-able avec une bonne solution en place et quelqu'un peut brancher un autre fournisseur de cache s'il le souhaite. :) Je ne sais jamais quand quelqu'un pourrait avoir besoin de Goyave ou ehcache ou quelque chose d'autre que je ne veux pas les inclure, mais si je fais la mise en cache plug-able, Je ne les exclurai pas non plus.

réduction des dépendances a sa propre récompense. J'aime recevoir des commentaires sur la façon de rendre le tout encore plus simple ou plus rapide, ou les deux.

Aussi, si quelqu'un connaît un prêt à aller....

Ok.. Je sais ce que vous pensez... Pourquoi n'utilise-t-il pas simplement l'entrée removeEldest de LinkedHashMap, et bien je devrais mais.... mais.. mais.. Ce serait un FIFO pas un LRU et on essayait de mettre en place un LRU.

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

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

cet essai n'est pas satisfaisant pour le code ci-dessus...

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

voici donc un cache FIFO rapide et sale en utilisant 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 ();
    }
}

les FIFOs sont rapides. Pas de recherche autour de. Vous pouvez présenter un FIFO en face d'un LRU et qui traiterait la plupart des entrées chaudes tout à fait bien. Un meilleur LRU va en avoir besoin. fonction inverse élément à Noeud.

en tout cas... maintenant que j'ai écrit un code, laissez-moi passer en revue les autres réponses et voir ce que j'ai manqué... la première fois que je les ai scannées.

LinkedHashMap est O(1), mais requiert une synchronisation. Pas besoin de réinventer la roue.

2 options pour augmenter la concurrence:

1. Créer plusieurs LinkedHashMap , et hachez dans eux: exemple: LinkedHashMap[4], index 0, 1, 2, 3 . Sur la touche faire key%4 (ou binary OR sur [key, 3] ) pour choisir quelle carte faire un put/get/remove.

2. Vous pourriez faire un "presque" LRU en étendant ConcurrentHashMap , et avoir un lien hachage de la carte comme la structure dans chacune des régions à l'intérieur d'elle. Le verrouillage se produirait de façon plus granulaire qu'un LinkedHashMap synchronisé. Sur un put ou putIfAbsent seulement un verrou sur la tête et la queue de la liste, est nécessaire (par région). Sur un supprimer ou obtenir l'ensemble de la région doit être verrouillé. Je suis curieux de savoir si les listes atomiques liées d'une façon ou d'une autre pourraient aider ici -- probablement pour le chef de la liste. Peut-être pour plus d'.

la structure ne conserverait pas le total l'ordre, mais seulement l'ordre par région. Tant que le nombre d'entrées est beaucoup plus élevé que le nombre de régions, c'est suffisant pour la plupart des caches. Chaque région devra avoir son propre nombre d'entrées, qui sera utilisé plutôt que le nombre global pour le déclencheur d'expulsion. Le nombre par défaut de régions dans un ConcurrentHashMap est de 16, ce qui est suffisant pour la plupart des serveurs aujourd'hui.

1. serait plus facile à écrire et plus rapide sous la concurrence modérée.

2. serait plus difficile à écrire, mais l'échelle beaucoup mieux à très haute concurrence. Il serait plus lent pour l'accès normal (tout comme ConcurrentHashMap est plus lent que HashMap où il n'y a pas de concurrence)

il y a deux implémentations open source.

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

il y a un projet open source pour un concurrent LinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap /

j'envisagerais d'utiliser java.util.simultané.PriorityBlockingQueue , avec priorité déterminée par un compteur" numberOfUses " dans chaque élément. Je serais très, très prudent pour obtenir toute ma synchronisation correcte, comme le compteur "numberOfUses" implique que l'élément ne peut pas être immuable.

L'élément object serait un wrapper pour les objets dans le cache:

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

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

    ... etc.
}

LRU Cache peut être mis en œuvre en utilisant un ConcurrentLinkedQueue et un Concurrententhashmap qui peut être utilisé dans le scénario de multithreading aussi bien. La tête de la file d'attente est l'élément qui a été sur la file d'attente le plus longtemps. La queue de la file d'attente est l'élément qui a été sur la file d'attente le plus court temps. Lorsqu'un élément de la Carte, on peut l'enlever de la LinkedQueue et l'insérer à la queue.

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

}

Espérons que cette aide .

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

Voici mon implémentation pour LRU. J'ai utilisé PriorityQueue, qui fonctionne essentiellement comme FIFO et non threadsafe. Utilisé Comparateur basé sur le temps de la création et sur la base effectue la commande des pages pour le moins récemment utilisé le temps.

Pages à considérer : 2, 1, 0, 2, 8, 2, 4

la Page ajoutée dans le cache est: 2

La Page ajoutée dans le cache est: 1

La Page ajoutée dans le cache est: 0

Page: 2 existe déjà en cache. Date de la dernière consultation mise à jour

Page Fault, PAGE: 1, remplacé par PAGE: 8

La Page ajoutée dans le cache est: 8

Page: 2 existe déjà en cache. Date de la dernière consultation mise à jour

Page Fault, PAGE: 0, remplacé par PAGE: 4

La Page ajoutée dans le cache est : 4

Sortie

LRUCache Pages

-------------

PageName: 8, PageCreationTime: 1365957019974

PageName: 2, PageCreationTime: 1365957020074

Nom De La Page: 4, Page CreationTime: 1365957020174

entrez le code ici

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

Voici mon implémentation de cache LRU concurrente la plus performante sans aucun bloc synchronisé:

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

}

c'est le cache LRU que j'utilise, qui encapsule un LinkedHashMap et gère la concurrence avec une simple serrure synchronisée qui protège les points juteux. Il " touche "les éléments au fur et à mesure qu'ils sont utilisés de sorte qu'ils redeviennent l'élément" le plus frais", de sorte qu'il s'agit en fait de LRU. J'ai aussi eu l'exigence de mes éléments ayant une durée de vie minimale, que vous pouvez également penser comme "temps d'inactivité maximale" autorisé, alors vous êtes en place pour l'expulsion.

cependant, je suis d'accord avec Hank conclusion et réponse acceptée -- si je recommençais aujourd'hui, je consulterais le CacheBuilder de Guava .

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

}

Eh bien pour un cache, vous chercherez généralement un morceau de données via un objet proxy, (une URL, chaîne de caractères....) donc l'interface de sage, vous allez vouloir une carte. mais pour virer les choses, il faut une file d'attente comme une structure. En interne, Je maintiendrais deux structures de données, une file D'attente prioritaire et un HashMap. heres une mise en œuvre qui devrait être capable de tout faire en O(1) fois.

Voici une classe que j'ai montée assez vite:

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

Voici comment cela fonctionne. Les clés sont stockées dans une liste liée avec les plus anciennes clés à l'avant de la liste (les nouvelles clés vont à l'arrière) donc quand vous avez besoin de "éjecter" quelque chose, vous le pop juste à l'avant de la file d'attente et ensuite utiliser la clé pour supprimer la valeur de la carte. Lorsqu'un élément est référencé, vous saisissez L'attribut de valeur de la carte, puis utilisez la variable de mise en file d'attente pour supprimer la clé de son emplacement actuel dans la file d'attente, puis vous la mettez à l'arrière de la file d'attente (sa plus récente utiliser.) Ajouter des choses est à peu près la même chose.

je suis sûr qu'il y a une tonne d'erreurs ici et je n'ai pas implémenté de synchronisation. mais cette classe fournira O(1) ajoutant au cache, O(1) enlevant les anciens éléments, et O (1) récupérant les éléments de cache. Même une simple synchronisation (juste synchroniser chaque méthode publique) serait encore peu de verrouillage en raison du moment de l'exécution. Si quelqu'un a des astuces de synchronisation, je serais très intéressé. Aussi, j'en suis sûr il y a quelques optimisations supplémentaires que vous pouvez implémenter en utilisant la variable maxsize par rapport à la carte.

regarder ConcurrentSkipListMap . Il devrait vous donner le temps log (n) pour tester et enlever un élément s'il est déjà contenu dans le cache, et le temps constant pour le ré-ajouter.

vous avez juste besoin d'un élément compteur etc et wrapper pour forcer la commande de L'ordre LRU et s'assurer que les choses récentes sont jetées lorsque le cache est plein.

voici ma courte mise en œuvre, s'il vous plaît critiquez ou améliorez-la!

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

Voici ma propre mise en œuvre de ce problème

simplelrucache fournit le cache LRU threadsafe, très simple, non distribué avec le support TTL. Il fournit deux implémentations:

• Concurrent basé sur le concurrent LinkedHashMap
• synchronisé basé sur LinkedHashMap

vous pouvez le trouver ici: http://code.google.com/p/simplelrucache /

je cherche un meilleur cache LRU en utilisant du code Java. Est-il possible pour vous de partager votre code cache LRU Java en utilisant LinkedHashMap et Collections#synchronizedMap ? Actuellement j'utilise LRUMap implements Map et le code fonctionne bien, mais je reçois ArrayIndexOutofBoundException sur les essais de charge en utilisant 500 utilisateurs sur la méthode ci-dessous. La méthode déplace l'objet récent à l'avant de la file d'attente.

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) et put(Object key, Object value) les appels de méthode ci-dessus moveToFront la méthode.

voulait ajouter un commentaire à la réponse donnée par Hank, mais certains comment je ne suis pas en mesure de - s'il vous plaît traiter comme commentaire

LinkedHashMap maintient l'ordre d'accès ainsi basé sur le paramètre passé dans son constructeur Il garde la liste doublée pour maintenir l'ordre (voir LinkedHashMap.Entrée)

@Pacerier il est correct que LinkedHashMap garde le même ordre pendant l'itération si l'élément est ajouté de nouveau mais c'est seulement dans le cas du mode d'ordre d'insertion.

c'est ce que j'ai trouvé dans java docs de LinkedHashMap.L'entrée de l'objet

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

cette méthode prend soin de déplacer l'élément récemment accédé à la fin de la liste. Donc, tout dans L'ensemble LinkedHashMap est la meilleure structure de données pour la mise en œuvre D'Irucache.

une autre pensée et même une simple implémentation en utilisant la collection LinkedHashMap de Java.

LinkedHashMap fourni la méthode removeEldestEntry et qui peut être outrepassé de la manière mentionnée dans l'exemple. Par défaut, la mise en œuvre de cette structure de collecte est fausse. Si son vrai et la taille de cette structure va au-delà de la capacité initiale que les éléments les plus anciens ou plus anciens seront enlevés.

nous pouvons avoir un pageno et le contenu de la page dans mon si pageno est entier et pagecontent j'ai gardé la chaîne de valeurs de nombre de page.

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

     }

}

résultat de l'exécution du code ci-dessus est le suivant:

 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 offre une mise en œuvre d'un LRU Cache . Le code est propre et simple.