Wie würden Sie einen LRU-Cache in Java implementieren?

Bitte sagen Sie nicht EHCache oder OSCache usw. Nehmen Sie für die Zwecke dieser Frage an, dass ich meine eigene nur mit dem SDK implementieren möchte (Learning by Doing). Welche Datenstrukturen würden Sie verwenden, da der Cache in einer Multithread-Umgebung verwendet wird? Ich habe bereits eine mit LinkedHashMap und Collections # synchronizedMap implementiert , bin aber gespannt, ob eine der neuen gleichzeitigen Sammlungen bessere Kandidaten wäre.

UPDATE: Ich habe gerade Yegges neueste Version gelesen, als ich dieses Nugget gefunden habe:

Wenn Sie einen zeitlich konstanten Zugriff benötigen und die Einfügereihenfolge beibehalten möchten, können Sie nichts Besseres tun als eine LinkedHashMap, eine wirklich wunderbare Datenstruktur. Der einzige Weg, wie es möglicherweise wundervoller sein könnte, wäre, wenn es eine gleichzeitige Version gäbe. Aber leider.

Ich habe fast genau das Gleiche gedacht, bevor ich mich für die oben erwähnte LinkedHashMap+ Collections#synchronizedMapImplementierung entschieden habe. Gut zu wissen, dass ich nicht einfach etwas übersehen hatte.

Basierend auf den bisherigen Antworten scheint es meine beste Wahl für eine hochkonkurrierende LRU zu sein, ConcurrentHashMap mit der gleichen Logik zu erweitern, die auch LinkedHashMapverwendet wird.

Ich mag viele dieser Vorschläge, aber ich denke, ich bleibe vorerst bei LinkedHashMap+ Collections.synchronizedMap. Wenn ich dies in Zukunft noch einmal besuche, werde ich wahrscheinlich daran arbeiten, auf ConcurrentHashMapdie gleiche Weise zu LinkedHashMaperweitern HashMap.

AKTUALISIEREN:

Auf Anfrage hier der Kern meiner aktuellen Implementierung.

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

Wenn ich das heute noch einmal von Grund auf machen würde, würde ich Guavas verwenden CacheBuilder.

Dies ist die zweite Runde.

Die erste Runde war das, was ich mir ausgedacht habe, dann habe ich die Kommentare mit der Domain noch einmal etwas tiefer in meinem Kopf verwurzelt gelesen.

Hier ist also die einfachste Version mit einem Komponententest, der zeigt, dass sie auf der Grundlage einiger anderer Versionen funktioniert.

Zuerst die nicht gleichzeitige 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 ();
    }


}

Das True-Flag verfolgt den Zugriff auf Gets und Puts. Siehe JavaDocs. Der removeEdelstEntry ohne das true-Flag für den Konstruktor würde lediglich einen FIFO-Cache implementieren (siehe Hinweise unten zu FIFO und removeEldestEntry).

Hier ist der Test, der beweist, dass er als LRU-Cache funktioniert:

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

    }

Nun zur gleichzeitigen Version ...

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


}

Sie können sehen, warum ich zuerst die nicht gleichzeitige Version behandele. Die obigen Versuche versuchen, einige Streifen zu erstellen, um Sperrenkonflikte zu reduzieren. Also hasht es den Schlüssel und sucht dann diesen Hash, um den tatsächlichen Cache zu finden. Dies macht die Grenzgröße eher zu einem Vorschlag / einer groben Vermutung innerhalb einer angemessenen Menge von Fehlern, abhängig davon, wie gut Ihr Schlüssel-Hash-Algorithmus verbreitet ist.

Hier ist der Test, um zu zeigen, dass die gleichzeitige Version wahrscheinlich funktioniert. :) (Test unter Beschuss wäre der echte Weg).

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



    }

}

Dies ist der letzte Beitrag. Der erste Beitrag, den ich gelöscht habe, war eine LFU und kein LRU-Cache.

Ich dachte, ich würde es noch einmal versuchen. Ich habe versucht, die einfachste Version eines LRU-Caches mit dem Standard-JDK ohne zu viel Implementierung zu entwickeln.

Folgendes habe ich mir ausgedacht. Mein erster Versuch war ein bisschen katastrophal, als ich anstelle von und LRU eine LFU implementierte und dann FIFO und LRU-Unterstützung hinzufügte ... und dann merkte ich, dass es ein Monster wurde. Dann fing ich an, mit meinem Kumpel John zu sprechen, der kaum interessiert war, und dann beschrieb ich ausführlich, wie ich eine LFU, LRU und FIFO implementierte und wie man sie mit einem einfachen ENUM-Argument wechseln konnte, und dann wurde mir klar, dass alles, was ich wirklich wollte war eine einfache LRU. Ignorieren Sie also den früheren Beitrag von mir und lassen Sie mich wissen, ob Sie einen LRU / LFU / FIFO-Cache sehen möchten, der über eine Aufzählung umgeschaltet werden kann ... nein? Ok .. hier geht er.

