6

LinkedHashMapを使用してLRUキャッシュを構築する方法（Java 6でLRUキャッシュをどのように実装しますか？）について少し混乱しています。内部でどのように機能するかを確実に理解したいと思います。

LinkedHashMapを拡張し、そのままオーバーライドするクラスLRUMapを定義するとしますremoveEldestEntry(final Map.Entry<A, B> eldest)。

次に、データ構造を構築し、4つのアイテムをマップに挿入します

    LRUMap<String,String> map = new LRUMap<String,String>(3); //capacity 3
    map.put("a", "a");
    map.put("b", "b");
    map.put("c", "c");
    map.put("d", "d");

そして、マップに追加するすべてのアイテムとリンクするために、開始ノードとして呼び出されたものを相互にLinkedHashMap使用します。したがって、この場合はEntry objectheader

   [header] ->  ["a"] -> ["b"] -> ["c"] -> ["d"] -> [header]

ヘッダーエントリオブジェクトは、header.before = header.after =ヘッダーが最初に作成されるため、二重リンクリストの開始と終了の両方になります。

そして、マップが私が望む最大エントリ（3アイテム）に達したとしましょう。

    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
         removeEntryForKey(eldest.key);
    }
    .....

つまり、最初に["a"]を削除するということですか？
そして、呼び出したときget(Object key)に、ヘッダーノードの前にそのキー（「b」としましょう）を配置するリストの順序を再配置します。

     [header] ->  ["c"] -> ["d"] -> ["b"] -> [header]

それを明確にしたいだけです。

4

1 に答える 1

11
  1. はい; エントリ<"a", "a">が最初に削除されます:-)

  2. 多分; LinkedHashMapデフォルトでは、 access- orderではなくinsertion-orderを使用します...仕様から直接：

    Map予測可能な反復順序を使用した、インターフェイスのハッシュテーブルとリンクリストの実装。HashMapこの実装は、すべてのエントリを介して実行される二重リンクリストを維持するという点で異なります。このリンクリストは、反復順序を定義します。これは通常、キーがマップに挿入された順序（挿入順序）です。

    そうは言っても、 access-orderLinkedHashMapもサポートしています。

    リンクされたハッシュマップを作成するための特別なconstructor機能が用意されており、その反復順序は、エントリが最後にアクセスされた順序であり、最近アクセスされた順序から最近アクセスされた順序（access-order）までです。この種のマップは、LRUキャッシュの構築に最適です。putorメソッドを呼び出すgetと、対応するエントリにアクセスできます（呼び出しの完了後に存在すると想定）。

    したがって、挿入順序get("b")を使用している場合、順序は;から変更されません。アクセス順序（通常はLRUキャッシュが使用します;-)を使用している場合は、順序が変更されます。

他に何かご質問は？:-)

于 2012-08-19T21:49:37.490 に答える