Wie würden Sie eine LRU-Cache in Java implementieren?
https://stackoverflow.com/questions/221525
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Bitte sagen Sie nicht EHCache oder OSCache usw. Es sei angenommen, für die Zwecke dieser Frage, die ich mag, dass mein eigenes nur mit dem SDK (learning by doing) implementieren. Da der Cache-Speicher in einer Multithread-Umgebung verwendet werden, die Datenstrukturen würden Sie nutzen? Ich habe schon einmal umgesetzt werden mit LinkedHashMap und Sammlungen # synchronizedMap , aber ich bin neugierig, wenn eine der neuen gleichzeitigen Sammlungen würde bessere Kandidaten sein.
UPDATE: Ich war gerade das Lesen durch Yegge neueste wenn ich dieses Nugget gefunden:
Wenn Sie konstant Zeitzugriff benötigen und wollen den Anzeigenauftrag erhalten, kann man nicht besser machen als ein LinkedHashMap, eine wirklich wunderbare Datenstruktur. Der einzige Weg, es vielleicht schöner sein könnte, ist, wenn es eine gleichzeitige Version war. Aber leider.
Ich dachte fast genau die gleiche Sache, bevor ich mit der LinkedHashMap + Collections#synchronizedMap Implementierung ging ich oben erwähnt. Schön zu wissen, hatte ich nicht nur etwas übersehen.
Auf der Grundlage der Antworten so weit, es klingt wie meine beste Wette für eine sehr gleichzeitige LRU zu verlängern wäre ConcurrentHashMap einige der gleichen Logik, die Verwendungen LinkedHashMap.
Lösung 3
Wenn ich das heute wieder von Grund auf zu tun, würde ich Guava der CacheBuilder .
Andere Tipps
Ich mag viele dieser Vorschläge, aber jetzt denke ich, dass ich mit LinkedHashMap + Collections.synchronizedMap hafte. Wenn ich dies in Zukunft tun denken, werde ich wahrscheinlich auf Arbeit ConcurrentHashMap in gleicher Weise erstreckt LinkedHashMap HashMap erstreckt.
UPDATE:
Mit dem Wunsch, hier ist 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));
oder verwenden diese Daten Apache Commons Struktur:
Dies ist rund zwei.
Die erste Runde war, was ich kam mit dann wieder gelesen habe ich die Kommentare mit der Domain ein bisschen mehr tief verwurzelt in meinem Kopf.
Hier ist also die einfachste Version mit einem Unit-Test, der auf einigen anderen Versionen zeigen Arbeiten zugrunde.
Zuerst wird die nicht-konkurrierende 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 ();
}
}
Die wahre Flagge wird den Zugang bekommt und Puts verfolgen. Siehe JavaDocs. Die removeEdelstEntry ohne die wahre Flagge an den Konstruktor würde implementieren nur eine FIFO-Cache (Notizen unten auf FIFO und removeEldestEntry sehen).
Hier ist der Test, dass es funktioniert als LRU-Cache belegt:
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 ();
}
Jetzt für die gleichzeitige Ausführung ...
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 die nicht gleichzeitige Version zuerst abdecken. Die obigen Versuche, einige Streifen zu schaffen Sperrenkonflikte zu reduzieren. So Hashes wir es den Schlüssel und dann schaut nach oben, dass Hash den eigentlichen Cache zu finden. Dies macht die Grenze Größe eher eine Anregung / grobe Schätzung innerhalb einer angemessenen Menge von Fehler je nachdem, wie gut Ihre Schlüssel verteilt Hash-Algorithmus ist.
Hier ist der Test zu zeigen, dass die gleichzeitige Version wahrscheinlich funktioniert. :) (Test unter Feuer würde die reale Art und Weise sein).
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 habe ich gelöscht, da es eine LFU kein LRU-Cache war.
Ich dachte, ich würde dies eine andere gehen geben. Ich habe versucht, versucht, mit der einfachsten Version eines LRU-Cache unter Verwendung des Standard JDK w / o zu viel Umsetzung zu entwickeln.
Hier ist, was ich kam mit. Mein erster Versuch war ein bisschen eine Katastrophe, wie ich einen LFU statt und LRU umgesetzt, und dann habe ich FIFO und LRU Unterstützung es ... und dann wurde mir klar, es ist ein Monster war immer. Dann begann ich zu meinem Kumpel sprechen John, der kaum interessiert war, und dann beschrieb ich in tiefen Länge, wie ich eine LFU implementiert, LRU und FIFO und wie Sie es mit einem einfachen ENUM arg wechseln konnte, und dann merkte ich, dass alle wirklich ich wollte ein einfaches LRU war. So ignorieren die frühere Post von mir, und lassen Sie mich wissen, wenn Sie eine LRU / LFU / FIFO-Cache sehen mögen, die schaltbar über eine Enumeration ist ... nicht wahr? Ok .. hier ist er gehen.
Die einfachste Möglichkeit LRU nur mit dem JDK. Ich implementiert sowohl eine gleichzeitige Version und eine nicht gleichzeitige Version.
habe ich eine gemeinsame Schnittstelle (es Minimalismus ist so wahrscheinlich ein paar Features fehlen, die Sie möchten, aber es funktioniert für meine Anwendungsfälle, aber lassen Sie, wenn Sie Feature XYZ sehen möchten lassen Sie mich wissen ... Ich lebe schreiben 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 ();
}
Sie fragen sich vielleicht, was getSilent ist. Ich benutze dies für die Prüfung. getSilent nicht LRU ändert ein Element Score von.
Zuerst wird die nicht gleichzeitige ein ....
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 potenziell teure Operation, wenn Sie einen großen Cache. Man könnte annehmen LinkedList als Beispiel und fügen Sie eine Reverse-Lookup-Hash-Karte von Elemente Knoten entfernen Operationen viel schneller und konsistenter zu machen. Ich begann auch, aber dann merkte ich es nicht brauchen. Aber ... vielleicht ...
Wenn put aufgerufen wird, wird der Schlüssel zu der Warteschlange hinzugefügt. Wenn get aufgerufen wird, wird der Schlüssel entfernt und wieder hinzugefügt, um die Spitze der Warteschlange.
Wenn Sie den Cache klein ist und das Gebäude ein Element teuer ist, dann soll dies ein guter Cache sein. Wenn Sie den Cache wirklich groß ist, dann könnte die lineare Suche einen Flaschenhals sein, besonders wenn Sie nicht heiße Bereiche des Cache verfügen. Je intensiver der Hot Spots, desto schneller ist die lineare Suche als heiße Gegenstände sind immer an der Spitze der linearen Suche. Wie auch immer ..., was notwendig ist für diese schneller zu gehen, ist ein andere LinkedList schreiben, die eine Entfernungsoperation hat die Reverse Element-Lookup für entfernen Knoten, dann Entfernen etwa so schnell wäre wie ein Schlüssel aus einer Hash-Karte zu entfernen.
Wenn Sie einen Cache unter 1.000 Produkte haben, sollte dies gut funktionieren werden.
Hier ist ein einfacher Test zu zeigen, seineOperationen in Aktion.
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 ();
}
}
Die letzte LRU-Cache war Single-Threaded und bitte wickeln Sie es nicht in einem synchronisierten etwas ....
Hier ist ein Stich bei einer gleichzeitigen 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 wichtigsten Unterschiede sind die Verwendung des ConcurrentHashMap statt HashMap und die Verwendung des Schlosses (ich mit synchronisierten weg bekommen konnte, aber ...).
Ich habe es nicht unter Feuer getestet, aber es scheint wie ein einfacher LRU-Cache, der in 80% der Anwendungsfälle funktionieren könnte, wo Sie eine einfache LRU Karte benötigen.
Ich begrüße Feedback, außer denen, warum Sie nicht verwenden Bibliothek a, b oder c. Der Grund, warum ich nicht immer eine Bibliothek verwenden, ist, weil ich nicht immer jeder Krieg Datei 80MB sein will, und ich schreibe Bibliotheken so neige ich dazu, die Libs Plug-in der Lage mit einer guten genug Lösung an seinem Platz zu machen und kann jemand stecken -in einem anderen Cache-Provider, wenn sie mögen. :) Ich weiß nie, wenn jemand könnte Guava oder ehcache oder etwas anderes brauchen Ich will sie nicht enthalten, aber wenn ich das Caching-Plug-fähig zu machen, ich will sie auch nicht ausschließen.
Reduktion von Abhängigkeiten hat seine eigene Belohnung. Ich liebe ein Feedback zu bekommen, wie dies auch machen einfacher oder schneller oder beides.
Auch wenn jemand weiß von einem bereit zu gehen ....
Ok .. Ich weiß, was Sie denken ... Warum nicht er verwendet nur removeEldest Eintrag von LinkedHashMap und gut, ich soll aber .... aber .. aber .. Das wäre ein FIFO kein LRU und wir versuchen, ein 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 nicht für den obigen Code ...
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 ();
So, hier ist ein schneller und schmutziger FIFO-Cache 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 lange Suche. Sie könnten ein FIFO vor einer LRU Front und das würde die meisten heißen Einträge ganz gut handhaben. Eine bessere LRU wird, dass die Reverse-Element Node-Funktion benötigen.
Wie auch immer ... jetzt, dass ich einige Code geschrieben, lassen Sie mich durch die anderen Antworten gehen und sehen, was ich verpasst ... das erste Mal, dass ich gescannt ihnen.
LinkedHashMap ist O (1), erfordert jedoch die Synchronisation. Keine Notwendigkeit, das Rad dort neu zu erfinden.
2 Möglichkeiten zur Erhöhung der Parallelität:
1.
Erstellen Sie mehrere LinkedHashMap und Hash in ihnen:
Beispiel: LinkedHashMap[4], index 0, 1, 2, 3. Auf dem Schlüssel tut key%4 (oder binary OR auf [key, 3]) zu wählen, welche Karte einen Put zu tun / get / entfernen.
2.
Sie könnten eine ‚fast‘ LRU tun ConcurrentHashMap durch erstreckt, und in der es in jedem der Bereiche einen verknüpften Hash-Map wie Struktur. Sperren auftreten würden mehr granular als ein LinkedHashMap, die synchronisiert ist. Auf einem put oder putIfAbsent nur ein Schloss auf dem Kopf und Schwanz der Liste benötigt wird (je nach Region). Auf einem Entfernen oder bekommen die ganze Region muss gesperrt werden. Ich bin gespannt, ob Atomic verkettete Listen irgendeine Art könnten hier helfen - wahrscheinlich so für den Kopf der Liste. Vielleicht für mehr.
Die Struktur würde den Gesamtauftrag nicht halten, sondern nur die Bestellung pro Region. Solange die Anzahl der Einträge ist viel größer als die Anzahl der Regionen, das ist gut genug für die meisten Caches. Jede Region muss einen eigenen Eintrag Anzahl haben, würde dies verwendet werden, anstatt die globale Zählung für die Räumung Auslöser.
Die Standardanzahl der Regionen in einem ConcurrentHashMap ist 16, die viel für die meisten Server heute ist.
-
wäre einfacher zu schreiben und schneller unter moderater Gleichzeitigkeit.
-
wäre schwieriger zu schreiben, aber viel besser bei sehr hohen Parallelität zu skalieren. Es wäre für den normalen Zugriff langsamer sein (wie
ConcurrentHashMapist langsamer alsHashMap, wo es keine Parallelität)
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 ist ein Open-Source-Projekt für eine ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/
würde ich prüfen, mit java.util.concurrent. PriorityBlockingQueue , mit Priorität durch einen "numberOfUses" counter in jedem Element bestimmt. Ich wäre sehr, sehr vorsichtig , um all meine Synchronisation korrekt, da das "numberOfUses" Zähler bedeuten, dass das Element nicht unveränderlich sein kann.
Das Element-Objekt wäre ein Wrapper für die Objekte im Cache sein:
class CacheElement {
private final Object obj;
private int numberOfUsers = 0;
CacheElement(Object obj) {
this.obj = obj;
}
... etc.
}
Hope, 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);
}
}
LRU Cache implementiert werden kann, ein ConcurrentLinkedQueue und ConcurrentHashMap verwendet, die auch in Multi-Threading-Szenario verwendet werden können. Der Kopf der Warteschlange ist, dass das Element in der Warteschlange, die längste Zeit gewesen ist. Das Ende der Warteschlange ist, dass das Element in der Warteschlange die kürzeste Zeit war. Wenn ein Element in der Karte vorhanden ist, können wir es aus dem LinkedQueue entfernen und am Heck ein.
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, die im Grunde arbeitet als FIFO und nicht THREAD verwendet. Gebrauchte Vergleicher auf der Seite Zeit Schöpfung basiert und auf der Grundlage der führt die Bestellung die Seiten für die zuletzt verwendete Zeit.
Seiten für die Prüfung: 2, 1, 0, 2, 8, 2, 4
Seite hinzugefügt in dem Cache ist: 2
Seite hinzugefügt in dem Cache ist: 1 |
Seite hinzugefügt in dem Cache ist: 0
Seite: 2 bereits im Cache exisit. Des letzten Zugriffs aktualisiert
Page Fault, SEITE: 1, ersetzt durch PAGE: 8
Seite hinzugefügt in dem Cache ist: 8
Seite: 2 bereits im Cache exisit. Des letzten Zugriffs aktualisiert
Page Fault, SEITE: 0, Ersetzt durch PAGE: 4
Seite hinzugefügt in dem Cache ist: 4
OUTPUT
LRUCache Seiten
-------------
Seitenname: 8, PageCreationTime: 1365957019974
Seitenname: 2, PageCreationTime: 1365957020074
Seitenname: 4, PageCreationTime: 1365957020174
Code eingeben hier
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 mein getestet beste gleichzeitige LRU Cache-Implementierung ohne synchronisierten Block ausführen:
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 die LRU-Cache I verwendet werden, die eine LinkedHashMap kapselt und Griffe Gleichzeitigkeit mit einem einfachen Schloss synchronisieren die saftigen Flecke schützt. Es „berührt“ Elemente, wie sie verwendet werden, so dass sie wieder das „frischeste“ Element geworden, so dass es LRU tatsächlich ist. Ich auch die Forderung meiner Elemente hatte eine minimale Lebensdauer aufweisen, die Sie auch als „maximale Leerlaufzeit“ denken kann, erlaubt, dann sind Sie sich für Vertreibung.
Aber ich stimme mit Hanks Abschluss und akzeptierte Antwort - wenn ich das heute noch mal beginnen, würde ich Guava die CacheBuilder Besuche
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 werden Sie in der Regel einige Stücke von Daten über ein Proxy-Objekt werden aufzublicken, (eine URL, String ....) so Interface-weisen Sie werden eine Karte wollen. aber die Dinge treten wollen Sie eine Warteschlange wie Struktur. Intern würde ich zwei Datenstrukturen beibehalten, eine Prioritätswarteschlange und eine HashMap. here eine Implementierung, die in der Lage sollte alles in O (1) Zeit zu tun.
Hier ist eine Klasse ich ziemlich schnell aufgepeitscht:
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;
}
}
}
Hier ist, wie es funktioniert. Die Schlüssel werden in einer verknüpften Liste mit den ältesten Schlüsseln in der Vorderseite der Liste gespeichert (neue Schlüssel gehen nach hinten) so, wenn Sie brauchen, um ‚Eject‘ etwas, das Sie es gerade die Spitze der Warteschlange Pop-off und dann den Schlüssel verwenden, um den Wert von der Karte entfernen. Wenn ein Element referenziert wird Sie die Valueholder aus der Karte greifen und verwenden dann die queuelocation Variable den Schlüssel aus seiner aktuellen Position in der Warteschlange zu entfernen und es dann an der Rückseite der Warteschlange gestellt (seine jetzt das zuletzt verwendete). Hinzufügen Dinge ist so ziemlich das gleiche.
Ich bin sicher, Theres eine Tonne Fehler hier und ich habe keine Synchronisation durchgeführt. aber diese Klasse bietet O (1) Zugabe zu dem Cache, O (1) Entfernung von alten Gegenständen und O (1) Abrufen von Cache-Elementen. Auch eine triviale Synchronisation (nur jede öffentliche Methode synchronisieren) müßte noch wenig Sperrenkonflikte aufgrund der Laufzeit. Wenn jemand eine kluge Synchronisierung Tricks hat wäre ich sehr interessiert. Auch ich bin sicher, es gibt einige zusätzliche Optimierungen, die Sie implementieren könnten die maxsize Variable in Bezug auf die Karte.
Hier finden Sie aktuelle ConcurrentSkipListMap . Es sollte Ihnen (n) Zeit zum Testen anmelden und das Entfernen eines Elements, wenn es bereits im Cache enthalten ist, und konstante Zeit für die Wiederschöpf es.
Sie würden auch nur einen Zähler usw. benötigen und Wrapperelement Ordnung der LRU, um zu erzwingen und die letzten Sachen sicherzustellen, wird verworfen, wenn der Cache voll ist.
Hier ist meine kurze Implementierung, bitte kritisieren oder verbessern!
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 für dieses Problem
simplelrucache bietet THREAD, sehr einfach, nicht ausgeschüttete LRU Caching mit TTL-Unterstützung. Es bietet zwei Ausführungen:
- Concurrent basierend auf ConcurrentLinkedHashMap
- Synchronisiert basierend auf LinkedHashMap
Sie können es hier finden: http://code.google.com/p/simplelrucache/
Ich bin auf der Suche nach einem besseren LRU-Cache Java-Code. Ist es möglich, dass Sie Ihren Java-LRU-Cache-Code mit LinkedHashMap und Collections#synchronizedMap zu teilen? Derzeit verwende ich LRUMap implements Map und der Code funktioniert gut, aber ich bin immer ArrayIndexOutofBoundException auf Lasttests 500 Benutzer auf der folgenden Methode. Das Verfahren bewegt das letzte Objekt Vorderseite der Warteschlange.
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) und put(Object key, Object value) Methode ruft die oben moveToFront Verfahren.
Gesucht Kommentar auf die Antwort von Hank gegeben hinzufügen, aber einige, wie ich bin nicht in der Lage - es bitte als Kommentar zu behandeln
LinkedHashMap Zugang aufrechterhält als auch basierend auf Parameter im Konstruktor übergeben Es hält doppelt Liste gefüttert zu halten, um (siehe LinkedHashMap.Entry)
@Pacerier es ist richtig, dass LinkedHashMap gleiche Reihenfolge hält, während Iteration, wenn das Element wieder hinzugefügt wird, aber das ist nur bei Auftrags-Modus.
Dies ist, was ich in Java-Dokumentation von LinkedHashMap.Entry Objekt gefunden
/**
* 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);
}
}
Diese Methode übernimmt die zuletzt zugegriffen Element der Bewegung von der Liste zu beenden. Also alles in allem LinkedHashMap ist beste Datenstruktur für LRUCache implementieren.
Ein weiterer Gedanke und sogar eine einfache Implementierung mit LinkedHashMap Sammlung von Java.
LinkedHashMap bereitgestellt Methode removeEldestEntry und die in der in Beispiel erwähnt Weise außer Kraft gesetzt werden. Durch die Standardimplementierung dieser Sammlung Struktur ist falsch. Wenn seine wahre Größe und diese Struktur über die ursprüngliche Kapazität geht als älteste oder ältere Elemente werden entfernt.
Wir können eine pageno und Seiteninhalt in meinem Fall pageno haben ist integer und Seiteninhalt i gehalten haben Seitennummer Werte String.
import java.util.LinkedHashMap; import java.util.Map; /** * @author Deepak Singhvi * */ public class LRUCacheUsingLinkedHashMap { private static int CACHE_SIZE = 3; public static void main(String[] args) { System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99"); System.out.println("----------------------------------------------\n"); // accessOrder is true, so whenever any page gets changed or accessed, // its order will change in the map, LinkedHashMap<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 "); } }
Ergebnis von oben Codeausführung ist wie folgt:
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
Nach dem @sanjanab Konzept (aber nach Korrekturen) Ich habe meine Version des LRUCache bietet auch die Verbraucher, die etwas mit den entfernten Elementen tun können, wenn nötig.
public class LRUCache<K, V> {
private ConcurrentHashMap<K, V> map;
private final Consumer<V> onRemove;
private ConcurrentLinkedQueue<K> queue;
private final int size;
public LRUCache(int size, Consumer<V> onRemove) {
this.size = size;
this.onRemove = onRemove;
this.map = new ConcurrentHashMap<>(size);
this.queue = new ConcurrentLinkedQueue<>();
}
public V get(K key) {
//Recently accessed, hence move it to the tail
if (queue.remove(key)) {
queue.add(key);
return map.get(key);
}
return null;
}
public void put(K key, V value) {
//ConcurrentHashMap doesn't allow null key or values
if (key == null || value == null) throw new IllegalArgumentException("key and value cannot be null!");
V existing = map.get(key);
if (existing != null) {
queue.remove(key);
onRemove.accept(existing);
}
if (map.size() >= size) {
K lruKey = queue.poll();
if (lruKey != null) {
V removed = map.remove(lruKey);
onRemove.accept(removed);
}
}
queue.add(key);
map.put(key, value);
}
}
