並行LRUキャッシュの実装

Question

スレッドの安全で効率的なキャッシュ実装コードLRUが必要です。 以下のコードはスレッドセーフではありません。このコードは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; 
    } 

    @Override 
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) { 
     return super.size() > maxEntries; 
    } 
} 

Answer 1

あなたができる最善のは、それがスレッドセーフにするためにあるのjavadocで説明したようにCollections.synchronizedMap(map)でそれをラップすることです。この実装はを同期化されていないことを

注意。複数のスレッド が同時にリンクされたハッシュマップにアクセスし、少なくとも1つのスレッド がマップを構造的に変更する場合は、外部と同期する必要があります。 これは通常、 がマップを自然にカプセル化するオブジェクトで同期することで実現します。そのようなオブジェクトが存在しない場合は、メソッドを使用してマップ を「ラップする」必要があります。あなたが敷居コンテンツ上の任意の繰り返しを保護する必要が完全にスレッドセーフにするには十分ではありませんが

Map m = Collections.synchronizedMap(new LinkedHashMap(...)); 

：この は、マップへの偶発的な非同期 アクセスを防ぐために、作成時に最もよく行われていますオブジェクトのモニターとしてラップマップのインスタンスを使用して、マップの：

Map m = Collections.synchronizedMap(map); 
... 
Set s = m.keySet(); // Needn't be in synchronized block 
... 
synchronized (m) { // Synchronizing on m, not s! 
    Iterator i = s.iterator(); // Must be in synchronized block 
    while (i.hasNext()) 
     foo(i.next()); 
} 

---

がこれはほとんどすべてのことができ簡単には、JDKのボックスの内容と同じですが、スレッドセーフで効率的なものをお望みなら、CacheをGoogle Guavaからご覧ください。ここで

はguavaで構築された2の最大サイズとLRUキャッシュの例である：

ConcurrentMap<String, String> cache = 
    CacheBuilder.newBuilder() 
     .maximumSize(2L) 
     .<String, String>build().asMap(); 
cache.put("a", "b"); 
cache.put("b", "c"); 
System.out.println(cache); 
cache.put("a", "d"); 
System.out.println(cache); 
cache.put("c", "d"); 
System.out.println(cache); 

出力：

{b=c, a=b} 
{b=c, a=d} 
{c=d, a=d} 

Answer 2

ラッパーとしてCollections.synchronozedMap()を使用する場合と比較して、私はConcurrentHashMapとConcurrentLinkedListを一緒に使用して012を実装する方が良いと思うインターフェース、必要に応じてListインターフェースが必要です。ただし、内部マップの操作と並行処理を確実に行うためのリストの間にカスタムロジックが必要です。しかし、パフォーマンスはまだ完全に​​マップよりも良いことができます。

Answer 3

見つかったグアバのCache。自分で使ったことはありません。

キャッシュはConcurrentMapに似ていますが、全く同じではありません。

出典：https://github.com/google/guava/wiki/CachesExplained

例：

LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder() 
     .expireAfterAccess(10, TimeUnit.MINUTES) 
     .maximumSize(1000) 
     .build(
      new CacheLoader<Key, Graph>() { 
      public Graph load(Key key) { // no checked exception 
       return createExpensiveGraph(key); 
      } 
      }); 

... 
return graphs.getUnchecked(key);