java - 最も単純で最小限のデータ構造を使用して、LFU キャッシュをどのように実装できますか?

Question

私はインタビューでこの質問をされました。彼は最初に LRU と LFU の違いについて尋ね、次に両方を実装するように求めました。LinkedHashMap を介して LRU を実装できることは知っていましたが、LFU と混同してしまいました。説明がわかりやすい最も単純なデータ構造で実装する方法を教えてもらえますか? また、LinkedHashMap でも実装できますか?

Answer 1

LinkedListキャッシュ エントリにキーが設定されていると仮定すると、キュー ( ) とマップ ( )を使用して実行できますHashMap。

(キューとマップがいっぱいであると仮定します)キュー
の境界bを選択します。キャッシュ要求ごとに、要求されたページのキーをキューにプッシュしてから、キューをポーリングします。
必要なページがマップにある場合は、そのページを返します。ページがマップにない場合は、必要なページのマップまたはキーにもあるキューで最も頻繁に発生しないキーを見つけます。そのキーが目的のページのキーである場合は、何もしません。それ以外の場合は、そのキーのエントリをマップから削除し、ページをマップに挿入します。
ページを返します。

キャッシュ ヒットの複雑度は O(1)、ミスの場合は O(b) です。
これは、周波数を制限することを前提としています。すなわち。「これまでで最も頻繁に使用されていない」ではなく、「最後の b リクエストで最も使用されていない」。