Solution Explanation
Runtime Complexity
get (hashset): 平均的なケースでO(1)、最悪のケースでO(n)
set (hashset): 定数、O(1)
新規要素追加時のheadでの削除(リンクリスト): 定数、O(1)
新規要素追加時のheadでの削除。 定数、O(1)
削除とtailへの追加のための検索(リンクリスト)。 O(n)
複雑である。 O(n)
メモリ複雑さ
線形、O(n) ここで n はキャッシュのサイズです。
解決策の内訳
キャッシュは、将来の要求を高速で処理するために、より速いストレージ（通常は RAM）にデータを格納する技術であります。 以下は、キャッシュが使用される一般的な例です。
- A processor cache is used to read data faster from main memory (RAM).
- Cache in RAM can be used to store part of disk data in RAM and serve future requests faster.
- Network responses can be cached in RAM to avoid too many network calls.
しかしながら、通常キャッシュ ストアはフル データセットを格納するには十分な大きさを持っていないためです。 そのため、キャッシュがいっぱいになるたびに、キャッシュからデータを退避させる必要があります。 キャッシュ退去ポリシーを実装するために、多くのキャッシュアルゴリズムがある。 LRU は非常に単純で、よく使われるアルゴリズムである。 LRU アルゴリズムの中核概念は、より多くのデータを収容するために、最も古いデータをキャッシュから追い出すことです。
LRU キャッシュを実装するには、ハッシュマップと 2 つのデータ構造、すなわち 2 重リンクリストを使用します。 二重リンクリストは退去順序を維持するのに役立ち、ハッシュマップはキャッシュされたキーの O(1) ルックアップに役立つ。 以下はLRUキャッシュのアルゴリズムである。
If the element exists in hashmapmove the accessed element to the tail of the linked listOtherwise,if eviction is needed i.e. cache is already fullRemove the head element from doubly linked list and delete its hashmap entryAdd the new element at the tail of linked list and in hashmapGet from Cache and Return二重リンクリストは最近アクセスされた要素を追跡するために使用されることに注意すること。 2重リンクリストの末尾にある要素が最も最近アクセスされた要素である。 (putで)新しく挿入された要素はすべてリストの末尾に移動する。 同様に、（get操作で）アクセスされた要素はリストの末尾に移動する。
