キャッシュ追い出し
01 / 共通の仕組み
容量固定のストアで、get も put も O(1)。 鍵はデータ構造 — 各方針は同じ問いへの違う答えだ:満杯のときどれを捨てるか? 古典的な 2 つは同じ O(1) のトリックを共有する。LRU はハッシュマップと双方向連結リストを組み合わせ、直前にアクセスされたキーを定数時間で先頭に移す。LFU はキーごとの頻度をバケットで管理し、最小頻度バケットを常に O(1) で取り出せるようにする。
02 / 一文で言うと
触れたばかりのノードは先頭へ移し、末尾が次の追い出し候補。 ハッシュマップが O(1) の参照、双方向連結リストが O(1) の付け替え。合わせて 1 操作 O(1)。
問題LRU キャッシュを get / put 共に O(1) で設計容量4操作数8
空のキャッシュ、容量 4。これから 8 件の操作を実行。
ステップ
0 / 12
現在の操作
—
サイズ / 容量
0 / 4
0 / 12
03 / パターンの骨格
# 状態:capacity、map: key → node、list: head ↔ … ↔ taildef get(k):if k not in map: return −1node ← map[k]splice(node); pushFront(node)return node.valdef put(k, v):if k in map:node ← map[k]; node.val ← vsplice(node); pushFront(node); returnnode ← Node(k, v); map[k] ← nodepushFront(node)if len(map) > capacity: # 超過evicted ← popBack(); del map[evicted.key]
04 / このパターンを使うべき合図
「容量固定 + O(1) の get/put」
LRU の教科書的なシグネチャ。「キャッシュをしたいが両操作とも定数時間で」と言われたら合図 —— ハッシュマップ単独でもリスト単独でも届かない。両者を組み合わせて初めて成立する。
「最も古いものを追い出す」
新しさはリストの順序が持っており、タイムスタンプは要らない。読み書きのたびに触れたノードを先頭へ移すので、 末尾は常に「最も久しく触れられていないもの」となる。時刻計測も走査も不要 —— リストが順序を維持してくれる。
「move-to-front の感触」
LC 432(All O`one)や LC 1756(Most Recently Used Queue)など、題は違ってもリズムは同じ —— ハッシュマップから連結構造の任意ノードに飛び、それを O(1) で指定の端に動かす。 LRU の枠を超えてよく使われる手筋。
05 / よくある落とし穴
追い出し後にマップから削除し忘れる。
末尾ノードを取り出したら同時に
del map[evicted.key] も必要 —— さもないとマップ側はそのキーがまだキャッシュにあると主張し続け、後の get は 既にリストから外れた古いノードを平然と返してしまう。マップとリストは必ず歩調を合わせる。容量判定のオフバイワン。
追い出しの条件は
size > capacity であって ≥ ではない。 先に挿入し、超えていれば追い出す —— こうすれば新ノードを置く隙間が常に確保される。 順序や比較を逆にすると、せっかく挿入したエントリを失うか、まったく追い出されないかになる。put による値更新時に先頭への移動を忘れる。
既存キーの値更新も「触れた」とみなす —— LRU 方策は読みか書きかを問わず、起きたかどうかだけを見る。 先頭へ動かし忘れると、追い出し順が実際のアクセス順から静かに乖離していく。 バグは後の put が容量を超えたときにようやく表面化する。
06 / LeetCode で練習
4 問。LRU Cache は教科書的な実装。LFU Cache は同じ「マップ + 連結リスト」の上にもう一段、 頻度の管理層を重ねたもの。All O`one は move-to-front を一般化し、最大と最小を同時に O(1) で扱う。First Unique Number は同じハッシュ + 連結の手筋を、ストリームの一意性問題に応用する。
— / どれをいつ使うか
LRU
シグナルが アクセスの新しさ のとき用いる — 直近に使ったものは再び使われやすい。 ハッシュマップが key → ノードを保ち、双方向連結リストが順序を保つ。 get / put は数本のポインタ操作とハッシュ参照 1 回、堂々の O(1)。
ハッシュマップ + 双方向連結リスト · LC 146
LFU
シグナルが アクセス頻度 のとき用いる — 最近触っていなくても、よく使われていたキーは新規挿入の冷たいキーに押し出されるべきではない。 ハッシュマップ → ノード、頻度ごとのバケットリスト、追い出し候補のバケットを指す `minFreq` ポインタ。 O(1) を維持するコストは記帳の増加。
ハッシュマップ + 頻度バケット · LC 460