Die einfachste mögliche LRU, die nur das JDK verwendet. Ich habe sowohl eine gleichzeitige als auch eine nicht gleichzeitige Version implementiert.

Ich habe eine gemeinsame Benutzeroberfläche erstellt (es ist ein Minimalismus, dem wahrscheinlich einige Funktionen fehlen, die Sie möchten, aber er funktioniert für meine Anwendungsfälle. Wenn Sie jedoch die Funktion XYZ sehen möchten, lassen Sie es mich wissen ... Ich lebe, um Code zu schreiben.) .

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

Sie fragen sich vielleicht, was getSilent ist. Ich benutze dies zum Testen. getSilent ändert die LRU-Punktzahl eines Elements nicht.

Zuerst die nicht gleichzeitige ....

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

Die queue.removeFirstOccurrence ist eine möglicherweise teure Operation, wenn Sie einen großen Cache haben. Man könnte LinkedList als Beispiel nehmen und eine Reverse-Lookup-Hash-Map von Element zu Knoten hinzufügen, um Entfernungsoperationen VIEL SCHNELLER und konsistenter zu machen. Ich habe auch angefangen, aber dann wurde mir klar, dass ich es nicht brauche. Aber vielleicht...

Wenn put aufgerufen wird, wird der Schlüssel zur Warteschlange hinzugefügt. Wenn get aufgerufen wird, wird der Schlüssel entfernt und oben in der Warteschlange wieder hinzugefügt.

Wenn Ihr Cache klein ist und das Erstellen eines Elements teuer ist, sollte dies ein guter Cache sein. Wenn Ihr Cache wirklich groß ist, kann die lineare Suche ein Flaschenhals sein, insbesondere wenn Sie keine heißen Cache-Bereiche haben. Je intensiver die Hot Spots sind, desto schneller ist die lineare Suche, da Hot Items immer ganz oben in der linearen Suche stehen. Wie auch immer ... Damit dies schneller geht, muss eine weitere LinkedList geschrieben werden, die über eine Entfernungsoperation verfügt, bei der ein umgekehrtes Element zur Knotensuche zum Entfernen verwendet wird. Das Entfernen ist dann ungefähr so ​​schnell wie das Entfernen eines Schlüssels aus einer Hash-Map.

Wenn Sie einen Cache unter 1.000 Elementen haben, sollte dies gut funktionieren.

Hier ist ein einfacher Test, um seine Operationen in Aktion zu zeigen.

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

    }
}

Der letzte LRU-Cache war Single-Threaded, und bitte verpacken Sie ihn nicht in etwas Synchronisiertes.

Hier ist ein Stich in eine gleichzeitige Version.

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

Die Hauptunterschiede sind die Verwendung der ConcurrentHashMap anstelle von HashMap und die Verwendung der Sperre (ich hätte mit synchronisiert davonkommen können, aber ...).

Ich habe es nicht unter Beschuss getestet, aber es scheint ein einfacher LRU-Cache zu sein, der in 80% der Anwendungsfälle funktioniert, in denen Sie eine einfache LRU-Karte benötigen.

Ich freue mich über Feedback, außer warum Sie die Bibliothek a, b oder c nicht verwenden. Der Grund, warum ich nicht immer eine Bibliothek verwende, ist, dass ich nicht immer möchte, dass jede War-Datei 80 MB groß ist, und ich schreibe Bibliotheken, sodass ich die Bibliotheken mit einer ausreichend guten Lösung steckbar mache und jemand einstecken kann -in einem anderen Cache-Anbieter, wenn sie möchten. :) Ich weiß nie, wann jemand Guava oder ehcache oder etwas anderes benötigt, das ich nicht einschließen möchte, aber wenn ich das Caching steckbar mache, werde ich sie auch nicht ausschließen.

Die Reduzierung von Abhängigkeiten hat ihre eigene Belohnung. Ich freue mich über Feedback, wie ich dies noch einfacher oder schneller oder beides machen kann.

Auch wenn jemand von einem Ready to Go weiß ....

Ok .. ich weiß was du denkst ... Warum benutzt er nicht einfach den Eintrag removeEldest von LinkedHashMap und nun sollte ich aber ... aber ... aber ... das wäre ein FIFO, kein LRU und wir waren es versuchen, eine LRU zu implementieren.

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

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

