Java で LRU キャッシュを実装するにはどうすればよいでしょうか?
https://stackoverflow.com/questions/221525
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
EHCache や OSCache などとは言わないでください。この質問の目的として、SDK のみを使用して独自のものを実装したいと仮定します (実行して学習)。キャッシュがマルチスレッド環境で使用されるとすると、どのデータ構造を使用しますか?私はすでに使用して実装しました リンクされたハッシュマップ そして コレクション#synchronizedMap, 、しかし、新しい同時コレクションのどれかがより良い候補となるかどうか興味があります。
アップデート：ただ読み進めていただけだった イエッゲの最新作 このナゲットを見つけたとき、
一定時間のアクセスが必要で、挿入順序を維持したい場合は、本当に素晴らしいデータ構造である LinkedHashMap 以外に優れたものはありません。より素晴らしいものになる唯一の方法は、同時バージョンが存在する場合です。しかし悲しいかな。
私も入社前はほぼ同じことを考えていました LinkedHashMap + Collections#synchronizedMap 上で述べた実装。単に何かを見落としていたわけではないことがわかってよかったです。
これまでの回答に基づくと、同時実行性の高い LRU を実現するための最善の策は、拡張することだと思われます。 同時ハッシュマップ 同じロジックの一部を使用して、 LinkedHashMap を使用します。
解決 3
これを今日ゼロからやり直す場合は、Guavaの CacheBuilder 。
他のヒント
これらの提案の多くは好きですが、今のところは LinkedHashMap + Collections.synchronizedMap に固執すると思います。将来これを再検討する場合は、おそらく LinkedHashMap が HashMap を拡張するのと同じ方法で ConcurrentHashMap を拡張することに取り組みます。
更新：
リクエストにより、ここに私の現在の実装の要点があります。
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));
または、次のApache Commonsデータ構造を使用します。
これはラウンド2です。
最初のラウンドは私が思いついたもので、それから私は私の頭の中にもう少し深く染み込んだドメインでコメントを読み直しました。
これが、他のバージョンに基づいて動作することを示す単体テストを備えた最も単純なバージョンです。
最初に非並行バージョン：
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 ();
}
}
trueフラグは、getsおよびputsのアクセスを追跡します。 JavaDocsを参照してください。コンストラクターに対するtrueフラグのないremoveEdelstEntryは、FIFOキャッシュを実装するだけです（FIFOおよびremoveEldestEntryに関する以下の注を参照）。
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 ();
}
同時バージョンの場合...
パッケージ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 ();
}
}
最初に非同時バージョンを取り上げる理由がわかります。上記は、ロックの競合を減らすためにいくつかのストライプを作成しようとします。したがって、キーをハッシュし、そのハッシュを検索して実際のキャッシュを見つけます。これにより、キーハッシュアルゴリズムの広がり具合に応じて、かなりのエラー内で制限サイズが提案/大まかな推測になります。
これは、同時バージョンがおそらく機能することを示すテストです。 :)（実際にテストするのは実際の方法です）。
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 ();
}
}
これは最後の投稿です。LRUキャッシュではなくLFUであったため、最初に削除した投稿です。
これをもう一度やりたいと思いました。実装が多すぎない標準のJDKを使用して、最も単純なバージョンのLRUキャッシュを作成しようとしていました。
これが私が思いついたものです。 LRUの代わりにLFUを実装し、FIFOとLRUサポートを追加したので、最初の試みはちょっとした災害でした...そして、それがモンスターになっていることに気付きました。それから、私はほとんど興味のない仲間のジョンと話を始めました。そして、LFU、LRU、FIFOをどのように実装し、単純なENUM引数でどのように切り替えることができるかを詳しく説明しました。シンプルなLRUでした。だから私からの以前の投稿を無視し、enum経由で切り替え可能なLRU / LFU / FIFOキャッシュを表示したい場合は教えてください...いいえ？わかりました。ここに行きます。
JDKのみを使用した最も単純なLRU。同時バージョンと非同時バージョンの両方を実装しました。
共通のインターフェイスを作成しました（ミニマリズムなので、必要な機能がいくつか欠けている可能性がありますが、私のユースケースでは機能しますが、機能XYZをご覧になりたい場合はお知らせください...コード）。
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 ();
}
getSilent とは何かと疑問に思うかもしれません。これをテストに使用します。 getSilentは、アイテムのLRUスコアを変更しません。
最初に非コンカレント....
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 ();
}
}
queue.removeFirstOccurrence は、キャッシュが大きい場合、潜在的に負荷の高い操作です。 LinkedListを例に取り、要素からノードに逆ルックアップハッシュマップを追加して、削除操作をより高速で一貫性のあるものにすることができます。私も始めましたが、必要ないことに気づきました。しかし...多分...
put が呼び出されると、キーがキューに追加されます。 get が呼び出されると、キーが削除され、キューの先頭に再度追加されます。
キャッシュが小さく、アイテムの構築に費用がかかる場合、これは適切なキャッシュになります。キャッシュが非常に大きい場合、特にキャッシュのホットエリアがない場合、線形検索がボトルネックになる可能性があります。ホットスポットの強度が高いほど、ホットアイテムが常に線形検索の先頭にあるため、線形検索が高速になります。とにかく...これを高速化するために必要なのは、削除のためのノードルックアップと逆の要素を持つ削除操作を持つ別のLinkedListを書くことです、そして削除はハッシュマップからキーを削除するのとほぼ同じくらい速いでしょう。
1,000アイテム未満のキャッシュがある場合、これは問題なく動作するはずです。
これは、動作中の動作を示す簡単なテストです。
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 ();
}
}
最後のLRUキャッシュはシングルスレッドでした。
LinkedHashMap はO（1）ですが、同期が必要です。そこで車輪を再発明する必要はありません。
並行性を高めるための2つのオプション：
1。
複数の LinkedHashMap を作成し、それらにハッシュします。
例： LinkedHashMap [4]、インデックス0、1、2、3 。キーで key％4 （または [key、3] の binary OR ）を実行して、put / get /を実行するマップを選択します削除します。
2。
ConcurrentHashMap を拡張し、その内部の各領域に構造のようなリンクされたハッシュマップを持つことにより、「ほぼ」LRUを実行できます。ロックは、同期される LinkedHashMap よりも細かく行われます。 put または putIfAbsent では、リストの先頭と末尾のロックのみが必要です（リージョンごと）。削除または取得時には、領域全体をロックする必要があります。ある種のアトミックリンクリストがここで役立つかどうかは、興味があります。多分もっと。
構造は全体の順序を保持せず、地域ごとの順序のみを保持します。エントリの数がリージョンの数よりはるかに多い限り、これはほとんどのキャッシュに十分です。各リージョンには独自のエントリカウントが必要です。エビクショントリガーのグローバルカウントではなく、これが使用されます。
ConcurrentHashMap のデフォルトのリージョン数は16です。これは、今日のほとんどのサーバーで十分です。
-
中程度の並行性のもとでは、記述がより簡単になり、高速になります。
-
記述はより困難になりますが、非常に高い同時実行性ではるかに拡張性が高くなります。通常のアクセスの場合は遅くなります（
ConcurrentHashMapが同時性のないHashMapよりも遅いのと同じように）
2つのオープンソース実装があります。
Apache SolrにはConcurrentLRUCacheがあります： https：// lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html
ConcurrentLinkedHashMapのオープンソースプロジェクトがあります。 http://code.google.com/p/concurrentlinkedhashmap/
java.util.concurrentの使用を検討します。 PriorityBlockingQueue 、＆quot;使用回数＆quot;によって決定される優先順位各要素のカウンター。 「numberOfUses＆quot; counterは、要素が不変にできないことを意味します。
要素オブジェクトはキャッシュ内のオブジェクトのラッパーになります：
class CacheElement {
private final Object obj;
private int numberOfUsers = 0;
CacheElement(Object obj) {
this.obj = obj;
}
... etc.
}
これがお役に立てば幸いです。
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キャッシュは、マルチスレッドシナリオでも使用できるConcurrentLinkedQueueおよびConcurrentHashMapを使用して実装できます。キューの先頭は、キューに最も長く存在していた要素です。キューの末尾は、キューに最短時間であった要素です。マップに要素が存在する場合、LinkedQueueからその要素を削除して、末尾に挿入できます。
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);
}
}
LRUの実装です。 PriorityQueueを使用しました。これは基本的にFIFOとして機能し、スレッドセーフではありません。 ページ時間の作成および順序付けの実行に基づいて使用されるコンパレータ 最も最近使用された時間のページの。
検討対象のページ：2、1、0、2、8、2、4
キャッシュに追加されたページ：2
キャッシュに追加されたページは次のとおりです：1
キャッシュに追加されたページ：0
ページ：2はすでにキャッシュに存在します。最終アクセス時刻が更新されました
ページ違反、ページ：1、ページに置き換え：8
キャッシュに追加されたページ：8
ページ：2はすでにキャッシュに存在します。最終アクセス時刻が更新されました
ページ違反、ページ：0、ページに置き換え：4
キャッシュに追加されたページ：4
出力
LRUCacheページ
-------------
PageName：8、PageCreationTime：1365957019974
PageName：2、PageCreationTime：1365957020074
PageName：4、PageCreationTime：1365957020174
ここにコードを入力
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;
}
}
同期ブロックを使用しない、テスト済みの最高のパフォーマンスを発揮する同時LRUキャッシュ実装を次に示します。
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);
}
}
これは私が使用するLRUキャッシュで、LinkedHashMapをカプセル化し、ジューシーなスポットを保護する単純な同期ロックで同時実行を処理します。 「触る」それらが「最新」になるように使用される要素再び要素、それは実際にLRUです。また、要素の寿命を最短にする必要がありました。これは、「最大アイドル時間」と考えることもできます。許可されたら、立ち退きの準備が整います。
ただし、ハンクの結論に同意し、回答を受け入れました。今日これを再び開始する場合は、Guavaの CacheBuilder を確認します。
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
public class MaxIdleLRUCache<KK, VV> {
final static private int IDEAL_MAX_CACHE_ENTRIES = 128;
public interface DeadElementCallback<KK, VV> {
public void notify(KK key, VV element);
}
private Object lock = new Object();
private long minAge;
private HashMap<KK, Item<VV>> cache;
public MaxIdleLRUCache(long minAgeMilliseconds) {
this(minAgeMilliseconds, IDEAL_MAX_CACHE_ENTRIES);
}
public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries) {
this(minAgeMilliseconds, idealMaxCacheEntries, null);
}
public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries, final DeadElementCallback<KK, VV> callback) {
this.minAge = minAgeMilliseconds;
this.cache = new LinkedHashMap<KK, Item<VV>>(IDEAL_MAX_CACHE_ENTRIES + 1, .75F, true) {
private static final long serialVersionUID = 1L;
// This method is called just after a new entry has been added
public boolean removeEldestEntry(Map.Entry<KK, Item<VV>> eldest) {
// let's see if the oldest entry is old enough to be deleted. We don't actually care about the cache size.
long age = System.currentTimeMillis() - eldest.getValue().birth;
if (age > MaxIdleLRUCache.this.minAge) {
if ( callback != null ) {
callback.notify(eldest.getKey(), eldest.getValue().payload);
}
return true; // remove it
}
return false; // don't remove this element
}
};
}
public void put(KK key, VV value) {
synchronized ( lock ) {
// System.out.println("put->"+key+","+value);
cache.put(key, new Item<VV>(value));
}
}
public VV get(KK key) {
synchronized ( lock ) {
// System.out.println("get->"+key);
Item<VV> item = getItem(key);
return item == null ? null : item.payload;
}
}
public VV remove(String key) {
synchronized ( lock ) {
// System.out.println("remove->"+key);
Item<VV> item = cache.remove(key);
if ( item != null ) {
return item.payload;
} else {
return null;
}
}
}
public int size() {
synchronized ( lock ) {
return cache.size();
}
}
private Item<VV> getItem(KK key) {
Item<VV> item = cache.get(key);
if (item == null) {
return null;
}
item.touch(); // idle the item to reset the timeout threshold
return item;
}
private static class Item<T> {
long birth;
T payload;
Item(T payload) {
this.birth = System.currentTimeMillis();
this.payload = payload;
}
public void touch() {
this.birth = System.currentTimeMillis();
}
}
}
キャッシュの場合、通常はプロキシオブジェクト（URL、文字列...）を介してデータの一部を検索するため、インターフェイス的にはマップが必要になります。しかし、物事を追い出すためには、構造のようなキューが必要です。内部的には、Priority-QueueとHashMapの2つのデータ構造を維持します。ここでは、O（1）時間ですべてを実行できるはずの実装を示します。
これは私が非常に簡単にまとめたクラスです：
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;
}
}
}
次のように動作します。キーはリンクされたリストに保存され、最も古いキーがリストの前にあります（新しいキーが後ろに移動します）。マップから値を削除します。アイテムが参照されると、マップからValueHolderを取得し、queuelocation変数を使用してキュー内の現在の場所からキーを削除し、キューの最後に配置します（最近使用したもの）。物事を追加することはほとんど同じです。
ここには大量のエラーがあり、同期も実装していません。ただし、このクラスは、キャッシュへのO（1）追加、古いアイテムのO（1）削除、およびキャッシュアイテムのO（1）取得を提供します。些細な同期（すべてのパブリックメソッドを同期するだけ）でも、実行時のロック競合はほとんどありません。誰かが巧妙な同期のトリックを持っているなら、私は非常に興味があるでしょう。また、マップに関してmaxsize変数を使用して実装できる最適化がいくつかあると確信しています。
見て 同時スキップリストマップ. 。要素がすでにキャッシュに含まれている場合は要素をテストして削除するための log(n) 時間が得られ、要素を再追加するための一定の時間が得られます。
LRU の順序を強制し、キャッシュがいっぱいになったときに最新のものを確実に破棄するには、カウンターなどとラッパー要素が必要です。
これは私の短い実装です。批判または改善してください！
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);
}
}
この問題に対する独自の実装
simplelrucacheは、TTLサポートを備えた、スレッドセーフで非常にシンプルな非分散LRUキャッシングを提供します。次の2つの実装を提供します。
- ConcurrentLinkedHashMapに基づく同時実行
- LinkedHashMapに基づいて同期
ここで見つけることができます： http://code.google.com/p/simplelrucache/
Javaコードを使用して、より良いLRUキャッシュを探しています。 LinkedHashMap および Collections＃synchronizedMap を使用してJava LRUキャッシュコードを共有することは可能ですか？現在、 LRUMapはMap を実装しており、コードは正常に動作していますが、以下のメソッドで500人のユーザーを使用した負荷テストで ArrayIndexOutofBoundException を取得しています。このメソッドは、最近のオブジェクトをキューの先頭に移動します。
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（オブジェクトキー）および put（オブジェクトキー、オブジェクト値）メソッドは、上記の moveToFront メソッドを呼び出します。
ハンクの回答にコメントを追加したいのですが、どうにかできません-コメントとして扱ってください
LinkedHashMapは、コンストラクターで渡されたパラメーターに基づいてアクセス順序も維持します 順序を維持するために二重に並んだリストを保持します（LinkedHashMap.Entryを参照）
@Pacerier LinkedHashMapは、要素が再度追加された場合、反復中に同じ順序を維持するのは正しいですが、それは挿入順序モードの場合のみです。
これはLinkedHashMap.EntryオブジェクトのJavaドキュメントで見つけたものです
/**
* 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);
}
}
このメソッドは、最近アクセスした要素をリストの最後に移動します。したがって、すべてのLinkedHashMapはすべて、LRUCacheの実装に最適なデータ構造です。
別の考え方と、JavaのLinkedHashMapコレクションを使用した単純な実装です。
LinkedHashMapはメソッドremoveEldestEntryを提供し、例で説明した方法でオーバーライドできます。デフォルトでは、このコレクション構造の実装はfalseです。この構造の実際のサイズが初期容量を超えると、最も古い要素または古い要素が削除されます。
pagenoが整数であり、pagecontentがページ番号の値の文字列を保持している場合、pagenoとpage contentを持つことができます。
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 "); } }
上記のコード実行の結果は次のとおりです。
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
@sanjanabの概念に従って（ただし修正後）、必要に応じて削除されたアイテムで何かを行うことができるConsumerも提供するLRUCacheのバージョンを作成しました。
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);
}
}
