LRU キャッシュ（LeetCode #146）

LRU キャッシュは最近使ったキーと値を残し、容量を超えると最も長く未使用の項目を捨てます。課題は get と put の後に、高速な位置検索と使用順を、全走査せず維持することです。

カードを一列に並べ、左を最近、右を最古とします。カードをすでに持っていれば前へ移せますが、キーから探すには別の索引が必要です。Python の functools.lru_cache、Redis の近似 allkeys-lru、OS の LRU 型置換も最近の使用という考え方を使いますが、詳細な仕組みは同一ではありません。

LRU キャッシュの仕組み

ハッシュ表と双方向リストの分担

ハッシュ表はキーをリストのノードへ写し、期待 O(1) で位置を得ます。双方向リストは新旧の順序を保存し、既知ノードの取り外しと先頭挿入を定数回の参照変更で行います。

表は「キーはどこか」、リストは「どれが最新・最古か」を答えます。両者の有効項目集合は同じでなければなりません。リストのキーは表にあり、表が指すノードはリストにあります。

使用順のリスト

MRU（最近使用）から LRU（最も長く未使用）へ並べ、実データを持たない番兵を両端に置きます。

HEAD ↔ MRU ↔ ... ↔ LRU ↔ TAIL

先頭挿入は常に HEAD と HEAD.next の間、追い出しは TAIL.prev です。番兵により空や一ノードでも同じ内部接続規則を使えます。

取り外しは before = node.prev、after = node.next を保存し、before.next = after、after.prev = before と書きます。

先頭へ入れる時は HEAD と現在の先頭ノード（空なら TAIL）の間で、新ノードの二リンクを更新し、HEAD.next とその先頭ノードの prev を変えます。

画面は各書き込みを分けます。一時的に表が指すノードがリストから外れたり、表への追加前にリストへ入ったりします。これは操作内部の状態で、各公開操作の完了時には一致を回復します。

操作をステップで追う

get

get(key) は表を調べます。なければ -1 を返し、何も動かしません。キャッシュ項目を使えていないからです。

あればノードを得て値を保存し、取り外して HEAD の直後へ入れ、値を返します。読み取りでも使用順が変わります。すでに MRU なら参照変更を省けますが、最後に最前であることが必要です。

put

既存キーなら元ノードの値を更新し、同じノードを先頭へ移します。複製もサイズ増加もしません。

新キーならノードを作り、先頭へ追加し、key → node を表へ書きます。表のサイズが capacity を超えたら TAIL.prev を選び、リストと表の両方から外します。

リストだけから消すと古い表参照が残り、表だけならキーで見つからないノードがリストを占めます。二つの削除が一回の論理的な追い出しです。

既定の列

容量 3 で次を実行します。

put(1, 10), put(2, 20), put(3, 30), get(1), put(4, 40)

最初の三回で 3, 2, 1。3 が最新、1 が最古です。

get(1) は 10 を返し、1 を前へ移して 1, 3, 2。キー集合は同じでも、次の追い出し対象が変わります。

put(4, 40) はまず 4, 1, 3, 2 を作り、サイズ 4 が容量を超えます。TAIL.prev のキー 2 をノードと表から外し、最後は 4, 1, 3。

途中の成功した get(1) がなければ 1 が最古のままで、最後に 1 を捨てます。読み取りも置換方針の一部です。

時間・空間計算量

ハッシュは期待 O(1) のモデルです。リストは位置を走査せず、その部分は最悪 O(1) です。

境界ケース

• 容量 1：最初の挿入以降、新キーが唯一の旧キーを置き換える。番兵で接続手順は同じ。
• get が未発見：-1 で順序不変。
• 既存キー更新：値を上書きし MRU へ移し、サイズ不変。
• 現在の MRU を get：値を返し、見える順序は不変。
• 更新でノードを再利用：複製すると表が一方を指し、リストに別のコピーが残る恐れがある。

よくある間違い

• get を読み取り専用とする。 成功したキーは MRU へ移します。
• 先頭を追い出す。 この順序では先頭が最新、末尾が最古です。TAIL.prev を使います。
• 隣接参照を保存せず変更する。 必要な隣を先に保持し、公開操作の終了時に表とリストを同期します。

番兵は分岐を減らすだけです。表で位置を探し、同じノード集合をリストで並べる不変条件は必要です。