Dieser Test schlägt für den obigen Code fehl ...

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

Hier ist also ein schneller und schmutziger FIFO-Cache mit 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 sind schnell. Keine Suche. Sie könnten ein FIFO vor eine LRU stellen, und das würde die meisten heißen Einträge recht gut handhaben. Eine bessere LRU benötigt dieses Reverse-Element zur Node-Funktion.

Wie auch immer ... jetzt, wo ich Code geschrieben habe, lass mich die anderen Antworten durchgehen und sehen, was ich verpasst habe ... als ich sie das erste Mal gescannt habe.

LinkedHashMapist O (1), erfordert jedoch eine Synchronisation. Dort muss das Rad nicht neu erfunden werden.

2 Optionen zur Erhöhung der Parallelität:

1. Erstellen Sie mehrere LinkedHashMapund hashen Sie sie ein: Beispiel : LinkedHashMap[4], index 0, 1, 2, 3. Wählen Sie auf der Taste do key%4 (oder binary ORon [key, 3]) aus, welche Karte zum Put / Get / Remove verwendet werden soll.

2. Sie können eine "fast" LRU erstellen ConcurrentHashMap, indem Sie eine verknüpfte Hash-Map-ähnliche Struktur in jeder der darin enthaltenen Regionen erstellen. Das Sperren würde granularer erfolgen als das LinkedHashMap, das synchronisiert wird. Bei einem putoder putIfAbsentnur einem Schloss am Kopf und am Ende der Liste wird benötigt (pro Region). Beim Entfernen oder Abrufen muss die gesamte Region gesperrt werden. Ich bin gespannt, ob Atomic-verknüpfte Listen hier helfen könnten - wahrscheinlich auch für den Kopf der Liste. Vielleicht für mehr.

Die Struktur würde nicht die Gesamtreihenfolge beibehalten, sondern nur die Reihenfolge pro Region. Solange die Anzahl der Einträge viel größer ist als die Anzahl der Regionen, ist dies für die meisten Caches ausreichend. Jede Region muss eine eigene Anzahl von Einträgen haben. Diese wird anstelle der globalen Anzahl für den Räumungsauslöser verwendet. Die Standardanzahl von Regionen in a ConcurrentHashMapist 16, was für die meisten Server heutzutage ausreichend ist.

1. wäre einfacher zu schreiben und schneller bei mäßiger Parallelität.

2. Es wäre schwieriger zu schreiben, aber bei sehr hoher Parallelität viel besser zu skalieren. Es wäre langsamer für den normalen Zugriff (genauso wie ConcurrentHashMapes langsamer ist als dort, HashMapwo es keine Parallelität gibt)

Es gibt zwei Open Source-Implementierungen.

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

Es gibt ein Open Source-Projekt für eine ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/

Ich würde in Betracht ziehen, java.util.concurrent.PriorityBlockingQueue zu verwenden , wobei die Priorität durch einen "numberOfUses" -Zähler in jedem Element bestimmt wird. Ich würde sehr, sehr vorsichtig sein , um alle meine Synchronisationen korrekt zu machen, da der Zähler "numberOfUses" impliziert, dass das Element nicht unveränderlich sein kann.

Das Elementobjekt wäre ein Wrapper für die Objekte im Cache:

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

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

    ... etc.
}

Hoffe das hilft .

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

Der LRU-Cache kann mithilfe einer ConcurrentLinkedQueue und einer ConcurrentHashMap implementiert werden, die auch im Multithreading-Szenario verwendet werden können. Der Kopf der Warteschlange ist das Element, das sich am längsten in der Warteschlange befunden hat. Das Ende der Warteschlange ist das Element, das sich in kürzester Zeit in der Warteschlange befunden hat. Wenn ein Element in der Map vorhanden ist, können wir es aus der LinkedQueue entfernen und am Ende einfügen.

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

}

Hier ist meine Implementierung für LRU. Ich habe PriorityQueue verwendet, das im Grunde genommen als FIFO und nicht threadsicher funktioniert. Verwendeter Komparator basierend auf der Erstellung der Seitenzeit und basierend auf der Ausführung der Reihenfolge der Seiten für die zuletzt verwendete Zeit.

Zu berücksichtigende Seiten: 2, 1, 0, 2, 8, 2, 4

In den Cache hinzugefügte Seite ist: 2
In den Cache hinzugefügte Seite ist: 1
In den Cache hinzugefügte Seite ist: 0
Seite: 2 bereits im Cache vorhanden. Zuletzt aktualisierte Zugriffszeit Seitenfehler
, SEITE: 1, ersetzt durch SEITE: 8 Die
in den Cache hinzugefügte Seite ist: 8
Seite: 2 ist bereits im Cache vorhanden. Zuletzt aktualisierte
Zugriffszeit Seitenfehler, SEITE: 0, Ersetzt durch SEITE: 4 Die
in den Cache hinzugefügte Seite ist: 4

