LRU キャッシュ アルゴリズムの Java カスタム実装

背景

LinkedHashMap は HashMap を継承し、内部的に removeEldestEntry メソッドを提供します。これは、LRU 戦略を実装するための鍵となります。HashMap は、LinkedHashMap 専用のコールバック メソッド afterNodeAccess、afterNodeInsertion、afterNodeRemoval の 3 つも提供します。これら 3 つのメソッドの文字通りの意味は非常に理解しやすく、それぞれノード アクセス、ノード挿入、ノード削除後に実行される動作です。上記の動作に基づいて、LinkedHashMap は LRUCache の機能を実現できます。

[[142638]]

LinkedHashMap の eldest について: eldest は文字通り最も古いという意味です。LinkedHashMap には accessOrder というフィールドがあります。accessOrder が true の場合、LinkedHashMap の内部ノードは訪問回数に応じてソートされます。最も古いノードは訪問回数が最も少ないノードです。 accessOrder が false の場合、LinkedHashMap の内部ノードは挿入順にソートされます。最も古いノードは、最初に挿入されたノードです。デフォルト値は false です。

成し遂げる

LRUCacheを自分で実装するには、removeEldestEntryメソッドをオーバーライドするだけです。コードは次のとおりです。

プライベート静的クラス LRUCache<K, V> は LinkedHashMap<K, V> を拡張します。
{
プライベート静的最終ロングシリアルバージョンUID = -9111855653176630846L;
プライベート静的int MAX_ELEMENTS;

パブリック LRUCache(int initCap, int maxSize) は IllegalArgumentException をスローします
{
スーパー(initCap、0.75f、true);
（最大サイズ<0）の場合
新しい IllegalArgumentException() をスローします。
MAX_ELEMENTS = 最大サイズ;
}

@オーバーライド
保護されたブール値の長男エントリを削除します(Map.Entry<K, V> 長男)
{
size() > MAX_ELEMENTS を返します。
}
}

上記のコードでは、保存されるノードの最大数を制限するために MAX_ELEMENTS 変数が必要です。ノードを挿入するときに、現在のノード数がこの値を超えると、LRU 戦略に従ってアクセスが最も少ないノードが削除されます。ここで注目すべきは、デフォルトの LinkedHashMap は挿入順序を保証し、つまりノードは挿入順にソートされるため、削除された場合でも、最後に挿入されたノードが削除されるということです。ただし、コンストラクタで true を渡しました。このパラメータは、LinkedHashMap 内のノードがどのようにソートされるかを決定します。パラメータが true の場合、内部ノードは最新のアクセス時間に従ってソートされることを意味します。false の場合、挿入順にソートされることを意味します。これまでに、単純な LRUCache 実装が完了しました。

知らせ

LinkedHahsMap 実装自体はスレッドセーフではないため、この LRUCache もスレッドセーフではありません。マルチスレッド アクセスが必要な場合は、次のように使用できます: LRUCache cache = Collections.synchronizedMap (new LRUCache (10, 10))。この方法では、キャッシュは複数のスレッドで get/put 操作を実行できます。ただし、この方法で取得されたキャッシュは、複数のスレッドによって走査される場合、依然として安全ではありません。したがって、キャッシュを複数のスレッドでトラバースすることはできず、公式ドキュメントでも、同期マップをトラバースするときにはマップ自体を同期に使用することを推奨しています。