LRUキャッシュとは、Least Recently Used Cacheの略で、最近使用したエントリを削除するキャッシュのことです。 キャッシュの目的は、データを取得するための高速で効率的な方法を提供することであるため、特定の要件を満たす必要がある。 キャッシュは、メモリ使用量を制限するための境界を持つ必要があります。
LRUキャッシュの場合、最も最近使われたエントリを退避させるので、最近使ったエントリ、長い間使われていないエントリ、最近使ったエントリを追跡しなければならない。 HashMapはO(1)の挿入と検索を提供するが、HashMapには最近照会されたエントリとそうでないエントリを追跡する機構がない。
これを追跡するには、挿入、削除、更新が高速な別のデータ構造が必要で、LRUの場合はDoubly Linkedlistを使用する。 Doublely LinkList を選択する理由は、削除、更新、および挿入の操作を実行するノードのアドレスがある場合、O(1) です。 HashMapには、Doubly LinkedListのキーとノードのアドレスが格納されます。 そして、Doubly LinkedList はキーの値を保持します。
最近使用されたエントリを追跡する必要があるため、巧妙なアプローチを使用することにします。 要素を下部から削除し、LinkedListの開始点に要素を追加し、いずれかのエントリがアクセスされるたびに、それは上部に移動します。
LRU キャッシュを実装してみましょう。