AUSGABE

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

Code hier eingeben

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

Hier ist meine getestete leistungsstärkste gleichzeitige LRU-Cache-Implementierung ohne synchronisierten Block:

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

}}

Dies ist der von mir verwendete LRU-Cache, der eine LinkedHashMap kapselt und die Parallelität mit einer einfachen Synchronisierungssperre behandelt, die die saftigen Stellen schützt. Es "berührt" Elemente, wenn sie verwendet werden, so dass sie wieder das "frischeste" Element werden, so dass es tatsächlich LRU ist. Ich hatte auch die Anforderung, dass meine Elemente eine minimale Lebensdauer haben, die Sie auch als "maximal zulässige Leerlaufzeit" betrachten können, dann sind Sie zur Räumung bereit.

Ich stimme jedoch Hanks Schlussfolgerung zu und akzeptiere die Antwort - wenn ich heute wieder damit anfangen würde, würde ich mir Guavas ansehen 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();
        }
    }

}

Nun, für einen Cache suchen Sie im Allgemeinen einige Daten über ein Proxy-Objekt (eine URL, eine Zeichenfolge ...), sodass Sie in Bezug auf die Benutzeroberfläche eine Karte benötigen. Aber um die Dinge rauszuwerfen, möchten Sie eine Warteschlangenstruktur. Intern würde ich zwei Datenstrukturen pflegen, eine Priority-Queue und eine HashMap. Hier ist eine Implementierung, die in der Lage sein sollte, alles in O (1) Zeit zu erledigen.

Hier ist eine Klasse, die ich ziemlich schnell zusammengestellt habe:

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

So funktioniert das. Schlüssel werden in einer verknüpften Liste mit den ältesten Schlüsseln vorne in der Liste gespeichert (neue Schlüssel gehen nach hinten). Wenn Sie also etwas "auswerfen" müssen, legen Sie es einfach von der Vorderseite der Warteschlange ab und verwenden Sie dann den Schlüssel, um Entfernen Sie den Wert aus der Karte. Wenn auf ein Element verwiesen wird, nehmen Sie den ValueHolder aus der Karte und verwenden dann die Variable queuelocation, um den Schlüssel von seiner aktuellen Position in der Warteschlange zu entfernen und ihn dann am Ende der Warteschlange abzulegen (es ist jetzt die zuletzt verwendete). Das Hinzufügen von Dingen ist ziemlich gleich.

Ich bin mir sicher, dass es hier eine Menge Fehler gibt und ich habe keine Synchronisation implementiert. Diese Klasse bietet jedoch O (1) Hinzufügen zum Cache, O (1) Entfernen alter Elemente und O (1) Abrufen von Cache-Elementen. Selbst eine triviale Synchronisation (nur jede öffentliche Methode synchronisieren) hätte aufgrund der Laufzeit immer noch wenig Sperrenkonflikte. Wenn jemand clevere Synchronisationstricks hat, wäre ich sehr interessiert. Ich bin mir auch sicher, dass es einige zusätzliche Optimierungen gibt, die Sie mithilfe der Variablen maxsize in Bezug auf die Karte implementieren können.

Schauen Sie sich ConcurrentSkipListMap an . Es sollte Ihnen log (n) Zeit zum Testen und Entfernen eines Elements geben, wenn es bereits im Cache enthalten ist, und konstante Zeit zum erneuten Hinzufügen.

Sie benötigen lediglich einen Zähler usw. und ein Wrapper-Element, um die Reihenfolge der LRU-Reihenfolge zu erzwingen und sicherzustellen, dass aktuelle Inhalte verworfen werden, wenn der Cache voll ist.

Hier ist meine kurze Implementierung, bitte kritisieren oder verbessern Sie sie!

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

Hier ist meine eigene Implementierung zu diesem Problem

simplelrucache bietet threadsicheres, sehr einfaches, nicht verteiltes LRU-Caching mit TTL-Unterstützung. Es bietet zwei Implementierungen:

• Concurrent basierend auf ConcurrentLinkedHashMap
• Synchronisiert basierend auf LinkedHashMap

Sie finden es hier: http://code.google.com/p/simplelrucache/

Der beste Weg, dies zu erreichen, ist die Verwendung einer LinkedHashMap, die die Einfügereihenfolge der Elemente beibehält. Es folgt ein Beispielcode:

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