LRUとLFUの違いは何ですか？

質問

とはどのような違いがあるのでしょうか？ LRU と LFU キャッシュの実装は？

LRUを実装するのに LinkedHashMap . しかし、LFUキャッシュはどのように実装するのでしょうか？

どのように解決するのですか？

以下、キャッシュ容量が3で、常にキャッシュ要求がある場合を考えてみましょう。

A, B, C, A, A, A, A, A, A, A, A, A, A, A, B, C, D

を考えるだけなら 最近使ったもの(LRU) キャッシュを HashMap + 二重リンクリストの実装で、立ち退き時間 O(1) とロード時間 O(1) で考えると、上記のようにキャッシュ要求を処理しながら、以下の要素がキャッシュされることになります。

[A]
[A, B]
[A, B, C]
[B, C, A] <- a stream of As keeps A at the head of the list.
[C, A, B]
[A, B, C]
[B, C, D] <- here, we evict A, we can do better! 

この例を見ると、もっと良い方法があることが簡単にわかります。将来的にAを要求する可能性がより高いことを考えると、たとえそれが最も最近使われたとしても、それを退去させるべきではないでしょう。

A - 12
B - 2
C - 2
D - 1

最低使用頻度 (LFU) キャッシュはこの情報を利用し、キャッシュ要求が何回使われたかを追跡し、退去アルゴリズムに利用します。