最も最近使用されたキャッシュを実装する方法

Question

最も最近使用されたオブジェクトのキャッシュを実装する最良の方法は何でしょうか？ここで

が要件と制限されているインタフェースは少しHashtableのようになるので...

• オブジェクトは、/コール」へ
• を入れます、キー/値オブジェクト/オブジェクトのペアとして格納されていますそのオブジェクトを最も最近使用されたものとしてマークします。
• いつでも、最も最近使用されたオブジェクトをキャッシュからパージすることができます。
• 高速である必要があります（Hashtableのように高速）
• オブジェクトの数が多いため、リストの検索が十分ではありません。
• 実装はJavaMEを使用して行う必要があります。したがって、サードパーティ製のコードまたは標準のJavaライブラリのきちんとしたライブラリクラスを使用する範囲はほとんどありません。このような理由から、私はペグ以外のソリューションの推奨事項ではなく、アルゴリズム的な回答を探しています。

Answer 1

Javaコレクションは、すぐにキャッシュを構築するのに適したLinkedHashMapを提供します。あなたがのための1つを実装し始める必要があり、それを見て、あなたはそれをコピー＆ペーストすることができない場合

http://kickjava.com/src/java/util/LinkedHashMap.java.htm

：あなたは、おそらくJavaのMEでこれを持っていませんが、ここではソースコードを入手することができますモバイルアプリに含める基本的な考え方は、リンクされたリストを地図要素に含めることです。誰かが出入りするたびにこの情報を更新し続けると、効率的にアクセス順番を追跡して注文を使うことができます。

ドキュメントには、メソッドをオーバーライドすることによってMRUキャッシュを構築するための手順が含まれています。あなたが本当にしなければならないすべてはLinkedHashMapを拡張するクラスを作成し、そのようなメソッドをオーバーライドしている：

あなたはクラスが挿入によって、または使用によって順番で物事を保存するかどうかを指定できます constructorもあります

private static final int MAX_ENTRIES = 100; 

protected boolean removeEldestEntry(Map.Entry eldest) { 
    return size() > MAX_ENTRIES; 
} 

public LinkedHashMap(int initialCapacity, 
        float loadFactor, 
        boolean accessOrder) 

パス真を使用順序と偽ための挿入順序のために：、あなたも、あなたの立ち退きポリシーのために少し柔軟性を持っているので。

Answer 2

既に実装されているものを実装するのはなぜですか？ Ehcacheを使用します。

しかしは、サードパーティのライブラリは完全に問題外であれば、私はあなたがこのようになり、データ構造を実装するために探していると思います：

• 基本的にはHashMapです（HashMap<Object, Object>場合を拡張あなたになります）
• マップ内の各値は、ソートされたリスト内のオブジェクトを指します。
• 最近使用したオブジェクトは、リストの先頭に追加されます - O(1)
• リストの末尾を切り捨て、最近最も使用される手段パージ - O(1)
• はまだあなたが検索地図与えますが、それでも最初の最近使用したアイテムを保持します...

Answer 3

もう1つのアプローチは、のJavaの同時実行性のセクション5.6を参照してください.Brian Goetz氏の「：効率的でスケーラブルな結果キャッシュの構築」あなたの目的のためにそれをカスタマイズしなければならないかもしれませんが、Memoizerを見てください。

私が理解できないことは、JavaがConcurrentLinkedHashMapをすぐに持っていない理由です。このデータ構造は、キャッシュ構築に非常に役立ちます。

Answer 4

ロックを必要とするため、ConcurrentLinkedHashMapを構築することは困難です。ロック付きのLinkedHashMapは簡単ですが、必ずしもパフォーマンスが良いとは限りません。並行バージョンは、ロック分割、または理想的にはロックを非常に安価にするCAS操作を行うことによって、ロック量を減らそうとします。 CASの運用が高価になる場合は、同様にバケット分割が役立ちます。 LRUはすべてのアクセス操作で書き込みを要求し、二重リンクリストを使用するため、これは純粋なCAS操作で実装するのは非常に難しい作業です。私はそれを試みましたが、アルゴリズムを成熟させ続ける必要があります。 ConcurrentLinkedHashMapを検索すると、私のプロジェクトページが表示されます...

Java MEでCAS操作がサポートされていない場合は、基本的な同期が可能です。サーバ側のスレッド数が多い場合にパフォーマンスの問題が発生していることを考えれば、おそらくLHMで十分です。だから上記の答え+1。